Win a copy of Design for the Mind this week in the Design forum!

# Iterating over an unknown number of vectors

Mark Herschberg
Sheriff
Posts: 6037
I'm trying to solve the following problem.

We have an unknown number of vectors, each of unknown length. We would like to iterate over all possible tuples. Given the large data sizes we're dealing with, how do we do this without using recursion? (I don't see a way to simply apply tail recursion.)

--Mark

Example:

Given the following 4 vectors:

{1, 2, 3}
{4, 5}
{6}
{7, 8}

The algorithm should produce the following 3 x 2 x 1 x 2 = 12 tuples (where the actual order is unimportant):

1,4,6,7
1,4,6,8
1,5,6,7
1,5,6,8
2,4,6,7
2,4,6,8
2,5,6,7
2,5,6,8
3,4,6,7
3,4,6,8
3,5,6,7
3,5,6,8

Ernest Friedman-Hill
author and iconoclast
Marshal
Posts: 24208
35
The most straightforward way goes basically like this:

[ October 19, 2005: Message edited by: Ernest Friedman-Hill ]

Jim Yingst
Wanderer
Sheriff
Posts: 18671
As it happens I made something for this a few months ago which uses JDK 5. This one does not require a huge array to store all the permutations in memory simultaneously; instead it just keeps incrementing the indices in an orderly manner, and calls a handle() method for each unique combination of indices.

Here's sample code that uses it:

Producing this output:

[ October 20, 2005: Message edited by: Jim Yingst ]

Mark Herschberg
Sheriff
Posts: 6037
Brilliant!

We actually were trying to modify some C code which did this with macros and I was banging my head against it for a bit. Good thing we phrased the problem in root form, as opposed to, "I've got this C code..."

I'm just embarassed that I didn't see that solution--especially since just last week I was just explaining the diagonalization proof for the countability of rational numbers.

Thanks guys.

--Mark