A dependency-free PHP package that answers: “how many complete sets can I build from a pool of quantities, which items go into them, and what is left over?” Cart promotions, gift boxes, assembly lines, shift rosters — same question, same three lines of code.
Collection items implement the small Subsetable interface. Property names are up to you; the solver only talks to the interface.
use Ozdemir\SubsetFinder\Subsetable;
class Item implements Subsetable
{
public function __construct(
public readonly int $id,
public readonly string $name,
public int $quantity,
public readonly float $price,
) {
}
public function getId(): int
{
return $this->id;
}
public function getQuantity(): int
{
return $this->quantity;
}
public function setQuantity(int $quantity): void
{
$this->quantity = $quantity;
}
}How many times does “any 5 drinks + any 2 snacks” apply to this cart — and which items does it capture?
The classic cart-discount problem. The promo set is flexible (“any of these”), so the solver picks which units fall under the promo — cheapest first, thanks to sortField: 'price' — and tells you exactly what stays at full price.
use Ozdemir\SubsetFinder\Subset;
use Ozdemir\SubsetFinder\SubsetCollection;
use Ozdemir\SubsetFinder\SubsetFinder;
use Ozdemir\SubsetFinder\SubsetFinderConfig;
$cart = [
new Item(1, 'Latte', quantity: 7, price: 4.50),
new Item(2, 'Espresso', quantity: 4, price: 3.00),
new Item(3, 'Croissant', quantity: 5, price: 3.75),
new Item(4, 'Brownie', quantity: 3, price: 4.25),
];
$promo = new SubsetCollection([
Subset::of([1, 2])->take(5), // any 5 drinks
Subset::of([3, 4])->take(2), // any 2 snacks
]);
$finder = new SubsetFinder($cart, $promo, new SubsetFinderConfig(sortField: 'price'));
$finder->solve();
printf("Promo applies %d times.\n\n", $finder->getSubsetQuantity());
echo "Discounted (cheapest first):\n";
foreach ($finder->getFoundSubsets() as $item) {
printf(" %-9s x%d\n", $item->name, $item->quantity);
}
echo "\nFull price:\n";
foreach ($finder->getRemaining() as $item) {
printf(" %-9s x%d\n", $item->name, $item->quantity);
}Promo applies 2 times. Discounted (cheapest first): Espresso x4 Latte x6 Croissant x4 Full price: Latte x1 Croissant x1 Brownie x3
How many complete gift boxes can we assemble from current stock — and which ingredient runs out first?
A box needs 2 candles, 3 soaps and a card — any variant of each. The answer tells you how many boxes to promise; the leftovers tell you what to restock (here the cards are the bottleneck, not the soaps).
use Ozdemir\SubsetFinder\Subset;
use Ozdemir\SubsetFinder\SubsetCollection;
use Ozdemir\SubsetFinder\SubsetFinder;
$stock = [
new Item(1, 'Vanilla Candle', quantity: 40, price: 12.00),
new Item(2, 'Pine Candle', quantity: 25, price: 14.00),
new Item(3, 'Lavender Soap', quantity: 80, price: 6.50),
new Item(4, 'Honey Soap', quantity: 60, price: 7.00),
new Item(5, 'Greeting Card', quantity: 30, price: 2.50),
];
$giftBox = new SubsetCollection([
Subset::of([1, 2])->take(2), // 2 candles, either scent
Subset::of([3, 4])->take(3), // 3 soaps, either kind
Subset::of([5])->take(1), // 1 card
]);
$finder = new SubsetFinder($stock, $giftBox);
$finder->solve();
printf("Complete gift boxes: %d\n\n", $finder->getSubsetQuantity());
echo "Still on the shelf:\n";
foreach ($finder->getRemaining() as $item) {
printf(" %-15s %3d left\n", $item->name, $item->quantity);
}
echo "\n=> Greeting cards are the bottleneck - restock those first.\n";Complete gift boxes: 30 Still on the shelf: Pine Candle 5 left Honey Soap 50 left => Greeting cards are the bottleneck - restock those first.
How many desks can we build when several parts are interchangeable?
A desk needs 4 legs, a top and 8 screws — but oak or steel legs both work, and either screw type fits. Classic BOM math breaks down with substitutable parts; here each requirement is simply a subset over the alternatives.
use Ozdemir\SubsetFinder\Subset;
use Ozdemir\SubsetFinder\SubsetCollection;
use Ozdemir\SubsetFinder\SubsetFinder;
use Ozdemir\SubsetFinder\SubsetFinderConfig;
$parts = [
new Item(1, 'Oak Leg', quantity: 90, price: 18.00),
new Item(2, 'Steel Leg', quantity: 60, price: 12.00),
new Item(3, 'Oak Top', quantity: 35, price: 80.00),
new Item(4, 'Glass Top', quantity: 10, price: 95.00),
new Item(5, 'Screw A', quantity: 500, price: 0.10),
new Item(6, 'Screw B', quantity: 140, price: 0.08),
];
$desk = new SubsetCollection([
Subset::of([1, 2])->take(4), // any 4 legs
Subset::of([3, 4])->take(1), // any top
Subset::of([5, 6])->take(8), // any 8 screws
]);
// Cheapest parts are consumed first
$finder = new SubsetFinder($parts, $desk, new SubsetFinderConfig(sortField: 'price'));
$finder->solve();
printf("Desks we can build: %d\n\n", $finder->getSubsetQuantity());
echo "Parts consumed:\n";
foreach ($finder->getFoundSubsets() as $part) {
printf(" %-9s x%d\n", $part->name, $part->quantity);
}
echo "\nParts left in the bin:\n";
foreach ($finder->getRemaining() as $part) {
printf(" %-9s x%d\n", $part->name, $part->quantity);
}Desks we can build: 37 Parts consumed: Steel Leg x60 Oak Leg x88 Oak Top x35 Glass Top x2 Screw B x140 Screw A x156 Parts left in the bin: Oak Leg x2 Glass Top x8 Screw A x344
How many coaching packages can we sell this month with the hours our tutors have left?
Quantities don't have to be things on a shelf — here they are hours, which split freely across packages. One package includes 10 senior hours and 20 junior hours, from any mix of tutors. Within each requirement the cheaper rate is booked first: Maya ($80) fills up before Tom ($90), Sam ($40) before Alex ($45).
use Ozdemir\SubsetFinder\Subset;
use Ozdemir\SubsetFinder\SubsetCollection;
use Ozdemir\SubsetFinder\SubsetFinder;
use Ozdemir\SubsetFinder\SubsetFinderConfig;
// quantity = hours available this month, price = hourly rate
$tutors = [
new Item(1, 'Maya (senior)', quantity: 40, price: 80.0),
new Item(2, 'Tom (senior)', quantity: 25, price: 90.0),
new Item(3, 'Alex (junior)', quantity: 60, price: 45.0),
new Item(4, 'Sam (junior)', quantity: 50, price: 40.0),
];
// One package = 10 senior hours + 20 junior hours, any mix of tutors
$package = new SubsetCollection([
Subset::of([1, 2])->take(10),
Subset::of([3, 4])->take(20),
]);
$finder = new SubsetFinder($tutors, $package, new SubsetFinderConfig(sortField: 'price'));
$finder->solve();
printf("Packages we can sell this month: %d\n\n", $finder->getSubsetQuantity());
echo "Hours booked (cheaper rate fills first within each requirement):\n";
foreach ($finder->getFoundSubsets() as $tutor) {
printf(" %-13s %3d hours @ \$%.0f/h\n", $tutor->name, $tutor->quantity, $tutor->price);
}
echo "\nHours still free:\n";
foreach ($finder->getRemaining() as $tutor) {
printf(" %-13s %3d hours\n", $tutor->name, $tutor->quantity);
}Packages we can sell this month: 5 Hours booked (cheaper rate fills first within each requirement): Maya (senior) 40 hours @ $80/h Tom (senior) 10 hours @ $90/h Sam (junior) 50 hours @ $40/h Alex (junior) 50 hours @ $45/h Hours still free: Tom (senior) 15 hours Alex (junior) 10 hours
Two recurring orders compete for the same product — how many rounds of both can we actually ship?
Order Alpha accepts either widget; Order Beta insists on the Pro. Checking each order against the stock independently counts the shared Pro units twice and promises rounds you cannot ship. The solver allocates everything from one shared pool.
use Ozdemir\SubsetFinder\Subset;
use Ozdemir\SubsetFinder\SubsetCollection;
use Ozdemir\SubsetFinder\SubsetFinder;
use Ozdemir\SubsetFinder\SubsetFinderConfig;
$stock = [
new Item(1, 'Widget Pro', quantity: 100, price: 8.00),
new Item(2, 'Widget Lite', quantity: 50, price: 3.00),
];
$orders = [
Subset::of([1, 2])->take(10), // Order Alpha: 10 of either widget per round
Subset::of([1])->take(10), // Order Beta: 10 Widget Pro per round
];
// The naive estimate: each order checked against the pool on its own.
$naive = PHP_INT_MAX;
foreach ($orders as $order) {
$supply = 0;
foreach ($stock as $item) {
if (in_array($item->getId(), $order->items, true)) {
$supply += $item->getQuantity();
}
}
$naive = min($naive, intdiv($supply, $order->quantity));
}
$finder = new SubsetFinder($stock, new SubsetCollection($orders), new SubsetFinderConfig(sortField: 'price'));
$finder->solve();
printf("Naive estimate : %2d rounds (double counts the shared Pro stock)\n", $naive);
printf("Shared-pool answer : %2d rounds (what you can actually ship)\n\n", $finder->getSubsetQuantity());
foreach ($finder->getFoundSubsets() as $item) {
printf(" %-12s %3d used\n", $item->name, $item->quantity);
}Naive estimate : 10 rounds (double counts the shared Pro stock) Shared-pool answer : 7 rounds (what you can actually ship) Widget Lite 50 used Widget Pro 90 used