4106. Генерация подмножеств

Задано множество s мощности n, содержащее все элементы из интервала [1..n]. Сгенерируйте все его подмножества.

Вход. Одно натуральное число n (1 ≤ n ≤ 8).

Выход. Каждое подмножество множества {1, …, n} следует выводить в отдельной строке. Подмножество записывается перечислением своих элементов в порядке возрастания. Элементы подмножества должны быть записаны без пробелов, то есть слитно. Каждое подмножество должно встречаться не более одного раза. Подмножества следует перечислять в возрастающем порядке. Пустое подмножество выводить не нужно.

Пример входа	Пример выхода
3	1 2 3 12 13 23 123

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

В задаче необходимо сгенерировать все подмножества заданного множества. Для этого переберем все числа от 1 до 2ⁿ – 1 (в цикле по i). Число i представляем в двоичном виде и рассматриваем его последние n бит (возможно с ведущими нулями). Каждому такому двоичному представлению соответствует подмножество: если на k-ом месте стоит единица, то в подмножество включается число k (1 ≤ k ≤ n). Например:

· если n = 3 и i = 2, то двоичному представлению i = 010₂ соответствует подмножество {2}.

· если n = 4 и i = 11, то двоичному представлению i = 1011₂ соответствует подмножество {1, 2, 4}.

Пример

Рассмотрим генерацию подмножеств для n = 3.

Реализация алгоритма

Подмножества будем генерировать в виде чисел в массиве v. Например, подмножество {1, 2, 3} будем представлять числом 123.

#define MAX 8

int v[1 << MAX];

Читаем входное значение n.

scanf("%d",&n);

В цикле перебираем все возможные маски для подмножеств множества из n элементов. Оператор 1 << n сдвигает единицу на n позиций влево, что эквивалентно возведению числа 2 в степень n. Генерируем все 2ⁿ – 1 подмножеств (кроме пустого).

for (i = 1; i < (1 << n); i++)

{

В переменной x сохраняем элементы текущего подмножества в строковом виде. Например, подмножество {1, 2, 4} будет сохранено как x = 124.

x = 0;

for (j = 0; j < n; j++)

if (i & (1 << j)) x = x * 10 + j + 1;

v[i] = x;

}

Отсортируем подмножества по возрастанию соответствующих им чисел.

sort(v, v + (1 << n));

Выводим подмножества в требуемом порядке.

for (i = 1; i < 1 << n; i++)

printf("%d\n", v[i]);

Java реализация

import java.util.*;

public class Main

{

public static void main(String []args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int v[] = new int[1<<n];

for(int i = 1; i < (1 << n); i++)

{

int val, j;

for(val = j = 0; j < n; j++)

if ((i & (1 << j)) > 0) val = val * 10 + j + 1;

v[i] = val;

}

Arrays.sort(v);

for(int i = 1; i < 1 << n; i++)

System.out.println(v[i]);

con.close();

}

}