/* Enumeration of k combinations on base set with n elements */
/* Elements are from 0 .. n-1 */
/* Ranks are from 0 .. C(n,k) - 1 */


#include <stdio.h>

int n,k,count;
int C[20][20];

int cardCombset(n,k)
int n,k;
{
int i,j,card;

for (i=0;i<=n;i++)
{
  C[i][0]=1;
  C[i][i]=1;
}
for (i=2;i<=n;i++)
  for (j=1;j<i;j++)
    C[i][j]=C[i-1][j-1]+C[i-1][j];
card=C[n][k];
printf("cardinality of combination set %d\n",card);
return card;
}

void rank2comb(rank,comb)
int rank,comb[20];
{
int i,j,leftover;
int complement[20];

leftover=count-rank-1;
j=n-1;
for (i=k-1;i>=0;i--)
{
  for (;leftover<C[j][i+1];j--)
    ;
  complement[i]=j;
  leftover-=C[j][i+1];
  j--;
}
for (i=0;i<k;i++)
  comb[i]=n-1-complement[k-1-i];
}

void readComb(comb)
int comb[20];
{
int i;

while (1)
{
  printf("enter %d combination elements\n",k);
  for (i=0;i<k;i++)
  {
    scanf("%d",&comb[i]);
    if (comb[i]<0 || comb[i]>=n)
    {
      printf("bad input\n");
      break;
    }
  }
  if (i==k)
  {
    for (i=0;i<k-1;i++)
      if (comb[i]>=comb[i+1])
        break;
    if (i==k-1)
      break;
    printf("bad input\n");
  }
}
}

void printComb(comb)
int comb[20];
{
int i;

for (i=0;i<k;i++)
  printf("%d ",comb[i]);
printf("\n");
}

int comb2rank(comb)
int comb[20];
{
int i,j,rank;
int complement[20];

for (i=0;i<k;i++)
  complement[i]=n-1-comb[k-1-i];
rank=C[n][k];
for (i=0;i<k;i++)
  rank-=C[complement[i]][i+1];
rank--;
return rank;
}

void nextComb(combA,combB)
int combA[20],combB[20];  /*Input & output arrays*/
{
int i,j;

for (i=0;i<k;i++)
  combB[i]=combA[i];
for (j=k-1;combB[j]==n-k+j;j--)
  ;
combB[j]++;
for (j++;j<k;j++)
  combB[j]=combB[j-1]+1;
}

main()
{
int rank,numCombs,i;
int comb[20],comb2[20];
int *combA,*combB,*temp;

printf("enter n and k\n");
scanf("%d %d",&n,&k);
count=cardCombset(n,k);
printf("rank -> comb\n");
while (1)
{
  printf("enter rank (-1 to terminate)\n");
  scanf("%d",&rank);
  if (rank<(-1) || rank>=count)
  {
    printf("bad rank\n");
    continue;
  }
  if (rank==(-1))
    break;
  rank2comb(rank,comb);
  printComb(comb);
}
printf("comb -> rank\n");
while (1)
{
  printf("wish to convert a case? (1=yes 0=no)\n");
  scanf("%d",&i);
  if (i<0 || i>1)
  {
    printf("bad response\n");
    continue;
  }
  if (!i)
    break;
  readComb(comb);
  printf("rank is %d\n",comb2rank(comb));
}
printf("enumerate combinations starting from a rank\n");
while (1)
{
  printf("enter rank & number of combinations (-1 -1 to stop)\n");
  scanf("%d %d",&rank,&numCombs);
  if (rank==numCombs && rank==(-1))
    break;
  if (rank<0 || rank>=count)
  {
    printf("bad rank\n");
    continue;
  }
  if (numCombs<1 || rank+numCombs-1>=count)
  {
    printf("bad number of combinations\n");
    continue;
  }
  rank2comb(rank,comb);
  printf("starting combination: ");
  combB=comb;
  combA=comb2;
  for (i=0;i<numCombs-1;i++)
  {
    printComb(combB);
    temp=combA;
    combA=combB;
    combB=temp;
    nextComb(combA,combB);
  }
  printComb(combB);
}
}