Introduction

Generating a Cartesian product in decreasing sum order means producing tuples from several input sequences so that tuples with larger element sums appear first. For small inputs, the simplest solution is to generate every tuple and sort the result. For large inputs, that becomes expensive, and a heap-based best-first algorithm can produce tuples in the right order without materializing the full product up front.

The Simple Solution: Generate and Sort

If the total product size is modest, use itertools.product and sort by sum.

1from itertools import product
2
3lists = [
4    [1, 2],
5    [3, 4],
6    [5, 6],
7]
8
9tuples = list(product(*lists))
10ordered = sorted(tuples, key=sum, reverse=True)
11
12for item in ordered:
13    print(item, "sum =", sum(item))

This is easy to read and correct. The downside is that it builds the entire Cartesian product in memory and sorts all of it afterward.

That is fine when the product size is small enough that clarity matters more than optimization.

Why Large Products Need a Different Approach

Suppose you have three lists of length 1,000. The Cartesian product contains one billion tuples. Generating all of them just to sort by sum is not realistic.

If the input lists are sorted in descending order, you can do something smarter. The tuple made from all first elements has the maximum possible sum. From there, you can explore neighboring tuples in best-first order using a max-heap.

Heap-Based Best-First Generation

The idea is:

• sort each input list in descending order
• start from the tuple using index 0 in every list
• store candidates in a heap keyed by tuple sum
• each time you pop the current best tuple, push neighbors formed by advancing one index

Here is a working version:

1import heapq
2
3
4def cartesian_by_decreasing_sum(lists):
5    arrays = [sorted(values, reverse=True) for values in lists]
6    start_indices = tuple(0 for _ in arrays)
7    start_tuple = tuple(arr[0] for arr in arrays)
8    start_sum = sum(start_tuple)
9
10    heap = [(-start_sum, start_indices)]
11    seen = {start_indices}
12
13    while heap:
14        neg_sum, indices = heapq.heappop(heap)
15        current = tuple(arrays[i][indices[i]] for i in range(len(arrays)))
16        yield current
17
18        for dim in range(len(arrays)):
19            next_indices = list(indices)
20            next_indices[dim] += 1
21
22            if next_indices[dim] >= len(arrays[dim]):
23                continue
24
25            next_indices = tuple(next_indices)
26            if next_indices in seen:
27                continue
28
29            seen.add(next_indices)
30            next_tuple = tuple(arrays[i][next_indices[i]] for i in range(len(arrays)))
31            heapq.heappush(heap, (-sum(next_tuple), next_indices))
32
33
34lists = [
35    [4, 1],
36    [6, 3],
37    [5, 2],
38]
39
40for item in cartesian_by_decreasing_sum(lists):
41    print(item, "sum =", sum(item))

This yields tuples from highest sum downward without generating the entire product first.

Why the Heap Approach Works

When each list is sorted descending, moving forward in any dimension cannot increase the tuple sum. That monotonic property is what makes best-first exploration valid.

The heap always exposes the largest not-yet-emitted candidate. The seen set prevents the same index combination from being inserted multiple times through different paths.

This is similar in spirit to best-first search on a grid of index combinations.

When to Use Each Approach

Use generate-and-sort when:

• the product is small
• code simplicity matters most
• you need all tuples anyway

Use the heap-based generator when:

• the product is huge
• you only need the first few highest-sum tuples
• input lists can be sorted descending

That second case is common in search, ranking, and top-k problems where the full Cartesian product is far larger than the answer you actually need.

Tie Handling and Custom Ordering

Two different tuples can have the same sum. The algorithms above do not guarantee any special secondary ordering among ties unless you add one yourself.

If you want a stable tiebreaker, sort with a compound key:

ordered = sorted(product(*lists), key=lambda item: (sum(item), item), reverse=True)

For the heap-based version, you would include a secondary key in the heap entry if deterministic tie behavior matters.

Common Pitfalls

The first pitfall is generating the full product for a problem that only needs the top few results. That wastes both memory and time.

Another issue is applying the heap-based method without first sorting the input lists in descending order. Without that monotonic structure, the best-first logic no longer guarantees correct output order.

Developers also forget to track visited index combinations, which causes duplicate tuples to be pushed into the heap repeatedly.

Finally, do not ignore tie behavior if your application depends on deterministic ordering among equal sums.

Summary

• For small inputs, itertools.product plus sorting is the simplest correct solution.
• For large inputs, a max-heap can generate tuples lazily in decreasing sum order.
• The heap-based method relies on each input list being sorted descending.
• Track visited index combinations to avoid duplicates.
• Choose the approach based on product size and whether you need all tuples or only the top results.