File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
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

Win a copy of REST with Spring (video course) this week in the Spring forum!
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

Iterating over an unknown number of vectors

Mark Herschberg

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



Given the following 4 vectors:

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

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

Ernest Friedman-Hill
author and iconoclast

Joined: Jul 08, 2003
Posts: 24195

The most straightforward way goes basically like this:

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

[Jess in Action][AskingGoodQuestions]
Jim Yingst

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

Joined: Dec 04, 2000
Posts: 6037

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.

I agree. Here's the link:
subject: Iterating over an unknown number of vectors
It's not a secret anymore!