Skip to content
Tutorials Center
My learning

Topics

Lesson 3 of 36 ยท Getting Started

Counting by Brute Force with Python

Use itertools to enumerate products, permutations, combinations and subsets, and learn when brute force is a trustworthy checker for your counting formulas.

Formulas are fast, but they are easy to get wrong. A brute-force program that generates every object and counts them is slow, but it is almost always correct. The professional habit is to use both: derive the formula, then compare it with brute force on small inputs. If they agree for n = 1 to 8, you can trust the formula for n = 1000.

Python's itertools module provides the four generators you need. This lesson shows each one and the matching count.

The four generators

Generator Produces Count (n items, pick k)
product(A, repeat=k) ordered, repeats allowed n^k
permutations(A, k) ordered, no repeats n! / (n-k)!
combinations(A, k) unordered, no repeats n! / (k!(n-k)!)
combinations_with_replacement(A, k) unordered, repeats allowed (n+k-1)! / (k!(n-1)!)

Those four cells are the whole story of "choosing k from n"; the next chapters derive each formula. Here you only need to see them produce objects.

Python The four ways of choosing 2 from {a, b, c}

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see counts 9, 6, 3 and 6. Make sure you can explain each by hand after the next two chapters.

Counting with a condition

Real problems add a restriction. The brute-force pattern is always the same: generate everything, filter with a condition, count what survives.

Example: how many 3-digit strings over the digits 0-9 have digit sum 10?

Python Counting with a filter

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second result is 24. You can predict it: 3 choices for the first letter, then 2 for each next letter (anything but its predecessor). That is the product rule in action.

Subsets of a set

Brute-forcing all subsets means choosing, for each element, "in" or "out". Python can generate them with combinations for each size k, or with a bit-mask loop. The bit-mask form is worth learning: the number m from 0 to 2^n - 1 encodes one subset, where bit i says whether element i is included.

Python All subsets by bit mask

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sizes 1, 4, 6, 4, 1 add to 16 = 2^4. That row of numbers is a row of Pascal's triangle, which you will meet in Pascal and the Binomial Theorem.

A small test harness

When you verify a formula, write a tiny function that compares the formula to brute force over a range of inputs. If any input disagrees, print it. This turns "I think it is right" into evidence.

Python Checking a formula against brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Limits of brute force

Brute force breaks when the number of objects reaches billions. A 12-element permutation already has 479,001,600 outcomes, and 20 elements has more than 2 x 10^18. Use brute force only on small sizes: its job is to validate your reasoning, not replace it.

Do not trust a brute-force program blindly either. Off-by-one errors in range and mistakes in the filter condition can fake an agreement. Test on cases where you already know the answer, such as sizes 0, 1 and 2.

flowchart LR
    P["Problem"] --> F["Derive a formula"]
    P --> B["Write brute force"]
    F --> C{"Same answer<br/>for small n?"}
    B --> C
    C -->|yes| T["Trust the formula"]
    C -->|no| D["Debug both"]

Two independent routes to the same number give you confidence.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which itertools function lists ordered selections without repeats?

    permutations(A, k) gives ordered arrangements of k distinct items.
  2. 2. How many items does list(product('01', repeat=5)) contain?

    2 choices for each of 5 positions: 2^5 = 32.
  3. 3. What is the main role of brute force in this course?

    It is a slow but reliable checker that exposes mistakes in reasoning.
  4. 4. How many subsets does a 5-element set have?

    Each element is in or out, giving 2^5 = 32.

Summary

  • product, permutations, combinations and combinations_with_replacement cover the four ways of choosing.
  • Count with a condition by generating, filtering and counting.
  • Bit masks encode subsets: n elements give 2^n masks.
  • Compare formulas with brute force on small inputs, never on huge ones.

Next: Bijections and Double Counting