smg1001

Hi there,

I'm trying to implement the problem of printing every possible pair combination of elements in two arrays. The pattern I have in mind is very simple, I just don't know how to implement it. Here's an example:

g[3] = {'A', 'B', 'C'}
h[3] = {1, 2, 3}

...code...??

Expected Output:

A = 1
B = 2
C = 3

A = 1
B = 3
C = 2

A = 2
B = 1
C = 3

A = 2
B = 3
C = 1

A = 3
B = 1
C = 2

A = 3
B = 2
C = 1

The code should work for any array size, as long as both arrays are the same size. Does anybody have an implementation of this or know how to code it?? It's driving me nuts!!!

Cheers,
Sean

alcdotcom

I could give you an answer, but you'll learn better if I just give you a hint and let you figure it out from there. So, to that end: try a nested for loop. In other words, have a for loop inside of a for loop. If you continue to have problems, come back and post your attempted solution.

__________________
Java Blog

smg1001

Thanks for the reply. Ok, here's what I have. It works but only for an array size of 3:

for(int i = 0; i < g.length; i++) {
for(int j = 0 ; j < g.length; j++) {
for(int k = 0; k < g.length; k++) {
if( (h[i] + h[j] + h[k] == 6) && (i != j) && (j != k) ) {
System.out.println("A = " + h[i] + " i = " + i);
System.out.println("B = " + h[j] + " j = " + j);
System.out.println("C = " + h[k] + " k = " + k);
System.out.println();
numPrinted++;
}
count++;
}
}
}

where h[3] = {1, 2, 3} and g.length = 3

Arevos

If you want to be able to do it with any array size, I suspect you would do best with a recursive method.

Are you familiar with recursion?

smg1001

I am, here's what I have:

public static void group(int i, int j) {

if(i < g.length) {
System.out.println(g[i] + " = " + h[j]);

i = i + 1;
j = j + 1;
group(i, j);
}
else {
//System.exit(0);
return;
}

}

I know it's not right. I was going to build from this but I've been looking at it for ages and I don't know where to go from here.

Arevos

Recursion is terribly tricky, and it takes a while to wrap your head around it. I completely messed up my functional programming coursework back when I was in my first year as an undergrad. The way I found of dealing with it is to take it one step at a time.

Recusion at it's basics is a function that calls itself, as you very well know:
Where a and b are your arrays.

But on it's own, this is no good at all. You need something to limit the recursion. What is the limiting factor with your group method? What stops it from continuing on forever?

The answer is the size of your arrays. Because your arrays are of finite size, you'll get back an answer of finite length.

Any limiting factor must eventually reach zero. When the limiting factor is at zero, then you've reached the greatest depth of recursion.

Take this method:
This piece of code takes in an array. It takes the head of the array, element 0, and adds it onto the tail of the array, elements 1 and above. Each time the method recurses, it reduces the array's length by one. When the size of the array is 0, the method stops recursing.

Think about that, and see if it helps any.

smg1001

I traced through the recursion with input 1,2,3,4 (see below). I don't know how this can be used to solve my problem, I'll have to keep looking at it. Any more hints are appreciated ;-)


1st iteration:
==========

head = 1
tail = int[3];
tail = {2, 3, 4}

return 1 + ...

2nd iteration:
==========

head = 2
tail = int[2]
tail = {3, 4}

return 2 + ...

3rd iteration:
==========

head = 3
tail = int[1]
tail = {4}

return 3 + ...

4th iteration:
==========

head = 4
tail = int[0]
tail = {}

return 4 + 3 + 2 + 1 = 10

smg1001

So I see now that this recursion gives me the number of iterations I need, i.e. the size of the array.

smg1001

This code above gives me the pattern:

1 2 3 4
2 3 4
3 4
4

I understand it gives me the correction number of iterations. Can anyone tell me how this helps me achieve the pattern I described at the beginning of this thread?

Sean

Arevos

Well, this isn't an easy problem, so don't get discouraged

Take it one step at a time. You have two arrays, a and b each of size n. You want to create every possible combination of the two. So let's walk through what you need to do to create a single combination.

You start off with a[0], and you have n possibilities. You can have a[0]b[0], a[0], a[0]b[1] all the way up to a[0]b[n].

For a[1] you can use any number except for the one you used for a[0]. So you have n-1 possibilities. At a[2] you have n-2 possibilities, at a[3] you have n-3 possibilities and so on.

This continues until you are at a[n - 1], the last element of a. You're also at the last element of b, so there's only one possibility left to you. At this point, you have all the elements in the sequence, which you can print to the screen.

So your limiting condition is when a and b have only one element each. And at this point, you can print out your sequence.

With recursion, you can pass data one of two ways. You can pass it from the bottom of the recursion to the top via a return value. Or you can pass it from the top to the bottom via a parameter. Because we want to print out the sequence at the bottom of the recursion stack, we need to use an extra parameter to pass data down:

I should also mention that using a List would be a good idea, since a List object is of variable size, so you can add and remove elements. A plain array is of fixed size, so you have to create a new array everytime you want to reduce or increase it's size. Not too convenient!

You can use Arrays.asList to convert an array into a list: