Create all possible subsets of k and m combinations of n terms in C

This is a lot harder than I initially thought.

Ok, let's say you have "n" uniq elements. The sum of the uniq possibilities is "n!". (so for 5 elements you have 120 possibilities).

Say you want to "group" "k" numbers.

So if n = 5 and k = 2, you will get the example:

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

Now, here's where the fun begins: in order to know if the current proposition is not a duplicate, you can discard every proposition that doesn't sort the first number in each complete group .

E.g:

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

Here, 1 and 3 are useless because it is not the first value of a complete group, and 4 is part of an incomplete group. So it's interesting

{ 0，？}，{ 2，？}，{？}。

Is it sorted by 0 and 2? Yes, so you can keep this claim. This means that if you have

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

bad because

{ 2，？}，{ 0，？}，{？}。

2, 0 are not sorted.

If n = 6 and k = 2, then

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

Does it work? No, because 0 3 1 is not sorted. you can see

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

is a valid ordering proposition.

Now, if we know n and k, how many valid propositions is it possible to calculate?

Yes.

Maybe. I think...I'll update if I can find it.

edit:

Aaaaaannnd, here is an implementation. Do something fun. It's based on the previous algorithm, so if my algorithm is false, 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;
}