Set Cover Problem Generator

What this generator does

Builds a collection of sets over a universe of items, guaranteeing every item appears somewhere so the problem is always solvable. It runs the greedy rule, then searches every combination by increasing size to find the genuine minimum, and confirms the greedy selection really does cover everything.

How to use this tool

1. Choose how many items need covering and how many sets are available.
2. Try to find the smallest covering selection yourself.
3. Generate, and compare your answer with both the greedy and the exhaustive one.
4. Run it several times — greedy matches the minimum often, but not always.

Understanding the controls

How many things to cover

Between 4 and 12 items in the universe. Every one is guaranteed to appear in at least one set, so a cover always exists.

How many available sets

Between 3 and 10 to choose from. More sets give greedy more chances to go wrong and make the exhaustive search slower.

Seed

Any word reproduces the same sets and the same answers.

Common use cases

• Teaching greedy approximation and what it costs against the optimum
• Coverage planning problems — shifts, skills, test cases, sensor placement
• Test instances for a set-cover implementation
• Showing what NP-hard means in a problem small enough to see whole
• Setting a reproducible exercise from a seed

How this generator works

Greedy takes the set adding the most newly covered items each round and stops when nothing is left uncovered. The exhaustive search represents each set as a bit mask and tries every combination of size one, then two, and so on, stopping at the first size that covers everything — which is by construction the minimum. The checker confirms the greedy answer covers the universe and never uses fewer sets than that minimum.

Randomness and fairness

The sets are random; both the greedy and exhaustive answers are computed from them. A seed reproduces the problem exactly and is therefore explicitly not cryptographically secure. Without a seed the browser's cryptographically secure generator is used.

For how randomness is produced across the whole site, see how Generate Random works.

Limitations and good to know

• Unweighted — every set costs the same, whereas weighted set cover is a harder and more realistic variant.
• Exhaustive search is capped at eighteen sets, above which the minimum is reported as unconfirmed.
• Sets are generated at random rather than from a real domain, so the instances have no particular structure.
• Ties are broken by index, so a different but equally small cover may exist.
• Nothing about an instance is saved; note the seed before closing the page.

Privacy and your data

The sets and both searches run entirely in your browser. Nothing about the problem or your seed is transmitted or kept.