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

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.

• $||x||_1$ is just the sum of all coordinates of $x$, isn't it? If I understand correctly, you are searching for an element $y$ which minimizes $||z||_1$ under the constraint $||x||_1<||z||_1$ ? Commented Jun 15, 2022 at 8:28
• @ChristopheLeuridan yes, you are right; the task is to report the vectors in increasing order of coordinate sums Commented Jun 15, 2022 at 9:18

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.

• If "a general-purpose sorting algorithm" sorts the elements of $X\times Y$, it costs $O(2n^2\log n)$ time for sorting them; sorting the individual lists is $O(2n\log n)$ the size of the "Dijkstra-algorithm heap" is $O(n)$ so that an update operation is $O(\log n)$ and $O(n^2)$ updates are made indicating that both methods are in $O(n^2\log n)$. The situation in which the Dijkstra algorithm is superior is when listing all pairs isn't the objective, e.g. in branch-and-bound situations. Commented Jul 19, 2022 at 10:47
• Dijkstra is also superior in space even if you want to list all pairs. (Also, sorting might take different time than what you state, if you use an integer sorting method; see en.wikipedia.org/wiki/Integer_sorting) Commented Jul 20, 2022 at 20:20

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.

• please note that I asked for minimal memory footprint; if I would like to check for the existence of a subset with given sum and exactly $k$ or $n-k$ summands, then that problem is in $P$ if $k$ is fixed (fixed parameter complexity) For $k=2$ I have an algorithm that enumerates all pairs of values using $O(n)$ space instead of $O(n^2)$ and for higher $k$ the space-savings are also very promising. Commented Jun 18, 2022 at 6:13
• @ManfredWeis I think "minimal memory" solution is unwanted without further restriction because the brute-force algorithm only needs $O(n)$ space to generate one next combination. I assume the time required per one combination should be small. Then, the priority-queue based approach uses $O(n)$ space with $O(\log n)$ time per combination for $k = 2$. Commented Jun 18, 2022 at 7:24
• what kind of brute force algorithm should that be, specifically in which order are the combinations generated? I guess it will be according to lexical order; but how can we then be sure that a specific combination, that also satisfies any further constraints, is indeed the optimal combination that satisfies all constraints? Regarding the size of the priority queue: do you have any reference for a proof of the claimed size limits? Commented Jun 18, 2022 at 14:10

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)))
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)
$$$$