Как сделать перебор всех возможных комбинаций из символов
Обновлено: 07.07.2024
Обучение переводу статей англоязычной документации, статьи про алгоритмы, а также LifeHacks, статьи по Компьютеру и Программированию, Журнал для Детей, Математику и смежные науки Инженерии.
Поиск по этому блогу
Алгоритмы - Полный перебор по алфавиту
Статья раcсматривывает алгоритм перебора по алфавиту. Статья является основой для классов программ для Полного перебора по алфавиту и с его использованием. Полный перебор по алфавиту представляет собой выдачу строк от начальной позиции до конечной из символов, заданных в начальном алфавите. Приведены примеры реализации на языке Java. Перебирать так же можно не только строковые значения, но и другие типы данных.
Программа перебора сочетаний и размещений
Постановка задачи
Рассмотрим задачу перебора сочетаний и размещений. Пусть мы хотим перебрать комбинации из четырех цифр по два элемента. Если одинаковые цифры не допускаются (размещение без повторений), то таких комбинаций будет 4!/(4-2)!=12.
если же повторы цифр возможны (размещение с повторениями), то комбинаций будет больше 4 2 =16.
если повтор цифр невозможен и их порядок неважен, то есть наборы и одинаковы, то число комбинаций будет 4!/(4-2)!/2!=6 - это называется сочетанием.
В общем виде требуется перебрать все комбинации из n объектов по k элементов с одной из опций: размещение с повторениями, размещение без повторений, сочетание. Написать такую программу перебора "в лоб" не получится. Вот как будет выглядеть примерный код программы.
Для размещений c повторениями
int * i = new int [ k ];
for ( i [ 0 ] = 0 ; i [ 0 ] n ; i [ 0 ]++) <
for ( i [ 1 ] = 0 ; i [ 1 ] n ; i [ 1 ]++) <
for ( i [ 2 ] = 0 ; i [ 2 ] n ; i [ 2 ]++) <
//.
>
>
>
delete [] i ;
Для размещений без повторений
int * i = new int [ k ];
for ( i [ 0 ] = 0 ; i [ 0 ] n ; i [ 0 ]++) <
for ( i [ 1 ] = 0 ; i [ 1 ] n ; i [ 1 ]++) <
if ( i [ 1 ] == i [ 0 ]) <
continue ;
>
for ( i [ 2 ] = 0 ; i [ 2 ] n ; i [ 2 ]++) <
if ( i [ 2 ] == i [ 0 ] || i [ 2 ] == i [ 1 ]) <
continue ;
>
//.
>
>
>
delete [] i ;
int * i = new int [ k ];
for ( i [ 0 ] = 0 ; i [ 0 ] n ; i [ 0 ]++) <
for ( i [ 1 ] = i [ 0 ] + 1 ; i [ 1 ] n ; i [ 1 ]++) <
for ( i [ 2 ] = i [ 1 ] + 1 ; i [ 2 ] n ; i [ 2 ]++) <
//.
>
>
>
delete [] i ;
Проблема заключается в том, что число вложенных циклов является параметром (количество циклов равно k), поэтому в общем случае нужно использовать другой подход.
Решение
Размещения с повторениями
Каждый индекс i[j] может быть от 0 до n. Все что нужно сделать - это написать алгоритм перехода от текущего набора индексов i[0]. i[k-1] к следующему набору. Рассмотрим начальный набор 0. 0,0. Следующими наборами будут 0. 0,1 0. 0,2 и так далее. Будем прибавлять к последнему индексу единицу до тех пор пока он не станет равным n-1. Когда индекс равен n-1, больше его увеличивать нельзя, теперь нужно перейти к предыдущему индексу, а этот обнулить, тогда из набора 0. 0,n-1 мы получим набор 0. 1,0. Таким образом, алгоритм состоит в том, чтобы идти от последнего индекса к первому, до тех пор пока текущее значение индекса равно n-1. Мы получим номер индекса к которому нужно прибавить единицу и обнулить все индексы, следующие за ним. Если этот номер равен -1, то мы достигли последнего набора. С помощью подобных рассуждений можно создать алгоритм перебора размещений без повторений и сочетаний.
Размещения без повторений
Рассмотрим более сложный случай - размещения без повторений. В этом случае неоходимо выполнение условие n≥k, иначе число размещений равно нулю. Можно использовать тот же алгоритм, что и для размещений с повторениями и отбрасывать случаи, когда хотя бы два индекса совпадут, но в этом случае придется перебирать множество ненужных комбинаций. Будем считать, что индексы будут меняться в диапазоне 0≤i[0]≤n-1, 0≤i[1]≤n-2 . 0≤i[k-1]≤n-k (0≤i[j]≤n-1-j). Опишем процедуру преобразования набора индексов i[0] . i[k-1] в набор несовпадающих индексов r[0] . r[k-1]. Рассмотрим набор целых чисел 0. k-1. Первый индекс i[0] будет означать номер среди этого набора (нумерацию ведем с нуля). Затем удалим из первоначального набора число соответствующее индексу i[0], после этого останется n-1 число, индекс i[1] 0≤i[1]≤n-2 означает номер элемента из оставшихся, после этого удалим этот элемент и так далее.
Рассмотрим пример. Пусть n=10 k=4 и есть набор индексов i[0]=3 i[1]=3 i[2]=4 i[3]=0. Берем набор чисел . Индекс i[0] равен трем, что соответствует четвертому элементу в наборе, то есть числу 3, соответственно r[0]=3. Теперь удалим число 3 из набора, получим набор . Индекс i[1] равен трем, что соответствует четвертому элементу в наборе - числу 4, то есть r[1]=4. Набор теперь такой . Аналогично i[2]=4 r[2]=6 набор оставшихся чисел , i[3]=0 r[3]=0. То есть из набора индексов i[]= получен набор несовпадающих чисел r[]=. Следует заметить, что для последнего индекса i[k-1], число можно уже и не удалять, хотя можно и удалить. Удаление лишь немного замедлит программу. Очевидно, что в наборе r[0] . r[k-1] числа никогда не совпадут. Нетрудно понять, что описанная выше процедура, является взаимно-однозначным соответствием между индексами i[] и несовпадающими числами r[]. Таким образом, осталось сделать процедуру перебора индексов i[0] . i[k-1] с учетом условия 0≤i[j]≤n-1-j ∀j.
Будем идти от последнего индекса к первому, до тех пор, пока текущее значение индекса i[j] равно n-1-j. После этого мы получим номер индекса j к которому нужно прибавить единицу и обнулить все индексы следующие за ним. При запросе значений нужно преобразовать набор индексов i[] в набор чисел r[] по правилу описанному выше.
Сочетания
int main () <
int i ;
PermutationType type [] = <
PERMUTATIONS_WITHOUT_REPLACEMENTS ,
PERMUTATIONS_WITH_REPLACEMENTS ,
COMBINATION
>;
Permutations p ;
for ( auto t : type ) <
p . init ( 2 , 4 , t );
printf ( "combinations=%2d " , p . number ());
do <
for ( i = 0 ; i p . getK (); i ++) <
printf ( "%c%d" , i == 0 ? ' >
printf ( ">" );
> while ( p . next ());
printf ( "\n" );
>
Результат работы программы
Аналогичный пример, использующий нововведения c++11
int main () <
int i ;
PermutationType type [] = <
PERMUTATIONS_WITHOUT_REPLACEMENTS ,
PERMUTATIONS_WITH_REPLACEMENTS ,
COMBINATION
>;
Permutations p ;
for ( auto t : type ) <
p . init ( 2 , 4 , t );
printf ( "combinations=%2d " , p . number ());
for ( auto & c : p ) <
i = 0 ;
for ( int v : c ) <
printf ( "%c%d" , i ++ ? ' ' : ' >
printf ( ">" );
>
printf ( "\n" );
>
Пример на java
public class Test
public static void main ( String [] args ) <
int i ;
Permutations p = new Permutations ();
for ( PermutationType type : PermutationType . values ()) <
p . init ( 2 , 4 , type );
System . out . format ( "combinations=%2d " , p . number ());
do <
System . out . print ( " for ( i = 0 ; i p . getK (); i ++) <
if ( i != 0 ) <
System . out . print ( " " );
>
System . out . print ( p . getIndex ( i ));
>
System . out . print ( ">" );
> while ( p . next ());
System . out . println ();
>
Я пытался создать список всех возможных 4 символьных строк, которые могут быть составлены из любого заданного набора символов. Я использовал функцию для генерации каждой 4-символьной комбинации из набора символов, но каждый символ используется только один раз. Мне нужна каждая возможная комбинация, используя данный набор символов, например:
использование класса CombinationGenerator из здесь, это вернет каждую уникальную комбинацию символов 4, такую как as:
но я хочу каждую возможную строку, которая может быть создана с использованием заданных символов. Например:
Я пробовал каждый рекурсивный и перестановочный метод, который мне удалось найти или придумать, но я в тупике, чтобы получить больше, чем генерировать все комбинации, как указано выше, а затем генерировать каждую перестановку каждой комбинации, но я не могу понять, как создать набор комбинаций с использованием повторяющихся символов.
любой помощь, или даже просто теория о том, как это можно сделать, была бы полезной.
вы должны быть более конкретными в том, что именно вы хотите, чтобы ваша функция получила. Существует много различных определений "комбинаций", и вы не указали, хотите ли вы упорядоченные или неупорядоченные комбинации.
математически, если у вас есть n элементов и вам нужен список из k из них (упорядоченный с повторами), это дает вам
комбинаций. (6 ^ 4 = 1296 комбинаций в исходном примере, что очень много!). Однако, если у вас н элементы и хотят МУЛЬТИСЕТЬ из k из них (неупорядоченных с повторами), что дает вам
комбинации и является гораздо более сложным перечислением.
если k мало, вы можете создать первый с ограниченным количеством циклов for, но это становится громоздким очень быстро, как K растет. Это сильно намекает на необходимость рекурсивного метода:
этот метод не только создаст все списки, но и перечислит их по порядку. То есть выход будет
использование исходного ввода. Он также может генерировать любую длину слов (будьте очень осторожны с этим! Просто со словами длины 8 я закончил с 1,679,616 комбинациями!).
если метод смущает вас (это рекурсивный метод, поэтому его немного трудно следовать) или если вы хотите решить вторую комбинационную проблему, не стесняйтесь спрашивать. Кроме того, этот метод несколько неэффективен, поскольку он пересчитывает комбинации для всех подсписков, поэтому он не подходит для очень длинных списков. Если вы действительно хотите эффективности, вы сохраните уже вычисленные кортежи в глобальном списке.
Приветствую всех, сегодня мы рассмотрим пример при котором на входе задается длина комбинации, а символы которые будут использоваться в комбинации вносятся в методе MakeSubsets. Давно еще лет 5 назад, когда мне требовалось написать программу для подбора пароля из комбинаций цифр я использовал условные операторы и счетчики. Мой код был ужасен, а длина его была очень большой. Сейчас я покажу как с помощью рекурсии и простого кода вывести все комбинации символов a, b, c, d заданной длины пароля.
Читайте также: