Генерация сочетаний без повторений

Требуется перебрать все комбинации группы символов от 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
Если вам не нужны одиночные комбинации, то можете их выбросить :)