Generate list of all possible permutations of a string

UnkwnTech picture UnkwnTech · Aug 2, 2008 · Viewed 204.7k times · Source

How would I go about generating a list of all possible permutations of a string between x and y characters in length, containing a variable list of characters.

Any language would work, but it should be portable.

Answer

alumb picture alumb · Aug 2, 2008

There are several ways to do this. Common methods use recursion, memoization, or dynamic programming. The basic idea is that you produce a list of all strings of length 1, then in each iteration, for all strings produced in the last iteration, add that string concatenated with each character in the string individually. (the variable index in the code below keeps track of the start of the last and the next iteration)

Some pseudocode:

list = originalString.split('')
index = (0,0)
list = [""]
for iteration n in 1 to y:
  index = (index[1], len(list))
  for string s in list.subset(index[0] to end):
    for character c in originalString:
      list.add(s + c)

you'd then need to remove all strings less than x in length, they'll be the first (x-1) * len(originalString) entries in the list.