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

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

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

问题陈述：
给定两个大小为 n 的向量 A，大小为 m 的 B，其中 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;
    }
};

Answer 3

非常简单的方法是

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

Answer 4

当我看到一个填字游戏风格的谜题时，我研究了这个挑战，其中每个方块都有一个数字，你必须找到哪个字母对应于哪个数字才能使单词正确。知道我正在接触已经给出的答案，我将尝试总结问题，并展示如何递归地解决它。

在 x-word 的情况下，较小的数组 A 是一系列数字，而较大的数组 B 包含字母表中的字母。问题是将每个数字分配给一个字母，并找到所有可能的组合。一般来说，我们有：

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

每个可能的结果都可以写成一个包含 m 个元素的数组 C，其中元素 i 带有值 j，对于 A(i)B(j) 对。排列的总数，即 C 数组，是 n(n-1).....(n-m+1) 或更简洁的写法：n!/(m+1)!

这个数字是根据这样的想法得出的：当 A 的第一个元素与 B 中的任何元素配对时，A 的第二个元素可以与任何元素配对，除了第一个元素所采用的元素之外，等等。

我们可以通过以下伪代码来实现这一点：

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

为了直观起见，我使用基于 1 的数组。

这段代码不适用于任意长度的 A，并且对于大的 m 来说编写起来会很麻烦，因此我们最好使用可以调用自身的过程 AllPairs 来递归：

   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

请注意，C 最初是一个与 A 大小相同的空数组（也可以是 A 的副本）。 C 保持相同大小，而 A 和 B 依次减小，直到 A 只剩下一个元素，递归调用结束。这样就可以了。也许（恕我直言）这与郑金吉的代码答案类似 - （我不能告诉）。我的目的是尝试提供一个简单直观的伪代码版本。可以在此处找到该解决方案在 VB 中的实现。

Answer 5

它不完全相同的问题，但我对以下问题做了一个解决方案，这可能是一个不错的起点：

数组组合数组

Answer 6

本网站上有很多关于两个列表的组合的问题（和答案）（参见侧边栏）。如果我理解正确的话，你的用例看起来只是表面上的不同。

是否就足够了

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

拥有一个方法（它以各种形式和大小存在于“重复项”中）然后按照以下步骤使用它（家庭作业=您填写详细信息）

：迭代列表 1 和 的所有组合;列表 2 （使用类似于上面的内容）和

• 按当前组合的第一个元素过滤列表 1
• 按当前组合的第二个元素过滤列表 2
• 将当前组合与过滤列表的所有可能组合组合（使用类似以下方法的内容）多于）

Answer 7

如果我正确理解你的问题，所有组合都可以导出：

• 从 A 中选择 2 个不同的元素 {A_i, A_j}，
• 从 A 中选择 2 个不同的元素 {B_k, B_l} B，
• 用这些元素 { (A_i, B_k), (A_j, B_l) }, { (A_i, B_l), (A_j, B_k) } 进行 2 种组合。

通过 A 和 B 的 2 个元素子集的所有组合，您可以获得您正在寻找的所有组合。

有|A| * (|A| - 1) * |B| * (|B| - 1) / 2 组合。

简单的实现是通过 4 个循环：

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