Перебор всех подмножеств заданного множества (Java)

Пусть дано множество, состоящее из четырех элементов: {a,b,c,d}.
Необходимо перебрать все возможные подмножества данного множества:
1) {} — пустое множество
2) {a}
3) {b}
4) {a,b}
5) {c}
6) {a,c}
7) {b,c}
8) {a,b,c}
9) {d}
10) {a,d}
11) {b,d}
12) {a,b,d}
13) {c,d}
14) {a,c,d}
15) {b,c,d}
16) {a,b,c,d}

Причем подмножества {a,b} и {b,a} считаются одним и тем же подмножеством.

Данную задачу будем решать с использованием битовых масок и битовых операций.
Сразу приведу реализацию:

char arr[] = new char[]{'a','b','c','d'};
int N = arr.length;
for (int mask = 0; mask < (1 << N); mask++) {//перебор масок			
	for (int j = 0; j < N; j++) {//перебор индексов массива
		if((mask & (1 << j)) != 0){//поиск индекса в маске
			System.out.print(arr[j] + " ");//вывод элемента
		}
	}
	System.out.println();//перевод строки для вывод следующего подмножества
}

А теперь пояснения.
1 << N — побитовый сдвиг единицы на N позиций влево.
В двоичном виде единица выглядит так 00000001. В нашем случае N = 4.
После сдвига на 4 позиции влево появится новое число, двоичный вид которого 00010000. Теперь, если вычесть из этого числа единицу получим: 00001111. Если опустить ведущие нули, то получим 1111. Четыре единицы — это состояние, когда в подмножество попадают все элементы, 0000 — пустое множество, 1010 — подмножество состоит из первого и третьего элемента множества (нумерация с нуля, отсчет ведется справа) и т.д.
Т.е. мы перебираем числа, двоичное представление которых от 0000 до 1111.

После того как мы получили маску (mask), необходимо узнать в каких позициях стоят единицы. Проверять будем следующим образом.
Например, на каком-то шаге цикла программы маска равна 1100, мы перебираем все позиции путем сдвига единицы: 0001, 0010, 0100 и 1000. Для проверки воспользуемся операцией побитового И (если в одинаковых позициях стоят единицы, то результат единица, иначе ноль). В Java обозначается как &
В нашем случае:
1100 & 0001 = 0000
1100 & 0010 = 0000
1100 & 0100 = 0100
1100 & 1000 = 1000
Т.е. если в итоге получилось число отличное от нуля, то включаем элемент в множество.
0100 — включаем в множество элемент с индексом 2
1000 — включаем в множество элемент с индексом 3
Нумерация с нуля и справа.
Результат работы программы (первая строка пустая — это пустое множество):


a 
b 
a b 
c 
a c 
b c 
a b c 
d 
a d 
b d 
a b d 
c d 
a c d 
b c d 
a b c d 

В данной реализации мы хранили маски в типе int.
(1 << 30) равно 1 073 741 824 Безопасное значение N для типа int: 30. Свыше 30 будет переполнение переменных типа int, поэтому нужно использовать long.
При N > 30 перебор будет ощутимо все медленнее и медленнее.

Если будете делать реализацию с long, то при сдвиге единицы нужно писать так:

1L << j

Т.е. нужно к единице приписать L, и тогда результат операции будет long, в противном случае будет int с переполнением.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.