Forum Archive

Go Back   3D Realms Forums > General Topics > Programming Forum
Blogs FAQ Members List Social Groups Calendar Mark Forums Read

Notices

 
 
Thread Tools
Old 08-15-2007, 06:49 AM   #1
NetNessie

NetNessie's Avatar
Recursion Question
I'm working with Java 5\1.5 and I have a series of arrays, each array stores a collection of objects. The number of arrays and the number of objects is not constant; it changes depending on the users input.

What I am trying to do is iterate over each element in each array and add them to a new array. This new array will store every possible combination of elements from the other arrays.

I.e. 3 arrays each storing 3 elements will produce 9 unique combinations.

The reason why I am stumped is because neither the arrays nor the number of elements is constant; sometimes I only need a small number of elements, other times many. So, I can't be lazy and write a series of for-loops.

Does anyone have any suggestions?
__________________
Ink Grass LazyMoon Photography
"Say something wise, and your name will be remembered forever." - Anonymous
NetNessie is offline  
Old 08-15-2007, 09:45 AM   #2
phreak
Re: Recursion Question
Could you give some concrete code?

It's not exactly clear to me what you're trying to do. Most naively, you can just store the number of elements and number of arrays in variables and iterate over that, but I'm not sure what you're doing, so that may be way off.
__________________
"A fool sees not the same tree that a wise man sees." - William Blake
phreak is offline  
Old 08-15-2007, 10:37 AM   #3
NetNessie

NetNessie's Avatar
Re: Recursion Question
Quote:
Originally Posted by phreak View Post
It's not exactly clear to me what you're trying to do.
I'll try to explain it more clearly.

I have two classes; Program and Session. Program contains the details about a particular university class (like a computer practical, lecture, tutorial, etc). Session contains a day, start and end time. Each program object associates with a varying number of session objects, which identifies when the day and time a program is held.

Say for example I've created 4 program objects, each program has 4 sessions objects. Since I only have to attend one session for each program, I have 256 different combinations to choose from. Therefore, each combination can only contain the same number of sessions as there are programs.

What I am trying to do is generate these 256 combinations. I want to take the first session associated with the first program and put it in an array with the first session from the second program, and so forth. The 256th combination will be the fourth session from all four programs.

Normally, I'd just use 4 for-loops nestled within each other. However, I don't know how many programs there will be, so I am looking for a solution that accomplishes the same thing.

Hope that clears things up (I need diagrams in the future)
__________________
Ink Grass LazyMoon Photography
"Say something wise, and your name will be remembered forever." - Anonymous
NetNessie is offline  
Old 08-16-2007, 02:38 AM   #4
Parkar

Parkar's Avatar
Re: Recursion Question
I would just create an array with counters, one for each array. Then have a loop that each iteration counts up the counters in the same fashion as a digital clock. Once the first counter reaches the last element in the first array you are done.
Parkar is offline  
Old 08-16-2007, 03:53 AM   #5
NetNessie

NetNessie's Avatar
Re: Recursion Question
Quote:
Originally Posted by Parkar View Post
I would just create an array with counters, one for each array. Then have a loop that each iteration counts up the counters in the same fashion as a digital clock.
That was the approach I started before thinking there might be an easier way It's probably the best and only approach.
__________________
Ink Grass LazyMoon Photography
"Say something wise, and your name will be remembered forever." - Anonymous
NetNessie is offline  
Old 08-16-2007, 05:26 PM   #6
NutWrench

NutWrench's Avatar
Re: Recursion Question
Are the individual elements in the array unique?
I.E. for an array with 3 elements, are you looking for something like:

321 231 312 132 213 123 ?
__________________
"If by chance some day you're not feeling well and you should remember some silly thing I've said or done and it brings back a smile to your face or a chuckle to your heart, then my purpose as your clown has been fulfilled."
NutWrench is offline  
Old 08-17-2007, 01:56 AM   #7
NetNessie

NetNessie's Avatar
Re: Recursion Question
Quote:
Originally Posted by NutWrench View Post
I.E. for an array with 3 elements, are you looking for something like: 321 231 312 132 213 123 ?
Actually, I'm looking for something like:
I have three programs: A, B & C. A has three sessions, and B & C have two each,

A:[1, 2, 3]
B:[1, 2]
C:[1, 2]

What I want to generate is the following combinations:

[A1, B1, C1]
[A1, B1, C2]
[A1, B2, C1]
[A1, B2, C2]

[A2, B1, C1]
[A2, B1, C2]
[A2, B2, C1]
[A2, B2, C2]

[A3, B1, C1]
[A3, B1, C2]
[A3, B2, C1]
[A3, B2, C2]

Is this making any sense?
__________________
Ink Grass LazyMoon Photography
"Say something wise, and your name will be remembered forever." - Anonymous
NetNessie is offline  
Old 08-17-2007, 11:05 AM   #8
Krust

Krust's Avatar
Re: Recursion Question
EDIT: wanted to post the code etc here, but the board is giving me a hard time doing this.

Instead, I uploaded it to my webspace.
__________________
The statement beneath is false
The statement above is true
Last edited by Krust; 08-17-2007 at 11:16 AM.
Krust is offline  
Old 08-17-2007, 05:33 PM   #9
rg3
Re: Recursion Question
Without using any specific language, I think the work you need to do is pretty trivial in any language. You have a sequence of arrays, and each array is a sequence of elements. Your combinations always have the same length as the number of arrays present.

Let's, like you said, have 3 arrays A, B and C as you described, with 3, 2 and 2 elements each. Your "combinations" have length 3, because there are 3 arrays (A, B and C). Let's suppose your arrays are also stored somewhere, so you can refer them by index. Let's suppose the arrays are stored in a variable called arrays. And finally let's suppose you have an output array that will store every combination, called combination, and an action to run on each combination, called action.

The following function iterates recursively over the combination array, setting each position.

Code:
function action_on_combs(arrays, combination, position, action)
{
    // all positions set
    if (position > length of "arrays" sequence) {
        action(combination);
        return;
    }

    // set the next position to each possible value, recursively
    for each item in arrays[position] {
        combination[position] = item;
        action_on_combs(arrays, combination, position + 1, action);
    }
}
Edit: of course, the initiall call should be used with position set to zero.
Last edited by rg3; 08-17-2007 at 05:40 PM.
rg3 is offline  
Old 08-18-2007, 04:47 PM   #10
Parkar

Parkar's Avatar
Re: Recursion Question
The problem with implementing it as a recursive function is it will result in a very deep stack of function calls if he uses it on large datasets. My loop suggestion came from thinking of it as a recursive operation though.
Parkar is offline  
Old 08-19-2007, 12:48 AM   #11
NetNessie

NetNessie's Avatar
Re: Recursion Question
Quote:
Originally Posted by Parkar View Post
The problem with implementing it as a recursive function is it will result in a very deep stack of function calls if he uses it on large datasets.
I'm looking at around 768,000 combination from an average input.
__________________
Ink Grass LazyMoon Photography
"Say something wise, and your name will be remembered forever." - Anonymous
NetNessie is offline  
Old 08-19-2007, 04:29 AM   #12
rg3
Re: Recursion Question
The maximum recursion depth is the number of arrays you have. If the high number of combinations stem from the number of array items, there is no problem. If they stem from the number of arrays, there is a problem. Still, as Parkar mentioned, you can still do it with two nested loops avoiding recursion. The code is only slightly more complicated.

BTW, I just noticed a blatant error in my code above. The ">" comparisson in the first "if" block should be a ">=".
rg3 is offline  
 

Bookmarks

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -6. The time now is 03:06 AM.

Page generated in 0.14146709 seconds (100.00% PHP - 0% MySQL) with 18 queries

Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2019, vBulletin Solutions, Inc.

Website is 1987-2014 Apogee Software, Ltd.
Ideas and messages posted here become property of Apogee Software Ltd.