Design an algorithm to print all permutations of a string. For simplicity, assume all character are unique.
def perms(s, temp):
"""s is a string,
temp is part of the output found so far."""
if len(s) == 0:
print temp
return
for i in s:
s2 = s.replace(i, '')
temp += i
perms(s2, temp)
temp = temp[:-1]
return
perms('abc', '')
Generalizing the previous example where the characters may not be unique:
output = []
def perms(s, temp):
if len(s) == 0:
output.append(temp)
return
for i in s:
s2 = s.replace(i, '', 1) #replace the first occurance of i in s
temp += i
perms(s2, temp)
temp = temp[:-1]
return
perms('acdc', '')
for i in set(output): #using 'set' to get rid of repititions
print i
The lexicographic permutations of 0, 1 and 2 are: 012 021 102 120 201 210.
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9? (this is problem 24 of project Euler)
remain = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
stack = []
solution_count = 0
flag = False
def prob(stack, remain):
global solution_count, flag
if len(stack) == 10:
solution_count += 1
if solution_count == 1000000:
print stack
flag = True
for i in remain:
remain2 = remain[:]
remain2.remove(i)
stack2 = stack[:]
stack2.append(i)
prob(stack2, remain2)
if flag:
return
prob(stack, remain)
