/* index2comb.c
 * combIndex.c
 *
 * Recherche d'une ou de plusieurs combinaisons de p éléments de
 * l'ensemble [1 n] = {1, 2, 3, 4, 5, ..., n}
 * 
 * Copyright (C) 2006 - 2009 Jean-Paul Davalan <jeux-et-mathematiques@davalan.org>
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 *
 *
 * compilation :  gcc -O2 -o index2comb index2comb.c
 *                gcc -O2 -DRECURSE -o index2comb index2comb.c 
 *
 * usage : index2comb n p k0 [k1 k2 ...]
 *                      (0 <= k_n < binomial(n, p))
 *	   index2comb n p
 *                      (si k_n n'est pas donné, la valeur retournée est binomial(n, p))
 *
 * exemple
 * -------
 * index2comb 50 25 126410606437751
 * 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
 *
 * 
 * exemple de script bash pour obtenir toutes les combinaisons 
 * -------
   n=10;
   p=4;
   A=`index2comb $n $p`;  # nombre de combinaisons
   i=0; 
   while [ $i -lt $A ] ; 
     do index2comb $n $p $i; # combinaison numéro $i
     i=$(($i+1)); 
   done
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

unsigned long long int
binom(int n, int p)
{
  unsigned long long int b = 1;
  int     i;
  for (i = 0; i < p; i++) {
    b *= n - i;
    b /= i + 1;
  }
  return b;
}

#ifdef RECURSE
void
combinaison(int n, int p, unsigned long long int k)
{
  if (k < 0 || n <= 0 || p <= 0)
    return;
  long long int b = binom(n - 1, p - 1);
  if (k < b) {
    printf("%d ", n);
    combinaison(n - 1, p - 1, k);
  } else {
    combinaison(n - 1, p, k - b);
  }
}
#else
void
combinaison(int n, int p, unsigned long long int k)
{
  long long int b;
  for (; k >= 0 && n > 0 && p > 0; n--) {
    b = binom(n - 1, p - 1);
    if (k < b) {
      printf("%d ", n);
      p--;
    } else {
      k -= b;
    }
  }
}

#endif
int
main(int argc, char *argv[])
{
  int     n, p;
  unsigned long long b;
  if (argc < 3) {
    printf("Combinaisons numérotées (d'indices donnés)\n"
       "Sous-ensembles de p éléments de [1 n]\n"
       "usage : %s n p [k0 [k1 ...]]\n", argv[0]);
    exit(1);
  }
  n = atoi(argv[1]);		// lecture des paramètres
  p = atoi(argv[2]);
  // pas de combinaison
  if (n < 0 || p < 0 || p > n)
    return 0;
  b = binom(n, p);
  //  les combinaisons     
  if (argc == 3) {
    // printf("binomial(%d, %d) = %Ld\n",n, p, binom(n,p));
    printf("%Ld\n", binom(n, p));
  } else {
    int     i;
    unsigned long long k;
    for (i = 3; i < argc; i++) {
      k = atoll(argv[i]);
      if (k < 0 || k >= b) {
	continue;
      }
      combinaison(n, p, k);
      printf("\n");
    }
  }
  return 0;
}

/*     Relation souvent utilisée pour construire le triangle de Pascal
 *     binom(n, p) = binom(n-1, p-1) + binom(n-1, p)
 *     
 *            p=0  1  2  3  4 ...
 *      n=0     1                    
 *              1  1                 
 *              1  2  1              
 *              1  3  3  1           
 *              1  4  6  4  1                  1
 *        5     1  5 10 10  5  1               .   5
 *              1  6 15 20 15  6  1            .   .  15
 *              1  7 21 35 35 21  7  1         .   .  21   .
 *        8     1  8 28 56 70 56 28  8  1      .   .   .  56
 *              
 *     algorithme pour construire la combinaison  n=8 p=3 k=19
 *
 *     19<21  donc combin(8, 3, 19) = combin(7, 2, 19) + "8"
 *     19>=15 donc combin(7, 2, 19) = combin(6, 2, 4)  où 19-15 = 4
 *     4<5         combin(6, 2, 4) = combin(5, 1, 4) + "6"
 *     1>=1        combin(5, 1, 4) = combin(4, 0, 0) + "5"
 *                                 = "" + "5"
 *
 *     combin(8, 3, 19) = "5 6 8"
 */