Search for all possible permutations of a given string in python

Question

I have a line. I want to generate all permutations from this line 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 repeat the list of lines, select 2 letters in random order and transfer them to a new line and add them for a set of litas. Based on the length of the string, I calculate the number of possible permutations and ongoing iterations until the 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])

Returns consecutive permutations of r elements in an iterable.

If r is not specified or None, then r is the default - length and all possible complete permutations are repeated.

Permutations are sent in lexicographic sort order. So, if the input is iterable is sorted, permutation tuples will be created in sorted order.

However, you will have to join your permutation letters as strings.

 >>> 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 "," cast "," 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 "," kat sc "," katcs "," kacst "," kacts "," kcsta "," kcsat "," kctsa "," kctas "," kcast ", 'Kcats']

If you have problems with duplicates, try to fine-tune your data in the structure without duplicates, such as set :

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

Thanks to @pst, pointing out that this is not what we traditionally thought of as a type, but call the set() constructor more.

Answer 2

You can get all N! permutations without big 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 index will begin with step + 1) permutations(string_copy, step + 1) 

Answer 3

Users have already posted some powerful solutions, but I wanted to show another solution. I find this one more intuitive

The idea is that for a given line: we can recursively execute an algorithm (pseudo-code):

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

Hope this 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, ""))] return permutation_list 

Answer 4

Here's another approach different from what @Adriano and @illerucis posted. It has a better lead time, you can check it 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 the arbitrary string "dadffddxcf", the permutation library took 1.1336 s, for this implementation it took 9.125 seconds, and for the versions @Adriano and @illerucis it took 16.357 sec. Of course, you can still optimize it.

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

itertools.permutations is good, but it has nothing to do with sequences that contain repeating elements. This is because internally it rearranges the indices of the sequence and does not pay attention to the values ​​of the elements of the sequence.

Of course, it is possible to filter the output of itertools.permutations through the set to eliminate duplicates, but it still takes time to create these duplicates, and if there are several duplicate elements in the base sequence, there will be many duplicates. In addition, using the collection to store the results takes away RAM, which negates the advantage of using an iterator in the first place.

Fortunately, there are more effective approaches. The code below uses the 14th-century Indian mathematician Narayan Pandita algorithm, which can be found in the Wikipedia article on permutation . This ancient algorithm is still one of the fastest ways to generate permutations in order, and is robust enough because it handles permutations that contain repeating elements correctly.

 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) 

Exit

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

Of course, if you want to collect the received rows into a list, you can do

 list(lexico_permute_string('data')) 

or in recent versions of Python:

 [*lexico_permute_string('data')] 

Answer 7

Here is another way to do a line swap with minimal code. We basically create a loop, and then continue to change two characters at a time. Inside the loop we will have recursion. Please note that we only print when indexers reach the length of our string. Example: ABC i for our starting point and our recursion parameter j for our loop

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

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 8

why don't you just 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 do not get duplicates, 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] 

Answer 9

See itertools.combinations or itertools.permutations .

Answer 10

Here's a slightly improved version of the illerucis code to return a list of all permutations of a string s with different characters (not necessarily in lexicographic sort order), without using itertools:

 def get_perms(s, i=0): """ Returns a list of all (len(s) - i)! permutations t of s where t[:i] = s[:i]. """ # To avoid memory allocations for intermediate strings, use a list of chars. if isinstance(s, str): s = list(s) # Base Case: 0! = 1! = 1. # Store the only permutation as an immutable string, not a mutable list. if i >= len(s) - 1: return ["".join(s)] # Inductive Step: (len(s) - i)! = (len(s) - i) * (len(s) - i - 1)! # Swap in each suffix character to be at the beginning of the suffix. perms = get_perms(s, i + 1) for j in range(i + 1, len(s)): s[i], s[j] = s[j], s[i] perms.extend(get_perms(s, i + 1)) s[i], s[j] = s[j], s[i] return perms 

Answer 11

 def permute(seq): if not seq: yield seq else: for i in range(len(seq)): rest = seq[:i]+seq[i+1:] for x in permute(rest): yield seq[i:i+1]+x print(list(permute('stack'))) 

Answer 12

Here's a really simple version of the generator:

 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 this is not so bad!

Answer 13

 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 14

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

Answer 15

 def perm(string): res=[] for j in range(0,len(string)): if(len(string)>1): for i in perm(string[1:]): res.append(string[0]+i) else: return [string]; string=string[1:]+string[0]; return res; l=set(perm("abcde")) 

This is one way to generate permutations with recursion, you can easily understand the code by entering the lines "a", "ab" and "abc" as input.

You get all N! permutations with this, without duplicates.

Answer 16

Everyone loves the smell of their own code. Just sharing what I find the easiest:

 def get_permutations(word): if len(word) == 1: yield word for i, letter in enumerate(word): for perm in get_permutations(word[:i] + word[i+1:]): yield letter + perm 

Answer 17

This program does not eliminate duplicates, but I think this is one of the most effective approaches:

 s=raw_input("Enter a string: ") print "Permutations :\n",s size=len(s) lis=list(range(0,size)) while(True): k=-1 while(k>-size and lis[k-1]>lis[k]): k-=1 if k>-size: p=sorted(lis[k-1:]) e=p[p.index(lis[k-1])+1] lis.insert(k-1,'A') lis.remove(e) lis[lis.index('A')]=e lis[k:]=sorted(lis[k:]) list2=[] for k in lis: list2.append(s[k]) print "".join(list2) else: break 

Answer 18

 def permute_all_chars(list, begin, end): if (begin == end): print(list) return for current_position in range(begin, end + 1): list[begin], list[current_position] = list[current_position], list[begin] permute_all_chars(list, begin + 1, end) list[begin], list[current_position] = list[current_position], list[begin] given_str = 'ABC' list = [] for char in given_str: list.append(char) permute_all_chars(list, 0, len(list) -1) 

Answer 19

A simpler solution using permutations.

 from itertools import permutations def stringPermutate(s1): length=len(s1) if length < 2: return s1 perm = [''.join(p) for p in permutations(s1)] return set(perm) 

Answer 20

Here's a simple and simple recursive implementation;

 def stringPermutations(s): if len(s) < 2: yield s return for pos in range(0, len(s)): char = s[pos] permForRemaining = list(stringPermutations(s[0:pos] + s[pos+1:])) for perm in permForRemaining: yield char + perm