Optimizing Coupon Combination Algorithms: From Cartesian Product to Array Indexing

1. Basics of Saving Money: Understanding Platform Coupon Rules

Rule 1: Coupons are divided into three major categories – “product coupons”, “stackable vouchers”, and “shipping coupons”.

Rule 2: For each SKU (same product ID), at most one coupon of each major type can be used.

Rule 3: Product coupons and stackable vouchers may have a minimum spend threshold, which is calculated after any promotional discounts; shipping coupons use the post‑discount amount of product and stackable vouchers as their threshold.

Rule 4: A higher threshold does not guarantee a higher discount, although it is often the case.

Rule 5: Most coupons have usage restrictions related to product category, business line, seller, service, specific product range, release time, as well as scene (terminal type, marketplace) and buyer/seller status (new customer, risk control, etc.).

Rule 6: Product coupons and stackable vouchers are further divided into “full‑amount reduction” and “full‑amount discount”. The latter may have a maximum discount amount (e.g., 10 % off up to ¥1000). Shipping coupons are either fixed‑amount or free‑shipping.

2. Concrete Example

To illustrate the problem, we ignore Rule 5 and shipping coupons and focus only on product coupons.

Scenario: Five products – P1=¥10, P2=¥20, P3=¥30, P4=¥40, P5=¥50.

Five product coupons – R1: spend ¥10, get ¥5 off; R2: spend ¥20, get ¥12 off; R3: spend ¥30, get ¥10 off; R4: spend ¥90, get ¥60 off; R5: spend ¥100, get ¥80 off. The compatibility matrix is shown in the following image.

3. Evolution of the Optimal Coupon Combination Calculation

3.1 First Generation – “Cartesian Product” Version

First, aggregate the usable products for each coupon:

R1 → P2, P3, P4, P5
R2 → P1, P3, P4, P5
R3 → P1, P2, P4, P5
R4 → P1, P2, P3, P5
R5 → P1, P2, P3, P4

All possible combinations are enumerated (yellow cells indicate combinations that do not meet the coupon threshold). The matrix is visualized in the following images.

The Cartesian product of columns is then computed (see image).

After evaluating each combination’s discount amount and sorting descending, the optimal result is: use R2 for product P5 and R5 for products P1‑P4, yielding a total discount of ¥92.

Core idea: Enumerate all possible coupon‑product assignments, compute each combination’s discount, and pick the maximum.

Problem: The number of combinations grows exponentially with the number of products and coupons, leading to OOM when computing the Cartesian product.

3.2 Second Generation – “Map Aggregation” Version

The first version’s drawback is that it builds all combinations before calculation, causing huge memory consumption. The second version adopts a “compute‑while‑enumerate” strategy, retaining only the best solution found so far and stopping when a time budget is exceeded.

It uses a HashMap to record the pointer positions for each product’s coupon list. Sample data structures:

// Record, for each product, the list of usable coupons per major type
private Map
> prodRed = Maps.newHashMap();

// Record, for each product, the index of the coupon being used in the list above
private Map
pointer = Maps.newHashMap();

Pointer movement creates a new combination (yellow cells indicate the current pointer position). Example image:

When a pointer moves, the algorithm re‑aggregates the products that share the same coupon:

// Record using Map structure
Map
>> oneType2RedId2Prods = Maps.newEnumMap(ERedMetaBigType.class);

Advantages: No need to generate the full combination space; the algorithm can be interrupted once the time limit is reached. Disadvantages: Each pointer shift requires rebuilding temporary Map and List objects, causing heavy GC pressure.

3.3 Third Generation – “Array Index Positioning” Version

The third version eliminates the massive temporary Map objects by using primitive arrays.

Data structures:

Long[] infoArray – stores product IDs; the index itself represents the product.

Long[] redArray – stores coupon IDs; the index represents the coupon.

byte[][] infoRedRel – a two‑dimensional matrix indicating the relationship between products and coupons (0 = not used in current iteration, 1 = used, -1 = not applicable).

The relationship matrix is shown below:

With this matrix, changing a cell’s value (excluding -1) directly modifies the coupon‑product combination without creating new objects. The algorithm now iterates over the coupon array, reads the corresponding entry in infoRedRel , and fetches the product from infoArray .

4. Summary

The article outlines the evolution of optimal coupon‑combination algorithms. The benchmark (average of 30 runs) compares the second and third generations under varying numbers of coupons, products, and per‑product coupon counts, showing that the third generation completes the computation in under 200 ms and processes more than five times the combinations of the second generation.

Beyond memory consumption (the first version can trigger Full GC or OOM), the key performance bottleneck in large‑scale calculations is the creation and destruction of temporary objects. The third generation’s array‑based approach dramatically reduces GC pressure, achieving a substantial speedup.

About the author

Ma Baoshan, Java development engineer in Zhaozhuan’s transaction middle‑platform.