Algorithm for generating all string combinations

Question

Say I have a list of strings, like so:

strings = ["abc", "def", "ghij"]

Note that the length of a string in the list can vary.

The way you generate a new string is to take one letter from each element of the list, in order. Examples: "adg" and "bfi", but not "dch" because the letters are not in the same order in which they appear in the list. So in this case where I know that there are only three elements in the list, I could fairly easily generate all possible combinations with a nested for loop structure, something like this:

for i in strings[0].length:
   for ii in strings[1].length:
      for iii in strings[2].length:
         print(i+ii+iii)

The issue arises for me when I don't know how long the list of strings is going to be beforehand. If the list is n elements long, then my solution requires n for loops to succeed.

Can any one point me towards a relatively simple solution? I was thinking of a DFS based solution where I turn each letter into a node and creating a connection between all letters in adjacent strings, but this seems like too much effort.

Is this python? It almost looks like python... (except I have no idea what `.length` is doing there) — rici, Mar 22 '17 at 03:15

rici · Answer 1 · 2017-03-22T15:47:16.590

In python, you would use itertools.product

eg.:

>>> for comb in itertools.product("abc", "def", "ghij"):
>>>   print(''.join(comb))
adg
adh
adi
adj
aeg
aeh
...

Or, using an unpack:

>>> words = ["abc", "def", "ghij"]
>>> print('\n'.join(''.join(comb) for comb in itertools.product(*words)))
(same output)

The algorithm used by product is quite simple, as can be seen in its source code (Look particularly at function product_next). It basically enumerates all possible numbers in a mixed base system (where the multiplier for each digit position is the length of the corresponding word). A simple implementation which only works with strings and which does not implement the repeat keyword argument might be:

def product(words):
    if words and all(len(w) for w in words):
        indices = [0] * len(words)
        while True:
            # Change ''.join to tuple for a more accurate implementation
            yield ''.join(w[indices[i]] for i, w in enumerate(words))
            for i in range(len(indices), 0, -1):
                if indices[i - 1] == len(words[i - 1]) - 1:
                    indices[i - 1] = 0
                else:
                    indices[i - 1] += 1
                    break
            else:
                break

Convienient, but I'm not necessarily using Python even though my psuedo-code was very Python-esque. — Jimmy_Rustle, Mar 22 '17 at 04:06
@jimmy: fair enough. It's easy to find implementations of itertools.product; there is one in the very link I provided but I wouldn't actually suggest using it. Here's a better one: http://stackoverflow.com/a/12605800/1566221 — rici, Mar 22 '17 at 08:27

score 1 · Answer 2 · answered Mar 22 '17 at 03:26

From your solution it seems that you need to have as many for loops as there are strings. For each character you generate in the final string, you need a for loop go through the list of possible characters. To do that you can make recursive solution. Every time you go one level deep in the recursion, you just run one for loop. You have as many level of recursion as there are strings.

Here is an example in python:

strings = ["abc", "def", "ghij"]

def rec(generated, k):
    if k==len(strings):
        print(generated)
        return

    for c in strings[k]:
        rec(generated + c, k+1)

rec("", 0)

Anish Goyal · Accepted Answer · 2017-03-22T03:24:11.397

Here's how I would do it in Javascript (I assume that every string contains no duplicate characters):

function getPermutations(arr)
{
  return getPermutationsHelper(arr, 0, "");
}

function getPermutationsHelper(arr, idx, prefix)
{
  var foundInCurrent = [];
  for(var i = 0; i < arr[idx].length; i++)
  {
    var str = prefix + arr[idx].charAt(i);

    if(idx < arr.length - 1)
    {
      foundInCurrent = foundInCurrent.concat(getPermutationsHelper(arr, idx + 1, str));
    }
    else
    {
      foundInCurrent.push(str);
    }
  }
  return foundInCurrent;
}

Basically, I'm using a recursive approach. My base case is when I have no more words left in my array, in which case I simply add prefix + c to my array for every c (character) in my last word.

Otherwise, I try each letter in the current word, and pass the prefix I've constructed on to the next word recursively.

For your example array, I got:

adg adh adi adj aeg aeh aei aej afg afh afi afj bdg bdh bdi 
bdj beg beh bei bej bfg bfh bfi bfj cdg cdh cdi cdj ceg ceh 
cei cej cfg cfh cfi cfj

Algorithm for generating all string combinations

3 Answers3

Related