Динамический генератор символов; Сгенерируйте все возможные строки из набора символов

Question

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

Я могу сделать это очень легко, используя для циклов, но затем его статическую и не динамическую длину.

// Prints all possible strings with the length of 3 

for a in allowedCharacters { 
    for b in allowedCharacters { 
     for c in allowedCharacters { 
      println(a+b+c) 
     } 
    } 
} 

Но когда я хочу, чтобы сделать эту динамику длины, так что я могу просто позвонить generate(length: 5) я запутаться.

Я нашел это Stackoverflow question Но принятый ответ генерирует строки длиной 1-maxLength, и я хочу maxLength на любой строке.

Answer 1

Как указано выше, используйте рекурсию. Вот как это можно сделать с помощью C#:

static IEnumerable<string> Generate(int length, char[] allowed_chars) 
{ 
    if (length == 1) 
    { 
     foreach (char c in allowed_chars) 
      yield return c.ToString(); 
    } 
    else 
    { 
     var sub_strings = Generate(length - 1, allowed_chars); 

     foreach (char c in allowed_chars) 
     { 
      foreach (string sub in sub_strings) 
      { 
       yield return c + sub; 
      } 

     } 
    } 
} 

private static void Main(string[] args) 
{ 

    string chars = "abc"; 

    List<string> result = Generate(3, chars.ToCharArray()).ToList(); 

} 

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

Answer 2

Перевода @ C# код YacoubMassad к Swift:

func generate(length: Int, allowedChars: [String]) -> [String] { 
    if length == 1 { 
     return allowedChars 
    } 
    else { 
     let subStrings = generate(length - 1, allowedChars: allowedChars) 

     var arr = [String]() 
     for c in allowedChars { 
      for sub in subStrings { 
       arr.append(c + sub) 
      } 
     } 

     return arr 
    } 
} 

println(generate(3, allowedChars: ["a", "b", "c"])) 

гравюр:

ааа, ааЪ, ААС, аба, АВВЫ, азбука, ас, ACB, акк, бея, бабы, BAC, BBA, ГЭБ, BBC, BCA, BCB, ОЦК, CAA, кабина, сас, CBA, CBB, CBC, CCA, CCB, ссс

Answer 3

в то время как вы можете (достаточно очевидно) использовать рекурсию, чтобы решить T его проблема, это довольно неэффективный способ выполнить эту работу.

Что вы действительно делаете, просто считаете. В вашем примере с «a», «b» и «c» в качестве допустимых символов вы считаете в базе 3, и поскольку вы разрешаете три символьные строки, они представляют собой трехзначные числа.

номер N-цифра в базовой M может представлять N ^M различных возможных значения, переходя от 0 до N ^М -1. Итак, для вашего дела, это limit=pow(3, 3)-1;. Чтобы сгенерировать все эти значения, вы просто считаете от 0 до предела и конвертируете каждое число в базу M, используя указанные символы в качестве «цифр». Например, в C++ код может выглядеть следующим образом:

#include <string> 
#include <iostream> 

int main() { 
    std::string letters = "abc"; 
    std::size_t base = letters.length(); 
    std::size_t digits = 3; 

    int limit = pow(base, digits); 

    for (int i = 0; i < limit; i++) { 
     int in = i; 
     for (int j = 0; j < digits; j++) { 
      std::cout << letters[in%base]; 
      in /= base; 
     } 
     std::cout << "\t"; 
    } 
} 

Одно незначительное замечание: как я написал здесь, это производит вывод в основном используется прямой порядок байтов. То есть, «цифра», которая отличается самым быстрым, находится слева, а одна, которая меняет самый медленный, находится справа.