/* arrgt.c
 *
 * Recherche de tous les arrangements de p éléments de
 * l'ensemble {1, 2, 3, 4, 5, ..., n}
 * 
 * 01/05/2005 Jean-Paul Davalan <jpdvl@wanadoo.fr>
 *
 * compilation :  gcc -O2 -o arrgt arrgt.c
 * usage : arrgt  n p
 *
 * la structure contient après calcul tous les arrangements
 * dans le tableau arrgt->tab
 *
 * arrgt->tab[i] est l'arrangement i 0 <= i < Anp
 *
 * arrgt->tab[i][k] pour 0<= k < p sont les termes de l'arrangement
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* la structure cb ci-dessous contient tous les résultats */
typedef struct arrgt {
	int n,    // le n de Anp
	    p,    // le p de Anp
	    anp,  // la valeur Anp du nombre de combinaisons
	    pos,  // varie de 0 au début à Cnp-1 à la fin
	    **tab; // tableau de Cnp lignes contenant chacune une combinaison
	           // sous la forme de p entiers (de 1 au moins à n au plus)
} arrgt;

void arrangements(arrgt *arr, int k, int *L, int *t);
	
int
main(int argc, char *argv[]) {
	int n, p, i, j, anp, *L, *t;
        arrgt * arr = (arrgt *)malloc(sizeof(arrgt));
	if(argc<3) {
		printf("usage : %s n p\n",argv[0]);
		exit(1);
	}
	n = atoi(argv[1]); // lecture des paramètres
	p = atoi(argv[2]);
        if(n<0 || p<0 || p>n) return 0;
	
	/* -----------------------------------------------------------------
	 * initialisations de 'arr' , 
	 * on pourrait le mettre dans une fonction
	 * -----------------------------------------------------------------
	 */
	for(i=n,j=1, anp=1;i>n-p;i--,j++) {   // calcul de Cnp
          anp *= i;
	}
	arr->n = n;
	arr->p = p;
	arr->anp = anp;
	arr->pos = 0;
	arr->tab = (int **)malloc(anp * sizeof(int *));
	
	/* -----------------------------------------------------------------
	 *  préparation des paramètres L et t avant de lancer 
	 *  la fonction 'combinaisons'
	 *  -----------------------------------------------------------------
	 */
	L = (int *) malloc(p*sizeof(int));
	t = (int *) malloc(n*sizeof(int));
	for(i=0;i<n;i++) t[i] = i;

	/* c'est parti */
	
	arrangements(arr, 0, L, t);
	
	/* -----------------------------------------------------------------
	 * faire ici ce qu'on veut de comb
	 * par exemple l'afficher comme on le fait ci-dessous
	 * -----------------------------------------------------------------
	 */
	for(i=0;i<arr->anp;i++) {   // Cnp lignes
		printf("(");
		for(j=0;j<arr->p;j++) { // de p nombres entiers
			printf("%d",arr->tab[i][j]);
			if(j<arr->p-1) printf(", ");
		}
                printf("), ");
	}
	printf("\n");
	/* -----------------------------------------------------------------
	 * pour faire bien on désalloue la mémoire
	 * -----------------------------------------------------------------
	 */
	free(L);
	free(t);
	for(i=0;i<arr->anp;i++) {
		 free(arr->tab[i]);
	}
	free(arr->tab);
	free(arr);
	
	/* -----------------------------------------------------------------
	 * plus rien à faire ici, on peut d'en aller
	 * -----------------------------------------------------------------
	 */
	return 0;
}


void arrangements(arrgt *arr, int k, int *L, int *t) {
	int n = arr->n, p = arr->p, i, j, j1, t2[n];
	
	if(k==p) {
		arr->tab[arr->pos] = (int *)malloc(p*sizeof(int));
		for(i=0;i<p;i++) arr->tab[arr->pos][i] = L[i] + 1;
		arr->pos++;
		return;
	}
	for(i=0;i<n-k;i++) {
		L[k] = t[i];
		for(j=0, j1=0;j<n-k;j++) {
			if(j != i) {
				t2[j1] = t[j];
				j1++;
			}
		}
		arrangements(arr, k+1, L, t2);
	}
}