Finding all possible value combinations between two arrays

15,475

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

Solution 2

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. One possible injective and non-surjective mapping

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: Permutation 1 Permutation 2 Permutation 3 Permutation 4

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;
    }
};

Solution 3

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++;
            }
        }

Solution 4

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.

Share:
15,475
JohnoBoy
Author by

JohnoBoy

Updated on June 28, 2022

Comments

  • JohnoBoy
    JohnoBoy almost 2 years

    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?

  • JohnoBoy
    JohnoBoy almost 13 years
    While this will give me all possible string pairs, what I need is the unique combinations of these pairs
  • Jingjie Zheng
    Jingjie Zheng almost 9 years
    To my understanding, using a pair of nested loops cannot generate the complete set without the assumption that one of the initial two arrays has a length of two. A more sensible manner of solving this problem in general is to use depth-first search.
  • Jingjie Zheng
    Jingjie Zheng almost 9 years
    Another solution is to fix the order of the smaller array, generate all the permutations of the longer, and make a match with the same index of the two arrays to the length of the smaller array.
  • Jingjie Zheng
    Jingjie Zheng almost 9 years
    Please see my answer for clarifications.
  • Paul Ruane
    Paul Ruane almost 9 years
    @JingjieZheng The two initial arrays can be any length. You can visualise this by adding rows/columns to the table as appropriate.