Create a Cartesian product in descending order of amount

Question

Given n sorted lists of integers A1, A2, ..., An in descending order, is there an algorithm for efficiently generating all elements of their Cartesian product while decreasing the sum of the sum of the order?

For example, n = 3

A1 = [9, 8, 0]
A2 = [4, 2]
A3 = [5, 1]

The expected result will be the Cartesian product A1xA2xA3 in the following order:
combination sum
9, 4, 5 18
8, 4, 5 17
9, 2, 5 16
8, 2, 5 15
9, 4, 1 14
8, 4, 1 13
9, 2, 1 12
8, 2, 1 11
0, 4, 5 9
0, 2, 5 7
0, 4, 1 5
0, 2, 1 3

Answer 1

If the problem instance has N intersection sets, then you can think of tuples in the product as an N-dimensional "rectangular" grid, where each tuple corresponds to a grid element. You will start by emitting max. The total set [9,4,5], which is located in one corner of the grid.

" " , . , "" . - , .

, , . , .

[9,4,5]

[8,4,5]  (one smaller on first dimension)
[9,2,5]  (one smaller on second dimension)
[9,4,1]  (one smaller on third dimension) 

. [8,4,5].

[0,4,5], [8,2,5], [8,4,1]

,

[9,2,5], [9,4,1], [0,4,5], [8,2,5], [8,4,1]

. [9,2,5]. -

[8,2,5], [9,2,1]. 

,

[9,4,1], [0,4,5], [8,2,5], [8,4,1], [9,2,1]

[8,2,5] . .

- [8,2,5]. -

[0,2,5], [8,2,1]

.

. O (log | C |), C - .

? . . , ,

|C| = O(|A1||A2| + |A2||A3| + |A1||A3|)

,

O(log(|A1||A2| + |A2||A3| + |A1||A3|))

N, O (log 3 N ^ 2) = O (log 3 + 2 log N) = O (log N).

A1 A1 A2 || A3 | , O (N ^ 3).

O (log N ^ 3) = O (3 log N) = O (log N). 50% , . , O (N). / - O (N ^ 2).

Java, .

import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class SortedProduct {
  final SortedTuple [] tuples;
  final NoDupHeap candidates = new NoDupHeap();

  SortedProduct(SortedTuple [] tuple) {
    this.tuples = Arrays.copyOf(tuple, tuple.length);
    reset();
  }

  static class SortedTuple {
    final int [] elts;

    SortedTuple(int... elts) {
      this.elts = Arrays.copyOf(elts, elts.length);
      Arrays.sort(this.elts);
    }

    @Override
    public String toString() {
      return Arrays.toString(elts);
    }
  }

  class RefTuple {
    final int [] refs;
    final int sum;

    RefTuple(int [] index, int sum) {
      this.refs = index;
      this.sum = sum;
    }

    RefTuple getSuccessor(int i) {
      if (refs[i] == 0) return null;
      int [] newRefs = Arrays.copyOf(this.refs, this.refs.length);
      int j = newRefs[i]--;
      return new RefTuple(newRefs, sum - tuples[i].elts[j] + tuples[i].elts[j - 1]);
    }

    int [] getTuple() {
      int [] val = new int[refs.length];
      for (int i = 0; i < refs.length; ++i) 
        val[i] = tuples[i].elts[refs[i]];
      return val;
    }

    @Override
    public int hashCode() {
      return Arrays.hashCode(refs);
    }

    @Override
    public boolean equals(Object o) {
      if (o instanceof RefTuple) {
        RefTuple t = (RefTuple) o;
        return Arrays.equals(refs, t.refs);
      }
      return false;
    }
  }

  RefTuple getInitialCandidate() {
    int [] index = new int[tuples.length];
    int sum = 0;
    for (int j = 0; j < index.length; ++j) 
      sum += tuples[j].elts[index[j] = tuples[j].elts.length - 1];
    return new RefTuple(index, sum);
  }

  final void reset() {
    candidates.clear();
    candidates.add(getInitialCandidate());
  }

  int [] getNext() {
    if (candidates.isEmpty()) return null;
    RefTuple next = candidates.poll();
    for (int i = 0; i < tuples.length; ++i) {
      RefTuple successor = next.getSuccessor(i);
      if (successor != null) candidates.add(successor);
    }
    return next.getTuple();
  }

  /** A max heap of indirect ref tuples that ignores addition of duplicates. */
  static class NoDupHeap {
    final PriorityQueue<RefTuple> heap = 
        new PriorityQueue<>((a, b) -> Integer.compare(b.sum, a.sum));
    final Set<RefTuple> set = new HashSet<>();

    void add(RefTuple t) {
      if (set.contains(t)) return;
      heap.add(t);
      set.add(t);
    }

    RefTuple poll() {
      RefTuple t = heap.poll();
      set.remove(t);
      return t;
    }

    boolean isEmpty() {
      return heap.isEmpty();
    }

    void clear() {
      heap.clear();
      set.clear();
    }
  }

  public static void main(String [] args) {
    SortedTuple [] tuples = {
      new SortedTuple(9, 8, 0),
      new SortedTuple(4, 2),
      new SortedTuple(5, 1),
    };
    SortedProduct product = new SortedProduct(tuples);
    for (;;) {
      int[] next = product.getNext();
      if (next == null) break;
      System.out.println(Arrays.toString(next));
    }
  }
}

Answer 2

Python. ( - , , .)

#! /usr/bin/env python
import heapq

def decreasing_tuple_order(*lists):
    # Each priority queue element will be:
    #    (-sum, indices, incrementing_index, sliced)
    # The top element will have the largest sum.
    if 0 < min((len(l) for l in lists)):
        indices = [0 for l in lists]
        sliced = [lists[i][indices[i]] for i in range(len(indices))]
        queue = [(-sum(sliced), indices, 0, sliced)]
        while 0 < len(queue):
            #print(queue)
            (_, indices, indexable, sliced) = heapq.heappop(queue)
            yield sliced

            # Can we increment this index?
            if indices[indexable] + 1 < len(lists[indexable]):
                new_indices = indices[:]
                new_indices[indexable] = indices[indexable] + 1
                sliced = [lists[i][new_indices[i]] for i in range(len(indices))]
                heapq.heappush(queue, (-sum(sliced), new_indices, indexable, sliced))

            # Start indexing the next index?
            while indexable + 1 < len(lists):
                indexable = indexable + 1
                if 1 < len(lists[indexable]):
                    # Start incrementing here.
                    indices[indexable] = 1
                    sliced = [lists[i][indices[i]] for i in range(len(indices))]
                    heapq.heappush(queue, (-sum(sliced), indices, indexable, sliced))



a1 = [9, 8, 0]
a2 = [4, 2]
a3 = [5, 1]

for x in decreasing_tuple_order(a1, a2, a3):
    print((x,sum(x)))

Answer 3

In python you can just use itertools.product

>>> A1 = [9, 8, 0]
>>> A2 = [4, 2]
>>> A3 = [5, 1]
>>> from itertools import product
>>> for p in product(A1, A2, A3):
...     print sum(p)
... 
18
14
16
12
17
13
15
11
9
5
7
3