c - 枚举一组子集的排列

标签 c set permutation

我有集合 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/

相关文章:

algorithm - 生成没有排列的序列

c - 在结构中设置数组值在结构中设置不同的字段

html - 通过 c/cgi-bin/html 显示密码字段和下一步按钮。我希望当屏幕显示时焦点位于密码字段中

c++ - 如何从命令行运行 Eclipse IDE for C/C++(我已经安装了)

C++ 遍历集合

algorithm - 如何使用 Factoradic 系统获取或取消排名 K-th 排列与重复项目

html - 在 C 中使用 CGI 将 HTML 表单数据文件上传到服务器?

python - 无法弄清楚导致 IOError 的原因是什么

algorithm - 根据许多不完整的有序集恢复原始顺序

JavaScript - 从具有 m 个元素的 n 个数组生成组合