### 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:

The itertools module has a useful method called permutations(). The documentation says:

itertools.permutations(iterable[, r])Return successive r length permutations of elements in the iterable.

If r is not specified or is None, then r defaults to the length of the

iterable and all possible full-length permutations are generated.Permutations are emitted in lexicographic sort order. So, if the input

iterable is sorted, the permutation tuples will be produced in sorted

order.

You’ll have to join your permuted letters as strings though.

```
>>> from itertools import permutations
>>> perms = [''.join(p) for p in permutations('stack')]
>>> perms
```

[‘stack’, ‘stakc’, ‘stcak’, ‘stcka’, ‘stkac’, ‘stkca’, ‘satck’,

‘satkc’, ‘sactk’, ‘sackt’, ‘saktc’, ‘sakct’, ‘sctak’, ‘sctka’,

‘scatk’, ‘scakt’, ‘sckta’, ‘sckat’, ‘sktac’, ‘sktca’, ‘skatc’,

‘skact’, ‘skcta’, ‘skcat’, ‘tsack’, ‘tsakc’, ‘tscak’, ‘tscka’,

‘tskac’, ‘tskca’, ‘tasck’, ‘taskc’, ‘tacsk’, ‘tacks’, ‘taksc’,

‘takcs’, ‘tcsak’, ‘tcska’, ‘tcask’, ‘tcaks’, ‘tcksa’, ‘tckas’,

‘tksac’, ‘tksca’, ‘tkasc’, ‘tkacs’, ‘tkcsa’, ‘tkcas’, ‘astck’,

‘astkc’, ‘asctk’, ‘asckt’, ‘asktc’, ‘askct’, ‘atsck’, ‘atskc’,

‘atcsk’, ‘atcks’, ‘atksc’, ‘atkcs’, ‘acstk’, ‘acskt’, ‘actsk’,

‘actks’, ‘ackst’, ‘ackts’, ‘akstc’, ‘aksct’, ‘aktsc’, ‘aktcs’,

‘akcst’, ‘akcts’, ‘cstak’, ‘cstka’, ‘csatk’, ‘csakt’, ‘cskta’,

‘cskat’, ‘ctsak’, ‘ctska’, ‘ctask’, ‘ctaks’, ‘ctksa’, ‘ctkas’,

‘castk’, ‘caskt’, ‘catsk’, ‘catks’, ‘cakst’, ‘cakts’, ‘cksta’,

‘cksat’, ‘cktsa’, ‘cktas’, ‘ckast’, ‘ckats’, ‘kstac’, ‘kstca’,

‘ksatc’, ‘ksact’, ‘kscta’, ‘kscat’, ‘ktsac’, ‘ktsca’, ‘ktasc’,

‘ktacs’, ‘ktcsa’, ‘ktcas’, ‘kastc’, ‘kasct’, ‘katsc’, ‘katcs’,

‘kacst’, ‘kacts’, ‘kcsta’, ‘kcsat’, ‘kctsa’, ‘kctas’, ‘kcast’,

‘kcats’]

If you find yourself troubled by duplicates, try fitting your data into a structure with no duplicates like a `set`

:

```
>>> perms = [''.join(p) for p in permutations('stacks')]
>>> len(perms)
720
>>> len(set(perms))
360
```

Thanks to @pst for pointing out that this is not what we’d traditionally think of as a type cast, but more of a call to the `set()`

constructor.

##
Answer #2:

You can get all N! permutations without much code

```
def permutations(string, step = 0):
# if we've gotten to the end, print the permutation
if step == len(string):
print "".join(string)
# everything to the right of step has not been swapped yet
for i in range(step, len(string)):
# copy the string (store as array)
string_copy = [character for character in string]
# swap the current index with the step
string_copy[step], string_copy[i] = string_copy[i], string_copy[step]
# recurse on the portion of the string that has not been swapped yet (now it's index will begin with step + 1)
permutations(string_copy, step + 1)
```

##
Answer #3:

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 #4:

Stack Overflow users have already posted some strong solutions but I wanted to show yet another solution. This one I find to be more intuitive

The idea is that for a given string: we can recurse by the algorithm (pseudo-code):

permutations = char + permutations(string – char) for char in string

I hope it helps someone!

```
def permutations(string):
"""
Create all permutations of a string with non-repeating characters
"""
permutation_list = []
if len(string) == 1:
return [string]
else:
for char in string:
[permutation_list.append(char + a) for a in permutations(string.replace(char, "", 1))]
return permutation_list
```

##
Answer #5:

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

##
Answer #7:

`itertools.permutations`

is good, but it doesn’t deal nicely with sequences that contain repeated elements. That’s because internally it permutes the sequence indices and is oblivious to the sequence item values.

Sure, it’s possible to filter the output of `itertools.permutations`

through a set to eliminate the duplicates, but it still wastes time generating those duplicates, and if there are several repeated elements in the base sequence there will be *lots* of duplicates. Also, using a collection to hold the results wastes RAM, negating the benefit of using an iterator in the first place.

Fortunately, there are more efficient approaches. The code below uses the algorithm of the 14th century Indian mathematician Narayana Pandita, which can be found in the Wikipedia article on Permutation. This ancient algorithm is still one of the fastest known ways to generate permutations in order, and it is quite robust, in that it properly handles permutations that contain repeated elements.

```
def lexico_permute_string(s):
''' Generate all permutations in lexicographic order of string `s`
This algorithm, due to Narayana Pandita, is from
https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
To produce the next permutation in lexicographic order of sequence `a`
1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists,
the permutation is the last permutation.
2. Find the largest index k greater than j such that a[j] < a[k].
3. Swap the value of a[j] with that of a[k].
4. Reverse the sequence from a[j + 1] up to and including the final element a[n].
'''
a = sorted(s)
n = len(a) - 1
while True:
yield ''.join(a)
#1. Find the largest index j such that a[j] < a[j + 1]
for j in range(n-1, -1, -1):
if a[j] < a[j + 1]:
break
else:
return
#2. Find the largest index k greater than j such that a[j] < a[k]
v = a[j]
for k in range(n, j, -1):
if v < a[k]:
break
#3. Swap the value of a[j] with that of a[k].
a[j], a[k] = a[k], a[j]
#4. Reverse the tail of the sequence
a[j+1:] = a[j+1:][::-1]
for s in lexico_permute_string('data'):
print(s)
```

**output**

```
aadt
aatd
adat
adta
atad
atda
daat
data
dtaa
taad
tada
tdaa
```

Of course, if you want to collect the yielded strings into a list you can do

```
list(lexico_permute_string('data'))
```

or in recent Python versions:

```
[*lexico_permute_string('data')]
```

##
Answer #8:

why do you not simple do:

```
from itertools import permutations
perms = [''.join(p) for p in permutations(['s','t','a','c','k'])]
print perms
print len(perms)
print len(set(perms))
```

you get no duplicate as you can see :

```
['stack', 'stakc', 'stcak', 'stcka', 'stkac', 'stkca', 'satck', 'satkc',
'sactk', 'sackt', 'saktc', 'sakct', 'sctak', 'sctka', 'scatk', 'scakt', 'sckta',
'sckat', 'sktac', 'sktca', 'skatc', 'skact', 'skcta', 'skcat', 'tsack',
'tsakc', 'tscak', 'tscka', 'tskac', 'tskca', 'tasck', 'taskc', 'tacsk', 'tacks',
'taksc', 'takcs', 'tcsak', 'tcska', 'tcask', 'tcaks', 'tcksa', 'tckas', 'tksac',
'tksca', 'tkasc', 'tkacs', 'tkcsa', 'tkcas', 'astck', 'astkc', 'asctk', 'asckt',
'asktc', 'askct', 'atsck', 'atskc', 'atcsk', 'atcks', 'atksc', 'atkcs', 'acstk',
'acskt', 'actsk', 'actks', 'ackst', 'ackts', 'akstc', 'aksct', 'aktsc', 'aktcs',
'akcst', 'akcts', 'cstak', 'cstka', 'csatk', 'csakt', 'cskta', 'cskat', 'ctsak',
'ctska', 'ctask', 'ctaks', 'ctksa', 'ctkas', 'castk', 'caskt', 'catsk', 'catks',
'cakst', 'cakts', 'cksta', 'cksat', 'cktsa', 'cktas', 'ckast', 'ckats', 'kstac',
'kstca', 'ksatc', 'ksact', 'kscta', 'kscat', 'ktsac', 'ktsca', 'ktasc', 'ktacs',
'ktcsa', 'ktcas', 'kastc', 'kasct', 'katsc', 'katcs', 'kacst', 'kacts', 'kcsta',
'kcsat', 'kctsa', 'kctas', 'kcast', 'kcats']
120
120
[Finished in 0.3s]
```