Card 07/ 09
Counting Combinations vs Counting Orderings
Coins outside and amounts inside counts each set of coins once; amounts outside counts every order.
Counting the ways to make an amount from coins gives two different answers depending only on which loop is outside: coins outside counts each set of coins once, and amounts outside counts every order of the same coins separately. This card compares the two on one amount and gives the rule for choosing.
The common ground is everything but the loops. Both keep ways[a], the number of ways to make amount a, start from ways[0] = 1, the one way to make nothing, and add ways[a − coin] into ways[a]. Both take O(amount × coins) time and O(amount) space. The listing below runs both on coins of 1, 2 and 5 for amounts up to 5.
coins = [1, 2, 5]
amount = 5
combinations = [1] + [0] * amount
for coin in coins:
for a in range(coin, amount + 1):
combinations[a] += combinations[a - coin]
orderings = [1] + [0] * amount
for a in range(1, amount + 1):
for coin in coins:
if coin <= a:
orderings[a] += orderings[a - coin]
print(f"coins outside: {combinations}")
print(f"amounts outside: {orderings}")coins outside: [1, 1, 2, 2, 3, 4]
amounts outside: [1, 1, 2, 3, 5, 9]The table sets the two printed arrays side by side, one row per amount.
| Amount | Coins outside: sets | Amounts outside: orders |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 1 | 1 |
| 2 | 2 | 2 |
| 3 | 2 | 3 |
| 4 | 3 | 5 |
| 5 | 4 | 9 |
The two agree up to 2 and part at 3, where 1 + 2 and 2 + 1 are one set but two orders. For 5 a run listed the four sets, 1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 2, 1 + 2 + 2 and 5, and counted nine orders.
The reason is what each loop lets the count see. With coins outside, all the ways using only 1s are counted before any 2 is considered, and a 2 can only be added after them, so every set is built in one fixed order of coins and counted once. With amounts outside, every amount tries every coin as its last coin, so 1 + 2 and 2 + 1 arrive by different last coins and are counted apart.
The rule: decide whether the question's "ways" cares about order. Change made from coins, items chosen for a basket, or numbers that add to a total are sets, so put the coins or items outside. Steps climbed one or two at a time, sequences of moves, or codes typed digit by digit are orders, so put the amounts outside. Check on an amount of 3, where the two answers first differ.
← → move through sections and cards