Monday, March 30, 2009

Algorithms: Find string combinations

Задача: найти все комбинации заданой строки.

Эта задача очень близка задаче поиска всех возможных перестановок строки. Пожалуй, если вы не знакомы с алгоритмом поиска возможных перестановок строки, то я бы советовал для начала ознакомится с ним.

Для начала в двух словах раскажу что такое комбинации в строке. Рассмотрим строку "abcd". В этой строке, например, две пары "ab" и "bc" являются комбинациями, в то время как "ab" и "ba" - нет.

Запишем теперь возможные комбинации для слова "abcd":

a b c d
ab bc cd  
abc bcd    
abcd bd    
abd      
ac      
acd      
ad      

В таблице выше представлены все возможные комбинации слова "abcd".

Итак, что мы можем получить из такого представления? А мы можем получить собственно сам алгоритм генерации комбинаций. Рассмотрим, к примеру, колонку "c" - как мы можем получить все комбинации для "c" - очень просто, берем "c", это будет одна комбинация, затем поочередно прибавляем значения со всех колонок справа. Получаем: "c" и "cd". Далее, расмотрим "b" - для "b" действует то же правило, берем "b", а затем к символу "b" прибавляем все значения из колонок справа... и так далее.

Следовательно, мы приходим к следующему рекурсивному алгоритму:

Для каждого символа во входящей строке, начиная со стартовой позиции и до конца
  Выбираем символ из входящей строки в результирующую
  Печатаем комбинацию
  Если текущий символ во входящей строке
    Переходим на следующий цикл рекурсии, начиная при этом с символа, следующим за текущим символом.

Приведу реализацию этого алгоритма на C# (и я думаю сразу "все станет на свои места"):

    1 /// <summary>

    2 /// Print string combinations.

    3 /// </summary>

    4 /// <param name="inputChars">Input string characters.</param>

    5 public static void PrintCombinations(char[] inputChars)

    6 {

    7     char[] outChars = new char[inputChars.Length];

    8     DoPrintCombinations(inputChars, outChars, 0, 0);

    9 }

   10 

   11 private static void DoPrintCombinations(char[] inputChars, char[] outChars, int level, int start)

   12 {

   13     for (int index = start; index < inputChars.Length; index++)

   14     {

   15         outChars[level] = inputChars[index];

   16         outChars.PrintArray();

   17         if (index < inputChars.Length - 1)

   18         {

   19             DoPrintCombinations(inputChars, outChars, level + 1, index + 1);

   20             outChars[level + 1] = '\0';

   21         }

   22     }

   23 }

Напомню, что PrintArray - это extension-метод, который мы ввели для облегчения вывода массивов на консоль.

 

Пример:

    1 public static void Main()

    2 {

    3     CommonAlgorithms.PrintCombinations("abcd".ToCharArray());

    4 }

 

Результатом работы этой програмки приведен ниже:

 

image

 

В следующий раз раскажу о поиске всех перестановок (хотя об этом надо было расказать сначала :))..

 

Happy coding...

No comments :

Post a Comment