Win a copy of Design for the Mind this week in the Design forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Iterating over an unknown number of vectors

 
Mark Herschberg
Sheriff
Posts: 6037
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 24208
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The most straightforward way goes basically like this:


[ October 19, 2005: Message edited by: Ernest Friedman-Hill ]
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic