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