Subsets and permutations

Some problems ask for every possible choice: every group of items, or every order of them. Recursion builds these one decision at a time, and the calls form a decision tree with one answer at each leaf.

Subsets: take it or skip it

A subset of a list is any selection of its items, from none to all. For each item there are exactly two choices: take it or skip it. A recursive function makes the choice for item i, then calls itself for item i + 1.

Keep the items chosen so far in one list, chosen. A helper go(i) makes the choice for item i. Here is that choice:

chosen.append(items[i])      # take items[i]
go(i + 1)
chosen.pop()                 # undo the choice
go(i + 1)                    # skip items[i]

When i reaches the number of items, every item has been decided: record a copy of chosen and return. Writing the whole function is RECR-P3.

Choose, explore, undo

chosen is one shared list. Every call adds to it before going deeper, and removes the same item after coming back. This pattern is called backtracking:

Two details matter. Record chosen[:], a copy: chosen itself keeps changing, and storing it would store the same list many times. And every append must have a matching pop on every path, or the choices from one branch are still inchosen when the next branch starts.

Orders: pick an unused item

An order of all the items is called a permutation. To build one, fill the first place with any item, the second with any item not yet used, and so on. Keep a record of which items are used. Step through the second version of the figure.

A list used of True and False values records which items are already placed. One call fills the next place: it tries every item that is not used yet, and undoes each try before the next one.

for i in range(len(items)):
    if not used[i]:
        used[i] = True
        chosen.append(items[i])
        go()                  # fill the next place
        chosen.pop()          # undo, in reverse order
        used[i] = False

When chosen holds every item, record a copy of it and return. Writing the whole function is RECR-P4.

How many answers

• Subsets: 2 choices for each of n items, so 2ⁿ subsets (n twos multiplied together).
• Orders: n choices for the first place, n − 1 for the second, and so on, so n! = n × (n − 1) × … × 1, read “n factorial”.
• Choosing k of n items, ignoring order: C(n, k) = n! / (k! (n − k)!). In the subset tree, stop taking items once you have k.

Each answer takes O(n) to copy, so listing all subsets takes time in proportion to n × 2ⁿ, written O(n × 2ⁿ), and all orders O(n × n!). Nothing can do better when you must list them all, because the output itself is that big. From BIGO-3, that means n of about 20 at most for subsets, and about 9 at most for orders.

Now try RECR-P3, Every group of coaches and RECR-P4, Every running order.