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

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