Требуется перебрать все комбинации группы символов от A до X где X может быть любой другой буквой.
Пример: дана последовательность ABCD, функция должна выдать AB, AC, AD, BC, BD, CD, ABC, BCD, CDA, ABD (вроде ничего не забыл), т.е. позиция символа в группе не важна - важна лишь уникальность самой группы.
Гуглил в сторону размещений и сочетаний. Но так и не понял что именно из этого мне требуется. Грешен - не учил математику. Умные люди, объясните на пальцах или кодом, буду признателен.
Update:
Обычно говорят, - и года не прошло. А вот у меня как раз прошел. Снова понадобилось, в этот раз подошел обстоятельно - вот код на PHP:
function gen_comb ($rest, $current = "", $container = []) {
// Если пустой текущий и есть остаток
if(!$current and $rest)
{
// Текущему даем первый символ остатка
$current = substr($rest, 0, 1);
// Потом для каждого в остатке
for($i=strlen($rest); $i > 0; $i--)
// формируем пару с текущим и записываем в вывод
$container[] = $current . substr($rest, $i, strlen($rest));
// при этом проверяем - если в остатке один
if(strlen($rest) == 1 and $current)
// возвращаем результат
return $container;
// если в остатке больше одного и при вычете еще останется
if(strlen($rest) - 1)
// возвращаем рекурсивный результат с уменьшенным на 1 остатком
return gen_comb(substr($rest, 1, strlen($rest)), "", $container);
}
}
Ответ
Предисловие
Я очень люблю следующий алгоритм из-за его просто детской простоты. Он не претендует на звание самого быстрого алгоритма, но является самым простым для понимания из всех, что я встречал.
Алгоритм
Если учитывать и одиночные комбинации (A, B, C, D), то таких комбинаций всего 2n - 1, где n - количество символов в исходной строке.
Допустим, что у нас строка из n символов. То есть, у нас n позиций в строке.
A B C D E F G H ... n-1 n //
^ ^ ^ ^ ^ ^ ^ ^ ... ^ ^
1 2 3 4 5 6 7 8 ... n-1 n // порядковый номер каждой позиции
Рассмотрим каждую позицию нулём (0) либо единицей (1). Договоримся ставить 1 на той позиции, на которой мы хотим видеть символ, а 0 на той, на которой не хотим.
Получится примерно следующая строка из n нулей и единиц
0 1 0 0 1 0 0 0 ... 0 0 // полученная закодированная строка
^ ^ ^ ^ ^ ^ ^ ^ ... ^ ^
1 2 3 4 5 6 7 8 ... n-1 n // порядковый номер каждой позиции
Эта строка кодирует комбинацию
_ B _ _ E _ _ _ ... _ _ // комбинация строка
^ ^ ^ ^ ^ ^ ^ ^ ... ^ ^
1 2 3 4 5 6 7 8 ... n-1 n // порядковый номер каждой позиции
А теперь выпишем двоичный набор длиной в n элементов
0 0 0 0 0 0 0 0 ... 0 0|_ _ _ _ _ _ _ _ ... _ _
0 0 0 0 0 0 0 0 ... 0 1|_ _ _ _ _ _ _ _ ... _ n
0 0 0 0 0 0 0 0 ... 1 0|_ _ _ _ _ _ _ _ ... n-1 _
0 0 0 0 0 0 0 0 ... 1 1|_ _ _ _ _ _ _ _ ... n-1 n
.......................|.........................
1 1 1 1 1 1 1 1 ... 1 0|A B C D E F G H ... n-1 _
1 1 1 1 1 1 1 1 ... 1 1|A B C D E F G H ... n-1 n
Этот набор выписывается достаточно просто. Если просто, то на каждой новой строке к последнему элементу прибавляется единица. И если в результате получается число больше единицы, то позиция обнуляется и единица добавляется на соседнюю слева позицию и т.д.
Этот набор (без первого) будет описывать всевозможные комбинации исходной строки.
Пример
Возьмём строку ABCD. В ней 4 символа, а значит, у нас будет 24 - 1 = 15 комбинаций.
Выпишем двоичный набор из 4 элементов
0 0 0 0|_ _ _ _
0 0 0 1|_ _ _ D
0 0 1 0|_ _ C _
0 0 1 1|_ _ C D
0 1 0 0|_ B _ _
0 1 0 1|_ B _ D
0 1 1 0|_ B C _
0 1 1 1|_ B C D
1 0 0 0|A _ _ _
1 0 0 1|A _ _ D
1 0 1 0|A _ C _
1 0 1 1|A _ C D
1 1 0 0|A B _ _
1 1 0 1|A B _ D
1 1 1 0|A B C _
1 1 1 1|A B C D
И получаем следующие варианты
1) D
2) C
3) CD
4) B
5) BD
6) BC
7) BCD
8) A
9) AD
10) AC
11) ACD
12) AB
13) ABD
14) ABC
15) ABCD
Если вам не нужны одиночные комбинации, то можете их выбросить :)