如何获得字符串数组的组合

本文关键字：组合 数组 字符串 何获得 | 更新日期: 2023-09-27 18:24:17

可能重复：
生成所有可能的组合

我正在尝试用C++或C#做一个小算法

基本上，如果你有一个阵列：

{"ab","cd"}

输出：

ac
ad
bc
bd

（我有两个嵌套的循环）

但是如果我有一个3个元素的数组呢？还是4？

谢谢大家：）

如何获得字符串数组的组合

您正在寻找任意多个字符序列的笛卡尔乘积。查看此博客文章：

http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx

还有这个StackOverflow问题，你已经重复了。

生成所有可能的组合

为了改变"嵌套循环"的数量，需要使用递归。

void printCombination(string[] str, string partial, int p) {
    if (p == str.Length) {
        Console.WriteLine(partial);
        return;
    }
    for (int i = 0 ; i != str[p].Length; i++) {
        printCombination(str, partial + str[p][i], p+1);
    }
}

初始调用如下：

printCombination(new[] {"ab", "cd", "ef", "gh"}, "", 0);

编辑（针对OP的评论）

要了解发生了什么，首先需要了解参数的含义：

  • str是字符串的数组。数组的每个元素对应于假想嵌套循环的嵌套级别：元素0用于外循环，元素1用于第一级嵌套，依此类推
  • partial是部分构造的结果字符串。它在初始级别为空，在嵌套的第一级别有一个字符，在第二级别有两个字符，依此类推
  • p是嵌套级别。它在初始级别为零，在第一个嵌套级别为一，依此类推

函数有两个部分——停止条件和递归调用的主体。停止条件很简单：一旦我们到达最后一个级别，partial的结果就不再是"部分的"：它是完整的；我们可以打印出来然后退出。我们怎么知道我们已经到了最后一关？str的元素数量等于级别数量，所以当p等于str数组的长度时，我们就完成了。

递归调用的主体是一个循环。它做的事情和嵌套循环做的一样，但只针对一个级别：每个迭代从自己的数组中添加一个字母，并在下一级别递归调用自己。

看到这一点的最佳方法是在带有return语句的行上设置一个断点，并查看调用堆栈窗口。单击每个调用级别，并检查函数参数的值。

如果您要进行练习，请尝试修改此函数以使用两个参数而不是三个参数。提示：您可以通过观察partial的长度始终与p的值匹配来消除最后一个参数。

在c++中有一个算法叫做std::next_permutation。这里有一个例子，希望对你有所帮助。

#include <algorithm>
#include <string>
#include <iostream>
int main()
{
    std::string s = "aba";
    std::sort(s.begin(), s.end());
    do {
        std::cout << s << ''n';
    } while(std::next_permutation(s.begin(), s.end()));
}

Output:
aab
aba
baa

然后您不能使用嵌套for循环，因为您不能通过编程改变它。

在这种情况下，为每个元素使用一个计数器，它是您正在迭代的当前元素。使用while循环和函数来检查是否已完成。

增加第一个元素的计数器，如果已达到最大值，则将其设置为0，并增加下一个计数器等。

（编辑：使用排列的解决方案可能在内部使用了我的解决方案）。

相关文章：