Finding all possible permutations of a given string in python

Posted on

Question :

Finding all possible permutations of a given string in python

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.

Answered By: machine yearning

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)
Answered By: illerucis

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)

enter image description here

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)
Answered By: grepit

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
Answered By: BushMinusZero

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)
Answered By: ArashkG

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.

Answered By: Rooky

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')]
Answered By: PM 2Ring

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]
Answered By: Vincenzo

Leave a Reply

Your email address will not be published.