Сгенерируйте все возможные строки длиной l с n символами

Question

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

Так, например, если l = 2 и символы [a, b, c], результат должен быть: 'aa',' ab ',' ac ',' ba ',' bb ',' bc ',' ca ',' cb 'и' cc '.

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

Более того, я подумал об алгоритме, который будет "рассчитывать" в базе n.Таким образом, в приведенном выше примере, если я заменю a-> 0, b-> 1 и c-> 2, я эффективно считаю «cc» -> 22 в базе 3. Однако это также кажется мне неэффективным.

Есть предложения?

Answer 1

Да, вы можете представить "считать базу n", используя деление.

Альтернативная реализация - пройти все значения n^m, используя подход, подобный старым электрическим встречным колесам:

src = "abc";
n = len(src)
m = 2
l = [0]*m
i = 0
while i < m:
    print([src[x] for x in l])
    i = 0
    l[i] += 1
    while (i < m) and l[i] >= n:
        l[i] = 0
        i += 1
        if i < m:
            l[i] += 1

['a', 'a']
['b', 'a']
['c', 'a']
['a', 'b']
['b', 'b']
['c', 'b']
['a', 'c']
['b', 'c']
['c', 'c']

Answer 2

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

 aa -> ab -> ac -> : we can't add 1 to c so why reset the last 'c' to 'a' 
                     but add 1 to previous 'a': 'ba'
                     now we keep on adding one to the last 'a':
 ba -> bb -> bc -> : again we reset 'c' to 'a' and increment previous b
 ca -> ...

Код (C #) ;давайте обобщим решение (любое alphabet необязательно string)

// alphabet should contain distinct items
private static IEnumerable<T[]> Solution<T>(IEnumerable<T> alphabet, int length) {
  if (null == alphabet)
    throw new ArgumentNullException(nameof(alphabet));

  var chars = alphabet.Distinct().ToArray();

  if (length <= 0 || chars.Length <= 0)
    yield break;

  int[] result = new int[length];

  do {
    yield return result
      .Select(i => chars[i])
      .ToArray();

    for (int i = result.Length - 1; i >=0 ; --i)
      if (result[i] == chars.Length - 1) 
        result[i] = 0;
      else {
        result[i] += 1;
        break;
      }
  }
  while (!result.All(item => item == 0));
}

Демо:

// Or     var test = Solution("abc", 2);
var test = Solution(new char[] { 'a', 'b', 'c' }, 2);

var report = string.Join(", ", test
  .Select(item => string.Concat(item)));

Итог:

aa, ab, ac, ba, bb, bc, ca, cb, cc