Finding all possible permutations of a given strin

Question

I have a string. I want to generate all permutations from that string, by changing the order of characters in it. For example, say:

x='stack'

what I want is a list like this,

l=['stack','satck','sackt'.......]

Currently I am iterating on the list cast of the string, picking 2 letters randomly and transposing them to form a new string, and adding it to set cast of l. Based on the length of the string, I am calculating the number of permutations possible and continuing iterations till set size reaches the limit. There must be a better way to do this.

Answer 1

See itertools.combinations or itertools.permutations.

Answer 2

Here's a simple function to return unique permutations:

def permutations(string):
    if len(string) == 1:
        return string

    recursive_perms = []
    for c in string:
        for perm in permutations(string.replace(c,'',1)):
            revursive_perms.append(c+perm)

    return set(revursive_perms)

Answer 3

Here's a really simple generator version:

def find_all_permutations(s, curr=[]):
    if len(s) == 0:
        yield curr
    else:
        for i, c in enumerate(s):
            for combo in find_all_permutations(s[:i]+s[i+1:], curr + [c]):
                yield "".join(combo)

I think it's not so bad!

Answer 4

Here is another way of doing the permutation of string with minimal code. We basically create a loop and then we keep swapping two characters at a time, Inside the loop we'll have the recursion. Notice,we only print when indexers reaches the length of our string. Example: ABC i for our starting point and our recursion param j for our loop

here is a visual help how it works from left to right top to bottom (is the order of permutation)

the code :

def permute(data, i, length): 
    if i==length: 
        print(''.join(data) )
    else: 
        for j in range(i,length): 
            #swap
            data[i], data[j] = data[j], data[i] 
            permute(data, i+1, length) 
            data[i], data[j] = data[j], data[i]  


string = "ABC"
n = len(string) 
data = list(string) 
permute(data, 0, n)

Answer 5

def f(s):
  if len(s) == 2:
    X = [s, (s[1] + s[0])]
      return X
else:
    list1 = []
    for i in range(0, len(s)):
        Y = f(s[0:i] + s[i+1: len(s)])
        for j in Y:
            list1.append(s[i] + j)
    return list1
s = raw_input()
z = f(s)
print z

Answer 6

Here is another approach different from what @Adriano and @illerucis posted. This has a better runtime, you can check that yourself by measuring the time:

def removeCharFromStr(str, index):
    endIndex = index if index == len(str) else index + 1
    return str[:index] + str[endIndex:]

# 'ab' -> a + 'b', b + 'a'
# 'abc' ->  a + bc, b + ac, c + ab
#           a + cb, b + ca, c + ba
def perm(str):
    if len(str) <= 1:
        return {str}
    permSet = set()
    for i, c in enumerate(str):
        newStr = removeCharFromStr(str, i)
        retSet = perm(newStr)
        for elem in retSet:
            permSet.add(c + elem)
    return permSet

For an arbitrary string "dadffddxcf" it took 1.1336 sec for the permutation library, 9.125 sec for this implementation and 16.357 secs for @Adriano's and @illerucis' version. Of course you can still optimize it.