在C中创建n个项目的k和m组合的所有可能子集

我正在为我的问题寻找解决方案:我必须编写一个代码来计算独特元素的组合,即n个元素的所有不同组合被选为k元素组并重新计算剩余子集的新组合而不复制。 给定S,所有可能的唯一元素的集合,我必须计算S的元素的唯一组合的子集T,现在我必须重新计算新的子集 – V – T的组合并且所有子集T和V必须是独特:

For example I have this set S: {0, 1, 2, 3, 4} 

我必须得到

 a {0, 1} {2, 3} { 4} b {0, 1} {2, 4} { 3} c {0, 1} {3, 4} { 2} d {0, 2} {1, 3} { 4} e {0, 2} {1, 4} { 3} f {0, 2} {3, 4} { 1} g {0, 3} {1, 2} { 4} h {0, 3} {1, 4} { 2} i {0, 3} {2, 4} { 1} j {0, 4} {1, 2} { 3} k {0, 4} {1, 3} { 2} l {0, 4} {2, 3} { 1} discarded as the same as g -> {1, 2} {0, 3} { 4} discarded as the same as j -> {1, 2} {0, 4} { 3} m {1, 2} {3, 4} {0} discarded as the same as d -> {1, 3} {0, 2} { 4} discarded as the same as k -> {1, 3} {0, 4} { 2} n {1, 3} {2, 4}{ 0} discarded as the same as e -> {1, 4} {0, 2} { 3} discarded as the same as h -> {1, 4} {0, 3} { 2} o {1, 4} {2, 3}{0} discarded as the same as a -> {2, 3} {0, 1} { 4} discarded as the same as l -> {2, 3} {0, 4} { 1} discarded as the same as o -> {2, 3} {1, 4} { 0} discarded as the same as b -> {2, 4} {0, 1} { 3} discarded as the same as i -> {2, 4} {0, 3} { 1} discarded as the same as n -> {2, 4} {1, 3} { 0} discarded as the same as c -> {3, 4} {0, 1} { 2} discarded as the same as f -> {3, 4} {0, 2} { 1} discarded as the same as m -> {3, 4} {1, 2} { 0} 

组合{1,2} {0,3} {4}与{0,3} {1,2} {4}的(对于此问题)相同,然后必须被丢弃,{1, 2} {0,4} {3}和{0,4} {1,2} {3}。

是否有可能在不使用考虑已经获得的组合的数据结构(作为列表)的情况下达到目标?

我需要这样的东西: 生成组合:1

它与先前的问题不重复,因为研究涉及必须被认为是单义的分区,即它们中包含的元素(无论其顺序如何)在先前的细分中必须不是已经同意的,例如{1,2} {0,4} {3}和{0,4} {1,2} {3}必须被视为非唯一,因此只有一个组合有效:{0,4} {1,2} {3}

它比我初步想象的更棘手。

好吧,那么就说你有“n”uniq元素。 uniq可能性的总量是“n!” (因此对于5个元素,你有120个可能性)。

假设您要制作“k”数字的“组”。

因此,如果n = 5且k = 2,您最终会得到您的示例:

{0,1},{2,3},{4}。

现在,这就是乐趣开始的地方:为了了解当前命题是否重复,您可以放弃每个完整组中第一个数字未排序的每个命题。

例如 :

{0,1},{2,3},{4}。

这里,1和3是无用的,因为它不是完整组的第一个值,而4是不完整组的一部分。 有趣的是

{ 0 ,?},{ 2 ,?},{?}。

0,2排序? 是的,所以你可以保留这个主张。 这意味着,如果你有

{2,3},{0,1},{4}。

这不好,因为

{ 2 ,?},{ 0 ,?},{?}。

2,0没有排序。


如果你有n = 6和k = 2,那么是

{0,2},{3,4},{1,5}

有效吗? 不,因为0 3 1没有排序。 你可以看到

{0,2},{1,5},{3,4}

是有效的排序命题。


现在,如果我们知道n和k,是否有可能计算出我们将拥有多少有效命题?

是。

也许。 我想……如果我能找到一些东西,我会更新。

编辑:

Aaaaaannnd,这里是一个实现。 有点乐趣…它基于以前的算法,所以当然如果我的算法是假的,那么这个代码是错误的。

 #include  #include  #include  #define N 5 #define K 2 void Comb_Display(int proposition[N]) { printf("{"); for (int i = 0; i < N; ++i) { if (i && i % K == 0) { printf("} {"); } printf("%d%s", proposition[i], (i && (i + 1) % K == 0) || i + 1 >= N ? "" : ", "); } printf("}\n"); } bool Comb_Valid(int proposition[N]) { int nbGroup = N / K; if (nbGroup == 1) { return (true); } for (int i = 0; i < nbGroup; i += K) { if (proposition[i] > proposition[i + K]) { return (false); } } return (true); } void Comb_MakeMagicPlease(int numberAvailable[N], int proposition[N], int ind) { // We are at the end of the array, so we have a proposition if (ind >= N) { printf("%s : ", Comb_Valid(proposition) ? "OK" : " "); // O = Valide, ' ' = invalide Comb_Display(proposition); return; } // We scan "numberAvailable" in order to find the first number available for (int i = 0; i < N; i++) { if (numberAvailable[i] != -1) { int number = numberAvailable[i]; numberAvailable[i] = -1; // We mark the number as not available proposition[ind] = number; Comb_MakeMagicPlease(numberAvailable, proposition, ind + 1); numberAvailable[i] = number; // we mark the number as available } } } int main(void) { int numberAvailable[N]; int proposition[N]; for (int i = 0; i < N; ++i) { numberAvailable[i] = i + 1; } Comb_MakeMagicPlease(numberAvailable, proposition, 0); return 0; } 

是。

在这种情况下,请确保结果已排序。 这样,您只需输出一个已排序的版本,而无需检查是否已获得该组合。

您也可以使用它来加速生成。 即选择{1,2}后,尝试以0开头的任何内容都没有意义,所以你可以跳过这些。