Finding all possible value combinations between two arrays

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?

---

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

---

Your problem is equivalent to the following problem:

Problem Statement:
Given two vectors A with size n, B with size m, where n <= m.
A = [0, 1, 2, ..., n - 1].
B = [0, 1, 2, ..., m - 1].
Find all possible injective and non-surjective mappings from A to B.

Solution:
As the size of A is smaller, in one mapping, the number of correspondences is equal to the size of A, i.e., n.

Then we generate all the possible permutations of B, so that the beginning n elements in each permutation can have an one to one correspondence with the elements in A.

The first several permutations and mappings go as follows:

Implementation:

class Helper {
public:
    /**
     * @brief generateArray
     * @param size
     * @return A vector [0, 1, ..., size - 1]
     */
    vector<int> generateArray(int size) {
        vector<int> arr;
        for (int i = 0; i < size; ++i) {
            arr.push_back(i);
        }
        return arr;
    }

    /**
     * @brief generateMatches
     * @param n, cardinality of the vector X, where X = [0,1, ..., n - 1].
     * @param m, cardinality of the vector Y, where Y = [0,1, ..., m - 1].
     * @return All possible injective and non-surjective mappings 
     * from the smaller vector to the larger vector.
     */
    vector<vector<pair<int, int> > > generateMatches(int n, int m) {
        // Deal with n > m. Swap back when generating pairs.
        bool swapped = false;
        if (n > m) {
            swapped = true;
            swap(n, m);
        }
        // Now n is smaller or equal to m
        vector<int> A = generateArray(n);
        vector<int> B = generateArray(m);
        vector<vector<pair<int, int> > > matches;
        // Generate all the permutations of m
        do {
            vector<pair<int, int> > match;
            for (int i = 0; i < n; ++i) {
                pair<int, int> p;
                if (swapped) {
                    // Swap back to the original order.
                    p = make_pair(A[i], B[i]);
                } else {
                    p = make_pair(B[i], A[i]);
                }
                match.push_back(p);
            }
            matches.push_back(match);
                // Generate next permutation.
        } while(next_permutaion(B.begin(), B.end())); 
        return matches;
    }
};

---

very simple way is

string[] arr = new string[3];
        string[] arr1 = new string[4];
        string[] jointarr = new string[100];

        for (int i = 0; i < arr.Length; i++)
        {
            arr[i] = "A" + (i + 1);
        }

        for (int i = 0; i < arr1.Length; i++)
        {
            arr1[i] = "B" + (i + 1);
        }

        int k=0;
        for (int i = 0; i < arr.Length; i++)
        {
            for (int j = 0; j < arr1.Length; j++)
            {
                jointarr[k] = arr[i] + " " + arr1[j];
                k++;
            }
        }

---

I looked into this challenge when I saw a crossword style puzzle where each square has a number, and you have to find which letter corresponds to which number in order to make the words correct. Knowing I'm touching answers already given, I'll try to summarize the problem, and show how it can be solved recursively.

In the x-word case, the smaller array A is a series of numbers, and the large array B contains the letters of the alphabet. The problem is to assign each number to a letter, and to find all possible combinations. Generally we have:

A={1,2,...m} and B={1,2,....n}     n>=m

Each possible result can be written as an array C with m elements, where element i carry the value j, for the pair A(i)B(j). The total number of permutations, i.e. C-arrays, is n(n-1).....(n-m+1) or more neatly written: n!/(m+1)!

This number follows from thinking that when the first element of A is paired with any of the elements in B, the second element of A can be paired with any element except the one that was taken by the first one, and so on and on.

We can achieve this with following pseudo-code:

for i= 1 to n
   C(1)=B(i)
   for j= 1 to n-1
      C(2)=B'(j)        '  B' is B with element i removed
         .........
          for x = 1 to n-m
             C(m)=B'''(x)   'B is now reduced with (m-1) elements
          next x

I use 1-based arrays for intuitivity.

This code would not work for arbitrary length of A, and would be cumbersome to write for large m, so we better make this recursive with a procedure AllPairs, that can call itself:

   AllPairs (A,B,C)
    if Size(A)>1             ' check no of elements in A        
      for i=1 to Size(B)
       C(Size(C)-Size(A)+1)= B(i)
       A'=Remove element 1 from A
       B'=Remove element i from B
       Call AllPairs(A',B',C)     'recursive call
      Next i
    else                          ' only one element in A
      for j=1 to Size(B)
      C(Size(C)) = B(i)  'looping last element in C through all unused in B
      Collect.ADD(C)      'collect C-arrays here for later use
      Next j                 
  End AllPairs

Note that C initially is an empty array with same size as A (could as well be a copy of A). C remains the same size, while A and B are succesively reduced, until A contains only one element, and the recursive calling ends. This would do it. Perhaps (with all respect) this is similar to the code Jingie Zheng's answer - (I can't tell). My intent here is to try to give an easy intuitive pseudocode version. This solution can be found implemented in VB here.

---

Its not quite the same problem, but there's a solution I did to the following question that would probably be a decent start point:

Array of array combinations

---

There are lots of questions (and answers) regarding combinations of two lists on this site (see sidebar). Your use case seems only superficially different if I understand it correctly.

Wouldn't it suffice to have a method

IEnumerable<Tuple<string, string>> Combinations(
  IEnumerable<string> list1, 
  IEnumerable<string> list2) {}

(which exists in various forms and sizes already in the 'duplicates') and then use that by following these steps (homework = you fill in the details):

Iterate over all combinations of list 1 & list 2 (using something like the above) and

• Filter list 1 by the first element of the current combination
• Filter list 2 by the second element of the current combination
• Combine the current combination with all possible combinations of the filtered lists (using something like the method above)

---

If I understand your problem correctly, all combinations can be derived with:

• chose 2 different elements {A_i, A_j} from A,
• chose 2 different elements {B_k, B_l} from B,
• make 2 combinations with these elements { (A_i, B_k), (A_j, B_l) }, { (A_i, B_l), (A_j, B_k) }.

With all combinations of 2 element subsets from A and B, you get all combinations you are looking for.

There are |A| * (|A| - 1) * |B| * (|B| - 1) / 2 combinations.

Easies implementation is with 4 loops:

for i = 1 ... |A|
  for j = i+1 ... |A|
    for k = 1 ... |B|
      for l = k+1 ... |B|
        make 2 combinations {(A_i, B_k),(A_j, B_l)}, {(A_i, B_l), (A_j, B_k)}