aspose file tools*
The moose likes Java in General and the fly likes Iterating over an unknown number of vectors Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Iterating over an unknown number of vectors" Watch "Iterating over an unknown number of vectors" New topic
Author

Iterating over an unknown number of vectors

Mark Herschberg
Sheriff

Joined: Dec 04, 2000
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

Joined: Jul 08, 2003
Posts: 24184
    
  34

The most straightforward way goes basically like this:


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

[Jess in Action][AskingGoodQuestions]
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
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 ]

"I'm not back." - Bill Harding, Twister
Mark Herschberg
Sheriff

Joined: Dec 04, 2000
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
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Iterating over an unknown number of vectors