Skip to content

Instantly share code, notes, and snippets.

@tahia-khan tahia-khan/permutations.py
Last active May 28, 2016

Embed
What would you like to do?
from collections import deque
def permutations(word):
if len(word) == 1:
return [word]
perms = permutations(word[1:])
c = word[0]
res = []
L = len(perms[0]) + 1
for perm in perms:
for i in range(L):
res.append(perm[:i] + c + perm[i:])
return res
def permutations_iter(word):
if len(word) == 1:
return [word]
stack = deque(word)
res = [stack.pop()]
while stack:
c = stack.pop()
next_res = []
L = len(res[0]) + 1
for r in res:
for i in range(L):
next_res.append(r[:i] + c + r[i:])
res = next_res
return res
def permutations_all_k(word, k):
letters = list(word)
res = [""]
while len(res[0]) != k:
next_res = []
for prefix in res:
for c in letters:
next_res.append(prefix + c)
res = next_res
return res
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.