#php #алгоритм #математика
Требуется перебрать все комбинации группы символов от 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);
}
}
Ответы
Ответ 1
Предисловие Я очень люблю следующий алгоритм из-за его просто детской простоты. Он не претендует на звание самого быстрого алгоритма, но является самым простым для понимания из всех, что я встречал. Алгоритм Если учитывать и одиночные комбинации (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 Если вам не нужны одиночные комбинации, то можете их выбросить :)Ответ 2
Для начала - о терминах. Возьмём для примера новогодние подарки. которых 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. Чтобы баланс сходился, надо добавить к перестановкам пустую строку.
Комментариев нет:
Отправить комментарий