c# - Finding all possible value combinations between two arrays

Question

I have two arrays of strings, not necessarily of the same length, I want to find all the possible "sets" of combinations between two values from the arrays, without repeats from either array.
For example, given the arrays:
{ "A1", "A2", "A3" }
{ "B1", "B2" }
The result I want is the following sets:
{ ("A1", "B1"), ("A2", "B2") }
{ ("A1", "B1"), ("A3", "B2") }
{ ("A1", "B2"), ("A2", "B1") }
{ ("A1", "B2"), ("A3", "B1") }
{ ("A2", "B1"), ("A3", "B2") }
{ ("A2", "B2"), ("A3", "B1") }

My general direction is to create recursive function that takes as a parameter the two arrays and removes each "chosen" strings at a time, calling itself until either array is empty, however I'm kinda worried about performance issues (I need to run this code on about a 1000 pairs of string arrays).
Can anyone direct my towards an efficient method to do this?

Answer 1

It might be beneficial to think of the two arrays as sides of a table:

        A1      A2      A3
---+-------+-------+-------+
B1 | B1,A1 | B1,A2 | B1,A3 |
---+-------+-------+-------+
B2 | B2,A1 | B2,A2 | B2,A3 |
---+-------+-------+-------+

This implies a loop nested within another, one loop for the rows and the other for the columns. This will give you the initial set of pairs:

{B1,A1} {B1,A2} {B1,A3} {B2,A1} {B2,A2} {B2,A3}

Then it is a matter of building up the combinations of that initial set. You can visualise the combinations similarly, with the set of pairs for both the rows and columns:

      B1,A1 B1,A2 B1,A3 B2,A1 B2,A2 B2,A3
-----+-----+-----+-----+-----+-----+-----+
B1,A1|     |  X  |  X  |  X  |  X  |  X  |
-----+-----+-----+-----+-----+-----+-----+
B1,A2|     |     |  X  |  X  |  X  |  X  |
-----+-----+-----+-----+-----+-----+-----+
B1,A3|     |     |     |  X  |  X  |  X  |
-----+-----+-----+-----+-----+-----+-----+
B2,A1|     |     |     |     |  X  |  X  |
-----+-----+-----+-----+-----+-----+-----+
B2,A2|     |     |     |     |     |  X  |
-----+-----+-----+-----+-----+-----+-----+
B2,A3|     |     |     |     |     |     |
-----+-----+-----+-----+-----+-----+-----+

Again this can be accomplished with a pair of nested loops (hint: your inner loop's range will be determined by the outer loop's value).