Programming Forums > Application Development > Java

smg1001 · Jan 17th, 2006, 11:22 AM

Thanks Arevos, you're extremely helpful. I'll have a look at this and try work it out further. I've never practiced recursion before but I'm beginning to see how it would work here.

Sean

alcdotcom · Jan 17th, 2006, 1:08 PM

Sorry - been busy with my classes. Looks like you guys are doing ok though.

smg1001 · Jan 17th, 2006, 1:34 PM

I've read the code and understand it. I don't know what I should put in the else block. I know there should be a recursive call back to group(). But should the arrays a and b that are sent back in recursive call be one element smaller? And should this element be removed from the head?

Arevos · Jan 17th, 2006, 3:05 PM

Well, look at it this way: you're taking the lists a and b and combining them to produce the output list. So you're moving elements from your input lists to your output. As your output grows, your input shrinks.

But this isn't a serial process. You don't want to create one output list, you want to create many of them, one for each possible combination of the input lists a and b.

Let's take an example of how one, individual combination might be constructed. Let's say you have a and b defined so:

(Toggle Plain Text)

a = {"A", "B", "C"}
b = {1, 2, 3}

We begin with the first element, a[0]. It's pretty easy to see that there are three combinations for your output lists:

(Toggle Plain Text)

a[0]b[0]
a[0]b[1]
a[0]b[2]

So far so good? Lets say we go with a[0]b[1]. We will output this as "A = 2", because a[0] is "A" and b[1] is 2.

Now for the second element in our combination. We've used up A and 2, so we need to remove them from the lists, because we can only use each letter once in a combination. The sequence "A = 1, A = 2, B = 3", is, I assume, not a valid sequence because A appears twice.

So with A and 2 removed from our lists:

(Toggle Plain Text)

a = {"B", "C"}
b = {1, 3}

Here we repeat the step of combining a[0] with an element from b, but this time, a[0] is "B", and there are only 2 elements from b.

Let's say we go with a[0]b[0], or "B = 1". Again, we remove "B" and 1 from our lists, and we get:

(Toggle Plain Text)

a = {"C"}
b = {3}

Now we're at our limiting condition, because there's only one choice, a[0]b[0], or "C = 3". Since we're at our limiting condition, we can now print out our combination:

(Toggle Plain Text)

A = 2
B = 1
C = 3

That's one combination done. Let's return to the first step, and examine it a little more closely. Remember that when we started, we had three choices for the first element:

(Toggle Plain Text)

a[0]b[0]
a[0]b[1]
a[0]b[2]

We had three choices because the size of our lists, n was equal to three. This could quite easily have been 4, 5 or even 50:

(Toggle Plain Text)

a[0]b[0]
a[0]b[1]
...
a[0]b[n - 1]

A combination sequence could start with any one of these. So we need a loop that combines a[0] with each b, and then to pass this onto the next recursive method call.

Some helpful commands you'll probably need:

(Toggle Plain Text)

a.get(0);               // get the first element of a
a.get(j);               // get the (j-1)th element of a
List newA = new LinkedList(a); // make a copy of list a
a.add(newElement);             // add newElement onto the end of list a
String e = a.remove(j);      // remove the (j-1)th element of a and put it in e

crawforddavid2006 · Jan 17th, 2006, 5:01 PM

I'm not trying to start a fight but for future reference please use code tags.

Jan 17th, 2006, 1:08 PM	#12
alcdotcom Programmer Join Date: Jan 2006 Location: Dallas, TX Posts: 49 Rep Power: 0	Sorry - been busy with my classes. Looks like you guys are doing ok though. __________________ Java Blog

Jan 17th, 2006, 3:05 PM	#14
Arevos Programming Guru Join Date: Aug 2005 Location: England Posts: 1,499 Rep Power: 5	Well, look at it this way: you're taking the lists a and b and combining them to produce the output list. So you're moving elements from your input lists to your output. As your output grows, your input shrinks. But this isn't a serial process. You don't want to create one output list, you want to create many of them, one for each possible combination of the input lists a and b. Let's take an example of how one, individual combination might be constructed. Let's say you have a and b defined so: (Toggle Plain Text) a = {"A", "B", "C"} b = {1, 2, 3} a = {"A", "B", "C"} b = {1, 2, 3} We begin with the first element, a[0]. It's pretty easy to see that there are three combinations for your output lists: (Toggle Plain Text) a[0]b[0] a[0]b[1] a[0]b[2] a[0]b[0] a[0]b[1] a[0]b[2] So far so good? Lets say we go with a[0]b[1]. We will output this as "A = 2", because a[0] is "A" and b[1] is 2. Now for the second element in our combination. We've used up A and 2, so we need to remove them from the lists, because we can only use each letter once in a combination. The sequence "A = 1, A = 2, B = 3", is, I assume, not a valid sequence because A appears twice. So with A and 2 removed from our lists: (Toggle Plain Text) a = {"B", "C"} b = {1, 3} a = {"B", "C"} b = {1, 3} Here we repeat the step of combining a[0] with an element from b, but this time, a[0] is "B", and there are only 2 elements from b. Let's say we go with a[0]b[0], or "B = 1". Again, we remove "B" and 1 from our lists, and we get: (Toggle Plain Text) a = {"C"} b = {3} a = {"C"} b = {3} Now we're at our limiting condition, because there's only one choice, a[0]b[0], or "C = 3". Since we're at our limiting condition, we can now print out our combination: (Toggle Plain Text) A = 2 B = 1 C = 3 A = 2 B = 1 C = 3 That's one combination done. Let's return to the first step, and examine it a little more closely. Remember that when we started, we had three choices for the first element: (Toggle Plain Text) a[0]b[0] a[0]b[1] a[0]b[2] a[0]b[0] a[0]b[1] a[0]b[2] We had three choices because the size of our lists, n was equal to three. This could quite easily have been 4, 5 or even 50: (Toggle Plain Text) a[0]b[0] a[0]b[1] ... a[0]b[n - 1] a[0]b[0] a[0]b[1] ... a[0]b[n - 1] A combination sequence could start with any one of these. So we need a loop that combines a[0] with each b, and then to pass this onto the next recursive method call. Some helpful commands you'll probably need: (Toggle Plain Text) a.get(0); // get the first element of a a.get(j); // get the (j-1)th element of a List newA = new LinkedList(a); // make a copy of list a a.add(newElement); // add newElement onto the end of list a String e = a.remove(j); // remove the (j-1)th element of a and put it in e a.get(0); // get the first element of a a.get(j); // get the (j-1)th element of a List newA = new LinkedList(a); // make a copy of list a a.add(newElement); // add newElement onto the end of list a String e = a.remove(j); // remove the (j-1)th element of a and put it in e

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Jan 17th, 2006, 11:22 AM	#11
smg1001 Newbie Join Date: Jan 2006 Posts: 10 Rep Power: 0	Thanks Arevos, you're extremely helpful. I'll have a look at this and try work it out further. I've never practiced recursion before but I'm beginning to see how it would work here. Sean

Jan 17th, 2006, 1:34 PM	#13
smg1001 Newbie Join Date: Jan 2006 Posts: 10 Rep Power: 0	I've read the code and understand it. I don't know what I should put in the else block. I know there should be a recursive call back to group(). But should the arrays a and b that are sent back in recursive call be one element smaller? And should this element be removed from the head?

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > Java

Pairing elements of two arrays...please help!!!