Permutations

A permutation is an ordering of items: abc, acb, bac, bca, cab and cba are the six orderings of three letters. Here each level of the decision tree answers another question: which item goes in the next place? Any item that isn't placed yet can go there, so the search keeps a list of used flags, one per item:

def permute(letters, used, path):
    if len(path) == len(letters):
        print("".join(path))
        return
    for i in range(len(letters)):
        if used[i]:
            continue
        used[i] = True                  # choose
        path.append(letters[i])
        permute(letters, used, path)    # explore
        path.pop()                      # un-choose
        used[i] = False


permute("abc", [False, False, False], [])

abc
acb
bac
bca
cab
cba

How it works

• Any letter whose flag is still False may take the next place. So the first place has n candidates, the second n - 1, and the last only one: n × (n - 1) × ... × 1 = n! orderings. That's 6 for 3 letters, 40,320 for 8 and over 6 billion for 13.
• The un-choose undoes both changes the choose made: the letter comes off path, and its flag goes back to False. The next turn of the loop then sees exactly the state the call started with.
• The letters are tried from left to right, so "abc" gives its orderings in alphabetical order. A word whose letters aren't in order, such as "cab", doesn't.
• Each ordering is n items long, so listing them all takes O(n · n!) time. The calls are only n + 1 deep.

Leave out the last line, used[i] = False, and the same program prints just one line, abc. The first path marks a, b and c as used, and nothing ever marks them free again, so every later loop finds all three used and skips them. When a backtracking search finds too few answers, check that every change made before the recursive call is undone after it.

Swapping instead of flags

Another classic way needs no flags: it moves the items around in the list itself. To fill place i, swap each of the items from place i on into place i, permute the rest from i + 1, then swap back:

def permute_swap(items, i):
    if i == len(items):
        print("".join(items))
        return
    for j in range(i, len(items)):
        items[i], items[j] = items[j], items[i]    # choose: items[j] goes to place i
        permute_swap(items, i + 1)
        items[i], items[j] = items[j], items[i]    # un-choose: swap back


permute_swap(list("abc"), 0)

abc
acb
bac
bca
cba
cab

The same six orderings, in a slightly different order: cba comes before cab, because the swap that moved c to the front put a at the back.

itertools.permutations

In real code, use the standard library. permutations gives tuples, in the same order as the flag version, and a second argument asks for orderings of only some of the items:

>>> from itertools import permutations
>>> list(permutations("abc", 2))
[('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b')]
>>> len(list(permutations(range(8))))
40320
>>> ["".join(p) for p in permutations("pop")]
['pop', 'ppo', 'opp', 'opp', 'ppo', 'pop']

Interviews still ask you to write the search yourself, and your own search can do what permutations can't: skip choices.

Repeated letters

permutations("pop") gives 6 orderings but only 3 different strings: to it, the two p's are different items. set() removes the repeats, but only after making all n! orderings. For "aaaaaaabbbbbbb", 14 letters, that's over 87 billion orderings (hours of work) for 3,432 different strings.

A better search never makes the repeats at all. Instead of asking "which position of the word goes next?", it asks "which letter goes next?", and it keeps a count of each letter that's left: {"o": 1, "p": 2} for "pop". The next place may take any letter whose count is above 0. Taking a letter lowers its count, the recursive call fills the places after it, and putting the letter back raises the count again. Both p's are now one option, "p", so each different string comes out exactly once, and no time goes into strings that would be thrown away.