Перебор всех подмножеств заданного множества (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 для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.