Enumerating the elements of cartesian products in ascending order of $\|\cdot\|_1$ norm

Question

let $\boldsymbol{X}_1,\,\dots,\,\boldsymbol{X}_n$ be well-ordered sets of positive values and $\mathcal{R}:=\lbrace\left(x_1,\,\dots,\,x_n\right)\rbrace = \boldsymbol{X}_1\times\,\dots\,\times\boldsymbol{X}_n$ the "induced" coordinate space.

Question:

given $\boldsymbol{x}:=(x_1,\,\cdots,\,x_n)\in\mathcal{R}$, how can one determine $$\boldsymbol{y}:=(y_1,\,\cdots,\,y_n)\in\mathcal{R}:\\\quad \|\boldsymbol{x}\|_1\,\lt\,\|\boldsymbol{y}\|_1\quad \land\quad \|\boldsymbol{x}\|_1\,\lt\,\|\boldsymbol{z}\|_1\implies \|\boldsymbol{y}\|_1\,\le\,\|\boldsymbol{z}\|_1$$ under the assumption that all norms are different and the elements of the $\boldsymbol{X}_i$ are sorted in ascending order?

As I intend to utilize the successor-generation in a branch and bound algorithm, I am looking for algorithms with minimal memory footprint.

Disclaimer: I already have an idea for such an algorithm, but can't prove its correctness and would like to hear of existing solutions before sharing my idea.

Answer 1

Even the case $n=2$ is a well-known open problem, X + Y sorting. It is unknown whether one can list the elements faster than the time it would take to apply a general-purpose sorting algorithm.

If you care more about space than time then the "Dijkstra's algorithm on a product of path graphs" solution mentioned in an earlier comment will at least take space proportional to a product one dimension lower than the overall product, while still taking the same amount of time as sorting.

Answer 2

This problem is at least as hard as the subset sum problem, therefore NP-hard.

For an instance of the subset sum problem with positive integer items $a_1, \dots, a_n$ and the target $T$, let $X_i = \{ 0, a_i + 2^{-i} \}$ and $X_{n+1} = \{ 0, T \}$. Then, the next point after $y = (0, \dots, 0, T)$ has $\|z\|_1 < T+1$ if and only if there is a subset sums to $T$.

All norms are different because $2^{-i}$ terms can be used to reconstruct the used subset. Values can be made positive by adding $1$ to all elements, as it doesn't change the ordering.

Answer 3

I share my "toy code" as an answer to make visually clear that at least a heuristic is available

# -*- coding: utf-8 -*-
"""
Created on Sat Jun 18 12:50:48 2022

@author: Manfred Weis


The algorithm is a "proof of concept" for enumerating the elements of the 
Cartesian  product of $k$ sets of positive values in ascending order of the
individual tuple's'weight sum

The code is neither verified nor optimized

"""

import numpy as np
from queue import PriorityQueue
  
q = PriorityQueue()

  
rows = 3 # the number of sets, i.e. $k$
cols = 5 # the number $n$ of elements; need not bequal for the sets

# generate random instance
X = np.random.rand(rows,cols)
for row in range(rows):
    for col in range(1,cols):
        X[row][col] += X[row][col-1]
print(X)

# the weight of the tuples
def weight(p):
    return sum([X[i][p[i]] for i in range(rows)])

def run(X):
    t = tuple([0]*rows)
    s = set()
    q.put(tuple((weight(t),t)))
    s.add(t)
    while q.queue:
        print('len(q):' + str(len(q.queue)))
        w_t = q.get()
        w = w_t[0]
        t = w_t[1]
        print(w_t)
        p=list(t)
        s.discard(t)
        r=[p.copy() for i in range(rows)]
        for i in range(rows):
            if(r[i][i] < cols-1):
                r[i][i] += 1
                t = tuple(r[i])
                if t not in s:
                    q.put(tuple((weight(t),t)))
                    s.add(t)
run(X)
``