Creating all possible subset of k and m combinations of n items in C [duplicate]

Question

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}

Ransack

I may be mistaken, but in your example, you give 24 possible result for the unique combinaison of 5 element. Isn't normally 120 results ? where is {2, 1} {0, 3} {4} ? Also, is T subset's value mandatory paired ? It can't be {0, 1, 2}{3, 4} ? Could you give a complete exemple for 3 and 4 element in S ? – Camphor

@Tom's {2, 1} {0, 3} {4} is not present beacuse different orders (inside a set) are considered to be the same combination, so {2, 1} {0, 3} {4} is the same of {0, 3} {1, 2} { 4}. T isn't mandatory paired, it is paired in this example. – Ransack

So, each "combination" is an unordered set of n/k unordered sets of k elements each, and one unordered set of n%k elements, all unique elements within each entire "combination", taken from a set of n unique elements, with k fixed. Sounds very much like a grouping problem (a subtype of combinatorics problems) to me. Interesting.. – Linseed

rosettacode.org/wiki/Combinations#C – Dorsad

@Dorsad thanks for the suggestion, but the recursive code does not do exactly as required, and the non recursive code at the end crash in a segmentation fault – Ransack

Answer 1

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;
}

Oar

If you have a new question, please ask it by clicking the Ask Question button. Include a link to this question if it helps provide context. - From Review – Voice

Thanks for the info, I will keep it in mind, but it's more an open question than a real question. – Camphor

@Oar Thanks for your code but it have a mistake, it returns OK : {1, 5} {2, 3} {4} and {2, 3} {5, 1} {4} as "OK" value, but actually they are the same value, so only none ca be "OK" – Ransack

Then you just have to modify the "Comb_Valid" function in order to check if each subset {., ., .} is internally sorted. Why sorted ? Because if we have the element "a, b, c" for a subnet, then you can have 6 subnet : abc, acb, bac, bca, cab, cba. How can we keep only one ? Well, we can see that only one is "sorted" (abc) when the 5 other aren't sorted. That's the same principle for the group of subnet. So, now that you know that each subnet can be keep or not depending on the fact that there are sorted or not, why not giving a try ? – Camphor

@Tom's, could you update your code ? – Ransack

Uuuuh, no. I nearly do all the code and I gived you all the algorithm. SO is not www.do_my_code.com. The only reason I for what I have do the code is because your problem is really interesting. Now, you just have to modify the "Comb_Valid" function. K is the length of a subset, and you have to add a check an each subset. Give it a try, and if it's not working, update your question in order to reflect what you have done. It's nothing more than an extra for-loop by the way. – Camphor

Answer 2

Yes.

In this case make sure the result is sorted. This way you only output the one sorted version without having to check if the combination has already been obtained.

You can also use this to speed up the generation. I.e. After selecting {1,2} there's no point in trying anything that starts with 0, so you can just skip those.

Sliver

Could you help me with an algorithm or code in C ? – Ransack