Перебор всех возможных вариантов

В данной статье будет рассмотрено два алгоритма перебора всех возможных вариантов.

Для начала придумаем задачу, на примере которой будем рассматривать алгоритмы.
Пусть у нас имеется множество S, состоящее из 4-х элементов: * + /, и наша задача — перебрать все возможные комбинации из 3-х элементов, используя элементы множества S. Причем, выбираемые элементы могут повторяться. Например: «+*+».

Первый алгоритм

Сопоставим каждому элементу число, начиная с 0.
* — 0
— 1
+ — 2
/ — 3

Можно догадаться, что нужно перебрать элементы от 0 0 0 до 3 3 3:
0 0 0
0 0 1
0 0 2
0 0 3
0 1 0
0 0 1


3 2 3
3 3 0
3 3 1
3 3 2
3 3 3

Всего получится 64 варианта (4 * 4 * 4 = 64)

Далее нужно провести обратную операцию, сопоставив числу элемент множества S.
Например, набору 2 0 2 соответствует +*+

В алгоритме мы будем имитировать сложение в столбик, каждый раз прибавляя единицу, чтобы получить новый вариант.

Реализация:

char abc[] = new char[]{'*','-','+','/'};//множество допустимых символов
int size = 3;//кол-во элементов
int arr[] = new int[size];//массив для хранения текущего варианта множества
outer: while(true){//вечный цикл
 
	//вывод варианта множества на экран
	for(int ndx : arr){
		System.out.print(abc[ndx]);
	}
	System.out.println();
 
	int i = size - 1;//ставим курсов в самую правую ячейку
	while(arr[i] == abc.length - 1){//движемся влево, если ячейка переполнена
		arr[i] = 0;//записываем в ячейку 0, т.к. идет перенос разряда
		i--;//сдвиг влево
		//если перенос влево невозможен, значит перебор закончен
		if(i < 0)break outer;
	}
	arr[i]++;//увеличиваем значение ячейки на единицу
}

В результате программа выведет все 64 варианта:

***
**-
**+
**/
*-*
*--
...
...
/++
/+/
//*
//-
//+
///

Второй алгоритм
Для начала посчитаем сколько всего возможных комбинаций, это число равно n ^ k, где n — это размер алфавита (кол-во допустимых символов), а k — кол-во элементов в комбинации.
Для нашего множества S, состоящего из *,,+ и /, n равно 4. И т.к. нужно перебрать все комбинации из трех элементов, то k равно 3.
Получаем: n ^ k = 4 ^ 3 = 64.
В итоге мы должны получить 64 комбинации.
Вот если бы существовал способ преобразования номера комбинации в элементы комбинации.
И такой способ существует: для этого нужно номер комбинации преобразовать в k-значное число в системе счисления по основанию n.
Первой комбинации будет соответствовать число 0, а последней 63.
Перебирая числа от 0 до 63, нам нужно каждое число преобразовать в число в систему счисления по основанию 4. Для получения разрядов числа нужно целочисленно разделить число на 1, 4, 16 (т.е. n^0, n^1, n^2) и результат взять по модулю n.
Пример: для числа 57 при k = 3 и n = 4
(57 / 1) % 4 = 57 % 4 = 1 (-)
(57 / 4) % 4 = 14 % 4 = 2 (+)
(57 / 16) % 4 = 3 % 4 = 3 (/)
Т.е. комбинации под номером 57 соответствует комбинация -+/

char abc[] = new char[]{'*','-','+','/'};//множество допустимых символов (алфавит)
int N = abc.length;//N - размер алфавита
int K = 3;//кол-во элементов в комбинации
 
int pow[] = new int[K + 1];//массив для степеней числа N: N^0, N^1, .., N^K   
pow[0] = 1;
for (int i = 1; i <= K; i++) {//вычисляем степени числа N
	pow[i] = pow[i - 1] * N
}
 
//перебираем все номера комбинаций
for (int i = 0; i < pow[K]; i++) {
	char arr[] = new char[K];
	//вычисляем элементы комбинации
	for (int j = 0; j < K; j++) {
		//каждый элемент получаем из массива abc по индексу,
		//индекс - это число в системе счисления по основанию N (0..N-1)
		//в соответствующем разряде j (от 0 до K-1 включительно)
		arr[j] = abc[(i / pow[j]) % N];
	}
	//вывод в консоль
	for(char ch : arr){
		System.out.print(ch);
	}
	System.out.println();
}

Вывод программы:

0 ***
1 -**
2 +**
3 /**
4 *-*
.....
57 -+/
58 ++/
59 /+/
60 *//
61 -//
62 +//
63 ///

В данном алгоритме перебор идет как бы слева направо, но это не важно, т.к. мы перебираем все комбинации.

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

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

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