我有集合 S1 = {s11,s12,s13), S2 = {s21,s22,s23) 等等直到 SN。我需要生成所有包含 S1,S2..SN 元素的排列.. 这样每个集合中只有 1 个元素。
例如:
S1 = {a,b,c}
S2 = {d,e,f}
S3 = {g,h,i}
我的排列是:
{a,d,g}, {a,d,h}, {a,d,i}, {a,e,g}, {a,e,h}....
我该怎么做? (我可以随机地从每个中挑选 1 个并合并它们,但即使在我看来这也是一个坏主意)。
为了一般性,假设每个集合中有“n”个元素。我正在考虑用 C 实现它。请注意“N”和“n”不是固定的。
最佳答案
这只是递归的问题。让我们假设这些定义。
const int MAXE = 1000, MAXN = 1000;
int N; // number of sets.
int num[MAXN]; // number of elements of each set.
int set[MAXN][MAXE]; // elements of each set. i-th set has elements from
// set[i][0] until set[i][num[i]-1].
int result[MAXN]; // temporary array to hold each permutation.
函数是
void permute(int i)
{
if (i == N)
{
for (int j = 0; j < N; j++)
printf("%d%c", result[j], j==N-1 ? '\n' : ' ');
}
else
{
for (int j = 0; j < num[i]; j++)
{
result[i] = set[i][j];
permute(i+1);
}
}
}
要生成排列,只需调用 permute(0);
关于c - 枚举一组子集的排列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1550144/