创建C中n项的k和m组合的所有可能子集 [英] Creating all possible subset of k and m combinations of n items in C
问题描述
我正在寻找解决问题的方法：
我必须编写代码来计算唯一元素的组合，即选择n个元素的所有不同组合作为k个元素的
组并重新计算没有复制的其余子集的新组合。
给定S，所有可能的唯一元素的集合，我必须计算S元素的唯一组合的子集T，现在我有
来重新计算T和T的组合的新子集-V-所有子集T和V必须唯一：
例如，我有以下集合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}
与g-> {1，2} {0，3} {4}
与j-> {1，2} {0，4} {3}
m {1，2} {3，4} {0}
与d相同-> {1，3} {0，2} {4}
与k->相同被丢弃。 {1，3} {0，4} {2}
n {1，3} {2，4} {0}
与e-> {1，4} {0，2} {3}
与h-> {1，4} {0，3} {2}
o {1，4} {2，3} {0}
与->相同{2，3} {0，1} {4}
与l->相同被丢弃。 {2，3} {0，4} {1}
被丢弃，与o->相同。 {2，3} {1，4} {0}
与b->相同被丢弃。 {2，4} {0，1} {3}
与i-> {2，4} {0，3} {1}
与n->相同被丢弃。 {2，4} {1，3} {0}
与c-> {3，4} {0，1} {2}
与f-> {3，4} {0，2} {1}
与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，我们将有答案。
是的。
也许。
我认为...
如果可以找到某些东西，我会进行更新。
编辑：
aaaaannnd，这里是一个实现。有趣的事...
它基于以前的算法，因此，如果我的算法为假，则此代码为假。
#include< stdio.h>
#include< stdlib.h>
#include< string.h>
#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，命题[i]，（i&（i + 1）％K == 0）|| i + 1> = N吗？ ：，）;
}
printf（} nn）;
}
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（true）;
}
void Comb_MakeMagicPlease（int numberAvailable [N]，int proposition [N]，int ind）
{
//我们在数组的结尾，因此我们有一个命题
if（ind> = N）{
printf（％s：，Comb_Valid（proposition）？ OK：）; // O = Valide，‘’= invalide
Comb_Display（proposition）;
的回报；
}
//我们扫描 numberAvailable，以找到第一个可用的
可以用于（int i = 0; i< N; i ++）{
if（numberAvailable [i]！= -1）{
int number = numberAvailable [i];
numberAvailable [i] = -1; //我们将数字标记为不可用
命题[ind] =数字；
Comb_MakeMagicPlease（numberAvailable，proposition，ind + 1）;
numberAvailable [i] =数字； // //将数字标记为可用
}
}
}
int main（void）
{
int numberAvailable [N] ;
int命题[N];
for（int i = 0; i< N; ++ i）{
numberAvailable [i] = i + 1;
}
Comb_MakeMagicPlease（numberAvailable，proposition，0）;
返回0；
}
I looking for a solution for my problem: I have to write a code which calculates a combination of unique elements, that is all different combinations of n elements chosen as group of k elemets and recalculate the new combination of the remain subset without replication. Given S, the set of all possible unique elements, I have to calculate a subset T of unique combination of elements of S, now I have to recalcuate a new subset - V - of combination of T and all the subset T and V must be unique:
For example I have this set S: {0, 1, 2, 3, 4}
I have to obtain
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}
The combination {1, 2} {0, 3} { 4} as the same of (for this question) of {0, 3} {1, 2} { 4} and then must be discarded, the same for {1, 2} {0, 4} { 3} and {0, 4} {1, 2} { 3}.
Is it possible to reach the goal without using a data structure (as a list) that takes into account the combinations already obtained ?
I need something like this: Generating Combinations: 1
It is not a duplicate of previous question, because the research involves partitions that must be considered univocal, ie the elements contained in them (regardless of their order) must not have already been consensual in a previous subdivision so for example {1, 2} {0, 4} { 3} and {0, 4} {1, 2} { 3} must be considered non-unique, and therefore only a combination is valid: {0, 4} {1, 2} { 3}
It's more trickier than I primarly thinked.
Okay, so lets say you have "n" uniq element. The total amout of uniq possibility is "n!" (so for 5 element, you have 120 possibility).
Let's say you want to make "group" of "k" number.
So if n = 5 and k = 2, you end up with your example :
{0, 1}, {2, 3}, {4}.
Now, that's where the fun begin : In order to know if the current proposition is not a duplicate, you can discard every proposition for which the first number in every complete group is not sorted.
for example :
{0, 1}, {2, 3}, {4}.
here, 1 and 3 are useless because that not the first value of a complete group, and 4 is part of an incomplete group. So what is interesting is
{0, ?}, {2, ?}, {?}.
Is 0, 2 sorted ? Yes, so you can keep this proposition. That means that if you have
{2, 3}, {0, 1}, {4}.
It's no good, because
{2, ?}, {0, ?}, {?}.
2, 0 is not sorted.
If you have n = 6 and k = 2, then is
{0, 2}, {3, 4}, {1, 5}
valid ? No, because 0 3 1 is not sorted. And you can see that
{0, 2}, {1, 5} , {3, 4}
is the valid sorted proposition.
Now, is there a possibility to calculate how many valid proposition we will have if we know n and k ?
Yes.
Maybe. I think ... I will update if I can found something.
Edit :
Aaaaaannnd, here an implementation. A little fun to do ... It based on the previous algorithm, so of course if my algorithm is false, then this code is false.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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;
}
这篇关于创建C中n项的k和m组合的所有可能子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
