Generate all possible strings of length l with n characters

Question

I want to generate all possible strings of a certain length l given n characters.

So for example if l = 2 and the characters are [a,b,c] the result should be: 'aa', 'ab', 'ac', 'ba', 'bb','bc', 'ca', 'cb' and 'cc'.

Initially I had done this using a recursive algorithm that would do this. However, I get a lot of duplicates and it is very time consuming.

Moreover, I thought about an algorithm that would "count" in base n. So, in the example above if I replace a->0, b->1 and c->2 I am effectively counting to 'cc'-> 22 in base 3. However, this also strikes me as inefficient.

Any suggestions ?

What do you mean, "I get a lot of duplicates"? "counting" in base N is exactly the usual non-recursive algorithm. You can see it in action in Python's source [here](https://github.com/python/cpython/blob/master/Modules/itertoolsmodule.c#L2588), as the next item is evaluated by "incrementing" a tuple containing "digits". — Amadan, Dec 10 '18 at 07:32
Possible duplicate of [Listing all permutations of a string/integer](https://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer) — HEWhoDoesn'tKnow, Dec 10 '18 at 07:32
This is exactly what I mean, however it does not support that the length of the string be longer than the size of the set of characters — popololvic, Dec 10 '18 at 07:35
@Amadan I know it, don't need to point it out. One of the tags is PERMUTATION so I provided a link. — HEWhoDoesn'tKnow, Dec 10 '18 at 07:35
Show us **YOUR** code. Use a debugger to find out why duplicates are generated. — MrSmith42, Dec 10 '18 at 08:01

Dmitry Bychenko · Answer 1 · 2018-12-10T12:48:37.313

You don't have to implement any recoursion. All you have to do is to get the next item from previous one

 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 -> ...

Code (C#); let's generalize the solution (any alphabet not necessary 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));
}

Demo:

// 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)));

Outcome:

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

score 0 · Answer 2 · answered Dec 10 '18 at 08:12

0

Yes, you can represent "count base n" using division.

Alternative implementation - traverse all n^m values using approach like old electric counter wheels:

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']

answered Dec 10 '18 at 08:12

MBo

77,366
5
53
86

in python, you can use directly itertools.product(src, repeat=m). Moreover as it is a generator, there is no risk of memory overload. – Vince Dec 10 '18 at 10:53
@Vince You are right. I just wanted to show general approach (author didn't mention specific language) – MBo Dec 10 '18 at 11:01

Generate all possible strings of length l with n characters

2 Answers2