查找两个数组之间的所有可能值组合

Question

我有两个字符串数组,不一定长度相同,我想找到数组中两个值之间所有可能的"组合"组合,而不是从任何一个数组重复.
例如,给定数组:
{"A1","A2","A3"}
{"B1","B2"}
我想要的结果是以下几组:
{("A1","B1"),( "A2","B2")}
{("A1","B1"),("A3","B2")}
{("A1","B2"),("A2","B1") }
{("A1","B2"),("A3","B1")}
{("A2","B1"),("A3","B2")}
{("A2"," B2"),("A3","B1")}

我的总体方向是创建递归函数,将两个数组作为参数并一次删除每个"选定"的字符串,调用自身直到任一个数组为空,但我有点担心性能问题(我需要运行这个大约1000对字符串数组的代码).
任何人都可以指导我做一个有效的方法吗？

Answer 1

将两个数组视为表的一侧可能是有益的:

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

这意味着一个循环嵌套在另一个循环中,一个循环用于行,另一个循环用于列.这将为您提供一组初始对:

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

然后是建立初始集的组合的问题.您可以使用行和列的成对集来类似地可视化组合:

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

同样,这可以通过一对嵌套循环来完成(提示:您的内循环的范围将由外循环的值确定).

Answer 2

您的问题相当于以下问题：

问题陈述：
给定两个向量A，大小n，B与大小m，其中n <= m。
A = [0, 1, 2, ..., n - 1].
B = [0, 1, 2, ..., m - 1].
查找所有可能的 射和非满射映射，从A到B。

解：
由于A的尺寸较小，在一次映射中，对应的个数等于A的尺寸，即n。

然后我们生成 B 的所有可能的排列，使得每个排列中开始的 n 个元素可以与 A 中的元素一一对应。

前几个排列和映射如下：

执行：

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