TwiddleLab / Code / Recursion: Functions That Call Themselves
Generate Everything: Subsets and Orders
What you will learn
- Brute force: list every possibility and check each one.
- Subsets: each call decides about one item, take it or skip it, and trusts itself with the rest. n items give 2^n subsets.
- Orders: each call picks the next item from those left. n items give n! orders, which grows even faster.
- 10 songs already have 3 628 800 orders, so listing everything soon becomes too slow.
How the lesson goes
Five pizza toppings. How many different pizzas can you order?
Any mix of them, including the plain pizza with none.
One decision at a time: take it or skip it.
Grow the tree for 3 toppings, then add toppings until you reach 5.
Every pizza from the smaller menu appears twice in the bigger one: once with the new topping and once without. So each topping doubles the count.
Missing pizza: one is not on the menu. Find it.
Build it with the topping buttons and Order. Two rounds, against the clock.
Brute force, subsets and orders.
Brute force means generating every possibility and checking each. Recursion makes the list easy.
Subsets: a call decides about the first item, take or skip, and calls itself on the rest. Base case: no items left, print what you chose. 2^n results.
Orders: a call picks which item comes next, for each item left, and calls itself on the rest. n x (n - 1) x ... x 1 = n! results.
Write subsets(items, chosen).
Base case: no items left, print the chosen ones. Otherwise: once with the first item, once without.
Each call removes one item, so items shrinks to empty and the base case is reached. Calling twice, once with the item added and once without, makes the take-or-skip tree.
Your pizzeria: pick 4 toppings and list every pizza.
Your subsets runs on your toppings.
Now the order matters: 3 songs on a playlist.
Each level picks the next song from the ones left. Grow the tree.
Subsets against orders. When do orders pass a million?
Slide n and find the first playlist size with more than 1 000 000 orders, then Check.
2^n multiplies by 2 each step; n! multiplies by n, which keeps getting bigger. 9! = 362 880 and 10! = 3 628 800.
Which pizza does your code print first?
These are all the pizzas from your toppings, shuffled. Tap one, then Check.
subsets(items[1:], chosen + [items[0]]) runs before subsets(items[1:], chosen), at every level. So the first path down is take every time, and the first print is the full pizza.
Previous lesson: Divide and Conquer · Next lesson: Backtracking: Solving a Maze · Part of the course: Recursion: Functions That Call Themselves
Lessons are interactive and need JavaScript. Turn it on to play them.
