First, let us have a look at few sample strings and their permutations.
Input String: 'ab'
Permutations: 'ab', 'ba'
Input String: 'abc'
Permutations: 'abc', 'acb', 'bac', 'bca', 'cab', 'cba'
Input String: 'abcd'
Permutations: a + all permutations of 'bcd', b + all permutations of 'acd', c + all permutations of 'abd', d + all permutations of 'abc'
As soon as we reached a 4 characters string the permutations become unwieldy and is becoming a challenge to compute mentally. However, if we recall from our math class, we know that we can have a maximum of 4! (factorial) permutations with a 4 characters string equaling 24 different variations.
But this simple analysis has given out the solution for us. If you look closely you will notice that for a string with 4 characters, we were computing permutations by combining each character from the 4 characters string with the result of all possible permutations of the remaining string with 3 characters. Similarly for the string with 3 characters we can compute the permutations by combining each characters of the 3 characters string with the result of all possible permutations of the remaining string with 2 characters and so on.
permutation ('abcd') = a + permutation('bcd') and so on
permutation('bcd') = b + permutation('cd') and so on
permutation('cd') = c + permutation('b') and so on
permutation('b) = b (Since there is nothing to permute with just one character)
The above flow lends itself elegantly to a recursive solution. I have specified the pseudo code below.
permutation(string) { myList = empty if string.length == 1 Add string to myList else for each char in string for each permutation(string-char) Add char + permutation to myList return myList }
Note the recursive call to "permutation" inside the function. Find below the implementation in Python.
def permute(instr): myList = list() if len(instr) == 1: myList.append(instr) else: for inchar in instr: for perm in permute(redux(instr, inchar)): myList.append(inchar + perm) return myList
def redux(instr, inchar): outstr = '' for c in instr: if c != inchar: outstr += c return outstr
I am a newbie to Python. Therefore, you may find code above that may not be the norm among pycoders.
Also, be warned, the above implementation & logic works only for string with distinct characters. If you have repetitive characters, the above logic will produce erroneous results.
you may take a look at itertools
ReplyDelete