4

Требуется перебрать все комбинации группы символов от 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);
    }
}
6
  • забыл группу - BD
    – user176262
    14 янв 2016 в 20:12
  • не знаю, как на русском, а на английском стэке вопросов про combination просто немеряно, полистайте, точно найдете
    – splash58
    14 янв 2016 в 20:15
  • @AlexShawnee Вообще вы много забыли или ошиблись с CDA. Раз у вас буква A может быть в конце, т.е. буквы не всегда возрастают то у вас должна быть еще масса всяких BA DA CA DBA DAB DAC и т.п.
    – Mike
    14 янв 2016 в 20:41
  • А одиночные A, B, C, D? Не обидятся?
    – LEQADA
    14 янв 2016 в 20:41
  • @Mike, мне кажется, что автору нужно сочетание, а не размещение. Ну, и да, должно быть ACD, а не CDA.
    – LEQADA
    14 янв 2016 в 20:43

2 ответа 2

9

Предисловие

Я очень люблю следующий алгоритм из-за его просто детской простоты. Он не претендует на звание самого быстрого алгоритма, но является самым простым для понимания из всех, что я встречал.

Алгоритм

Если учитывать и одиночные комбинации (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

Если вам не нужны одиночные комбинации, то можете их выбросить :)

1

Для начала - о терминах.
Возьмём для примера новогодние подарки. которых N штук в мешке.
Перестановки - когда эти подарки раскладывают на N полок (порядок важен).
Вариантов: N!.
Размещения - когда их пытаются разложить на M полок (попадают не все, порядок важен).
Вариантов: N! / M!.
Сочетания - когда их пытаются переложить в другой мешок (порядок неважен), в который входит только M штук.
Вариантов: N! / (M!(N-m)!) = CNM.

Судя по постановке задачи (порядок неважен), речь идёт о сочетаниях, причём могут потребоваться либо они все (M = 1...N) либо диапазон в 2-3 элемента.

Программно реализована функция, которая может вызываться с разным числом параметров. Если на входе только массив символов, на выходе - все возможные сочетания. Но можно указать также M (один дополнительный параметр) или диапазон M (параметры from, to).

Программа на PHP:

function placing($chars, $from=0, $to = 0){
    $cnt = count($chars);
    if(($from == 0) && ($to == 0)){
        $from = 1;
        $to = $cnt;
    }
    if($from == 0) $from = 1;
    if($to == 0) $to = $from;
    if($from < $to){
        $plac = [];
        for($num = $from; $num <= $to; $num++){
            $plac = array_merge($plac, placing(["A","B","C","D"], $num));
        }
    }else{
        $plac = [""];   
        for($n = 0; $n < $from; $n++){
            $plac_old = $plac;
            $plac = [];
            foreach($plac_old as $item){
                $last = strlen($item)-1;
                for($m = $n; $m < $cnt; $m++){
                    if($chars[$m] > $item[$last]){
                        $plac[] = $item.$chars[$m];
                    }
                }
            }
        }
    }
    return $plac;
}

$plac = placing(["A","B","C","D"]);
var_dump($plac);
$plac = placing(["A","B","C","D"],2);
var_dump($plac);
$plac = placing(["A","B","C","D"],2,3);
var_dump($plac);

Результаты:

array (size=15)
  0 => string 'A' (length=1)
  1 => string 'B' (length=1)
  2 => string 'C' (length=1)
  3 => string 'D' (length=1)
  4 => string 'AB' (length=2)
  5 => string 'AC' (length=2)
  6 => string 'AD' (length=2)
  7 => string 'BC' (length=2)
  8 => string 'BD' (length=2)
  9 => string 'CD' (length=2)
  10 => string 'ABC' (length=3)
  11 => string 'ABD' (length=3)
  12 => string 'ACD' (length=3)
  13 => string 'BCD' (length=3)
  14 => string 'ABCD' (length=4)
array (size=6)
  0 => string 'AB' (length=2)
  1 => string 'AC' (length=2)
  2 => string 'AD' (length=2)
  3 => string 'BC' (length=2)
  4 => string 'BD' (length=2)
  5 => string 'CD' (length=2)
array (size=10)
  0 => string 'AB' (length=2)
  1 => string 'AC' (length=2)
  2 => string 'AD' (length=2)
  3 => string 'BC' (length=2)
  4 => string 'BD' (length=2)
  5 => string 'CD' (length=2)
  6 => string 'ABC' (length=3)
  7 => string 'ABD' (length=3)
  8 => string 'ACD' (length=3)
  9 => string 'BCD' (length=3)

Заметим, что в соответствии с формулой бинома Ньютона суммарное число всех перестановок символизирует число (1+1)N. При N=4 это 16, но программа в первом варианте выдаёт 15. Чтобы баланс сходился, надо добавить к перестановкам пустую строку.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.