// generationCPS.cpp   Combinaisons, permutations, sous-ensembles<xmp>

// Génération systématique de combinaisons, permutations ou sous-ensembles
//    les combinaisons: combInit, combSuivante
//        6 combinaisons de 2 valeurs parmi 0,1,2,3:
//           0,1   0,2   0,3   1,2,  1,3   2,3
//    les permutations: permInit, permSuivante
//        6 permutations des nombres 0,1,2:
//           0,1,2  1,0,2  0,2,1  2,0,1  1,2,0  2,1,0
//    les sous-ensembles d'un ensemble: sousInit, sousSuivant
//       8 sous-ensembles d'un ensemble de 3 éléments:
//       (1: élément choisi, 0:élément non choisi)
//          0,0,0  0,0,1  0,1,0  0,1,1  1,0,0  1,0,1  1,1,0  1,1,1
//
// Tirage au sort de combinaisons, permutations ou sous-ensembles
//    combAleatoire, permAleatoire, sousAleatoire
//
// En plus
//     tri d'un tableau d'entiers par ordre croissant: trierOC

// g++ -o t generationCPS.cpp

#include <iostream.h>
#include <values.h>

const int MAX=32;

//  =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =  +
//                      Sous-programmes définis                        +
//  =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =  +

void affTableau(int p, int v[MAX], char sep[]=",");
//
int combInit( int n, int p, int v[MAX]);
int combSuivante( int n, int p, int v[MAX]);
//
int permInit(int p[], int np);
int permSuivante(int p[], int np);
void trierOC(int p[], int np);
int echangerPlusGrand(int &d, int p[], int np);
//
int sousInit( int ns, int s[]);
int sousSuivant( int ns, int s[], int b=2);
//
void combAleatoire(int p, int n, int v[MAX]);
void permAleatoire(int n, int v[MAX]);
void sousAleatoire(int n, int v[MAX], int & p);


void affTableau(int p, int v[MAX], char sep[]) {
// Affichage d'un tableau à une dimension
int i;
for(i=0; i<p-1; i++) cout<<v[i]<<sep;
if(p>0) cout<<v[p-1]<<"  ";
}

//  =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =  +
//                           Combinaisons                              +
//  =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =  +

int combInit( int n, int p, int c[MAX]) {
// Initialise le tableau c pour obtenir des combinaisons des p entiers
// de 0 à n-1. Exemple d'obtention des combinaisons  de 4 éléments: à
// chaque appel de combSuivante, on obtient une nouvelle permutation:
//      int t[10],nt;
//      nt=4; combInit(nt,2,t);
//      while(combSuivante(nt,2,t)) {
//         affTableau(nt,t);
//         }
// Affichage obtenu:   0,1   0,2   0,3   1,2,  1,3   2,3
// VOIR combSuivante

int existe=(n>0 &&  p>0 && p<=n);
if(existe) {
   int i;
   for(i=0; i<p-1; i++) c[i]=i;
   c[p-1]=p-2;
   }
return existe;
}

int combSuivante( int n, int p, int c[MAX]) {
// Renvoie 1 s'il existe une autre combinaison, et 0 si elles ont toutes
// été obtenues.
// Si elle existe, le tableau c contient la nouvelle combinaison.
// VOIR combInit

int i,v,k;
int existe=1;

k=p-1;
v = ++c[k];
while(k>0 && v>=n) {
   k=k-1;
   for(i=k, v=c[k]; i<p; i++) {
       v++;
       c[i]=v;
       // cout<<"  c["<<i<<"]="<<c[i];
       }
   }
return (v<n);

return existe;
}


//  =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =  +
//                           Permutations                              +
//  =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =  +

int permInit(int p[], int np) {
// Initialise p pour obtenir des permutations des entiers de 0 à np-1
// Exemple d'obtention des permuations de 4 éléments; à chaque appel
// de permSuivante, on obtient une nouvelle permutation:
//      int t[10],nt;
//      nt=4; permInit(t,nt);
//      while(permSuivante(t,nt)) {
//         affTableau(nt,t);
//         }
// VOIR permSuivante

if(np<1) return 0;
else {p[0]=INT_MAX; return 1;}
}

int permSuivante(int p[], int np) {
// Renvoie une permutation des entiers de 0 à np-1 inclus
//   avec np=3, on obtient: 0,1,2  1,0,2  0,2,1  2,0,1  1,2,0  2,1,0
// UTILISE echangerPlusGrand, trierOC
// VOIR permInit
int existe,d;
if(np<1) existe=0;
else if(p[0]==INT_MAX) {
   // Première permutation à générer
   existe=1;
   for(d=0; d<np; d++) p[d]=d;
   }
else if(np==1) existe=0;
else if(np==2) {
   if(p[0]>p[1]) existe=0;
   else {
      existe=1;
      d=p[0]; p[0]=p[1]; p[1]=d;
      }
   }
else {
   existe=permSuivante(p,np-1);
   if(!existe) {
      // Il faut changer le dernier élément de p;
      existe=echangerPlusGrand(p[np-1],p,np-1);
      }
   }
return existe;
}

int echangerPlusGrand(int &d, int p[], int np) {
// Renvoie VRAI si p contient un entier e, strictement inférieur à d
//         FAUX si tout élément de p est supérieur a d
// Si e existe, il est échangé avec d
// UTILISE trierOC
int i,iM,aux;
// Indices du min de p et du max
for(iM=-1, i=0; i<np; i++)
   if(p[i]<d && iM==-1) iM=i;
   else if(p[i]<d && p[i]>p[iM]) iM=i;
if(iM==-1) return 0;
// échange
aux=p[iM]; p[iM]=d; d=aux;
trierOC(p,np);
return 1;
}

void trierOC(int t[], int nt) {
// Tri par ordre croissant (tri par insertion), des nt éléments de t
// Algorithme du 'tri insertion'

int tst;  // taille du sous tableau trié
int val, j, k, im;

for( tst=1; tst<nt; tst++) {
   //ici t[0..tst-1,] est trié
   val = t[tst];
   // Etape: où ranger val dans le sous-tableau trié t[0..tst-1]
   j=-1; k=tst;                // recherche dichotomique
   while( j < k-1) {
      im = (j+k)/2;  // indice du milieu de t[j+1 .. k-1]
      if( val < t[im] ) k=im;
      else              j=im;
      //ici t[j] <= val < t[k];
      }
   // Décalages et insertion
   for( k=tst-1; k>j; k-- ) t[k+1]=t[k];
   t[j+1] = val;
   // ici t[0..tst-1,tStTtie] est trié
   }
}

//  =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =  +
//                    Sous-parties d'un ensemble                       +
//  =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =  +

int sousInit( int ns, int s[]) {
// Initialisation de s pour obtenir ensuite les sous-parties d'un
// ensemble à ns éléments.
// VOIR sousSuivant

int i;
if(ns < 1) return 0;
for(i=0; i<ns; i++) s[i]=0;
// initialisation liée à l'incrémentation dans sousSuivant
s[ns-1]=-1;
return 1;
}

int sousSuivant( int ns, int s[], int b) {
// Renvoie 1 s'il existe une sous-partie suivante, de {0,1,..ns-1}
// Une sous-partie d'un ensemble à ns éléments, est codée par un
// tableau de ns valeurs 0 ou 1.
// Exemple avec ns=3, les appels suivants:
//         sousInit(ns,ts);
//         while(sousSuivant(ns,ts)){
//              cout<<" "; affTableau(ns,ts);
//              }
//    fournissent les affichages:
//         0,0,0  0,0,1  0,1,0  0,1,1  1,0,0  1,0,1  1,1,0  1,1,1
// VOIR sousInit

if(ns<1) return 0;
// initialisation de k liée à sousInit
int k=ns, correct=0;
do {
   k--;
   s[k]=s[k]+1; correct=(s[k]<b);
   } while(!correct && k>0);
if(correct) for(k=k+1;k<ns;k++) s[k] = 0;
// cout<<" et c:"<<correct<<",";  affTableau(s,ns,""); cout<<"  ";
return correct;
}


//  =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =  +
//                    Génération pseudo-aléatoire                      +
//  =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =  +

void combAleatoire(int p, int n, int v[MAX]) {
// Génére une combinaison pseudo-aléatoire de p entiers 0 parmi 0 .. n-1
// Condition d'emploi:  0<=p  p<=n
int i,m, a, aux, pp;

// Les cas limites
if(p==0) return;
for(i=0; i<n; i++) v[i]=i;
if(p==n) return;

// Une combinaison de p éléments est associée à une combinaison de n-p
// éléments; donc on cherche la plus courte
pp = (p+p<n) ? p : n-p;
for(m=n; m>n-pp; m--) {
   // Tirer au sort un nombre a entre [0 m[, et échanger v[a] v[m-1]
   a = rand()%m;
   aux=v[a]; v[a]=v[m-1]; v[m-1]=aux;
   // cout<<a<<"    "; affTableau(n,v); cout<<endl;
   }
if(pp==p) {
   // Ramener en tête les p éléments de droite
   for(i=0, m=n-1; i<pp; i++, m--) {
      aux=v[i]; v[i]=v[m]; v[m]=aux;
      }
   // cout<<a<<"    "; affTableau(n,v); cout<<endl;
   }
}


void permAleatoire(int n, int v[MAX]) {
// Génére une permutation pseudo-aléatoire des entiers 0, 1 ... n-1
int i,m, a, aux;
for(i=0; i<n; i++) v[i]=i;
for(m=n; m>1; m--) {
   // Tirer au sort un nombre a entre [0 m[, et échanger v[a] v[m-1]
   a = rand()%m;
   aux=v[a]; v[a]=v[m-1]; v[m-1]=aux;
   }
}


void sousAleatoire(int n, int v[MAX], int & p) {
// Génére un sous-ensemble pseudo-aléatoire de {0, 1, ... n-1}
// p est le nombre d'éléments du sous-ensemble tiré au sort
// {v[0], v[1] ... v[p-1]} sont les éléments tirés au sort
p = rand()%(1+n);
combAleatoire(p,n,v);
if(p>2) trierOC(v,p);
}

//  =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =  +
//                           Vérifications                             +
//  =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =  +

int  main()    {
// Génération aléatoire de sous-ensemble
int te[MAX], pe, ne;
srand(time(NULL));
ne=10; sousAleatoire(ne,te,pe); affTableau(pe,te); cout<<endl;
ne=10; sousAleatoire(ne,te,pe); affTableau(pe,te); cout<<endl;
ne=10; sousAleatoire(ne,te,pe); affTableau(pe,te); cout<<endl;
ne=10; sousAleatoire(ne,te,pe); affTableau(pe,te); cout<<endl;

// Génération aléatoire de combinaison
int tc[MAX], pc, nc;
int occ[MAX][MAX], socc[MAX], ic,jc,kc, rc, larc;
srand(time(NULL));
cout<<endl;
pc=6;nc=9; combAleatoire(pc,nc,tc);
cout<<"Une combinaison: "; affTableau(pc,tc); cout<<endl;
pc=3;nc=9; combAleatoire(pc,nc,tc);
cout<<"Une combinaison: "; affTableau(pc,tc); cout<<endl;
// On regarde si sur plusieurs tirages les valeur apparaissent de façon
// régulière
rc=10000;
for(ic=0; ic<nc; ic++) {
   socc[ic]=0;
   }
for(pc=5, nc=10, kc=0; kc<rc; kc++) {
   combAleatoire(pc,nc,tc); // affTableau(pc,tc); cout<<endl;
   for(jc=0; jc<pc; jc++) {ic=tc[jc]; socc[ic]++;}
   }
larc=3; cout.precision(larc);
cout.setf(ios::left,ios::adjustfield);
cout<<"Fréquence de chaque nombre ("<<rc<<" essais) pour C("
   <<pc<<","<<nc<<"):\n   0      ";
for(ic=1; ic<nc; ic++) { cout.width(4+larc);  cout<<ic; }
cout<<"\n  ";
for(ic=0; ic<nc; ic++) {
      cout.width(4+larc);
      cout<<float(socc[ic])/rc/pc;
      // cout<<socc[ic]<<"  ";
      }
   cout<<endl;
//

/* Génération aléatoire de permutation
int ta[MAX], na,sa, occ[MAX][MAX], socc[MAX], ia,ja,ka, rep;
srand(time(NULL));
na=9; permAleatoire(na,ta);
cout<<"Une permutation: "; affTableau(na,ta); cout<<endl;
for(ia=0; ia<na; ia++) {
   for(ja=0; ja<na; ja++) occ[ia][ja]=0;
   socc[ia]=0;
   }
// On regarde si sur plusieurs tirages les valeur apparaissent de façon
// régulière
rep=10000;
for(ka=0; ka<rep; ka++) {
   permAleatoire(na,ta);
   for(ja=0, sa=na*(na-1)/2; ja<na; ja++) sa-=ta[ja];
   if(sa!=0) { cout << "bizarre "; affTableau(na,ta); cout<<endl; }
   for(ja=0; ja<na; ja++) {ia=ta[ja]; occ[ia][ja]++;}
   }
cout.precision(4);
cout<<"Fréquences d'apparition de chaque valeur:\n"
    <<"   la ligne 2 montre les fréquences d'apparition du 2\n"
    <<"   fréquence moyenne: "<<1./na
    <<"   nb.tirages: "<<rep<<"\n\n";
cout.setf(ios::left,ios::adjustfield);
cout<<"case:   ";
for(ia=0; ia<na; ia++) { cout.width(8); cout<<ia;}
cout<<endl; 
for(ia=0; ia<na; ia++) {
   cout<<"li:"<<ia<<"  ";
   for(ja=0; ja<na; ja++) {
      cout.width(8);
      cout<<float(occ[ia][ja])/rep;
      }
   cout<<endl;
   }
*/



/* Sous-parties d'un ensemble
int ts[10],ns,nse;
ns=3; sousInit(ns,ts);
while(sousSuivant(ns,ts)){
   cout<<" "; affTableau(ns,ts);
   }
cout<<endl;
nse=0; ns=4; sousInit(ns,ts);
while(sousSuivant(ns,ts,3)){
   nse++;
   cout<<" "; affTableau(ns,ts,"");
   if(nse%9==0) cout<<endl;
   }
cout<<"   nse="<<nse<<endl;;
*/


/*
int t0[]={ 3,2,1,4}, nt0=sizeof(t0)/sizeof(t0[0]);
int t1[]={ 4,3,2,1}, nt1=sizeof(t1)/sizeof(t1[0]);
int b;
affTableau(nt0,t0); cout<<endl;
trierOC(t0,nt0);
cout<<"   version triée ";affTableau(nt0,t0); cout<<endl;

affTableau(nt0,t0); cout<<endl;
b=echangerPlusGrand(t0[3],t0,3);
cout<<"   b="<<b<<"   ";affTableau(nt0,t0); cout<<endl;
//
affTableau(nt1,t1); cout<<endl;
b=echangerPlusGrand(t1[3],t1,3);
cout<<"   b="<<b<<"   ";affTableau(nt1,t1); cout<<endl;


affTableau(3,t0); cout<<endl;
b=permSuivante(t0,3);
cout<<"  permSuivante:"<<b<<"   ";affTableau(3,t0); cout<<endl;
b=permSuivante(t0,3);
cout<<"  permSuivante:"<<b<<"   ";affTableau(3,t0); cout<<endl;
b=permSuivante(t0,3);
cout<<"  permSuivante:"<<b<<"   ";affTableau(3,t0); cout<<endl;
b=permSuivante(t0,3);
cout<<"  permSuivante:"<<b<<"   ";affTableau(3,t0); cout<<endl;
b=permSuivante(t0,3);
cout<<"  permSuivante:"<<b<<"   ";affTableau(3,t0); cout<<endl;
b=permSuivante(t0,3);
cout<<"  permSuivante:"<<b<<"   ";affTableau(3,t0); cout<<endl;

b=0; nt1=4; permInit(t1,nt1);
while(permSuivante(t1,nt1)) {
   b++;
   affTableau(nt1,t1);
   if(b%6==0)cout<<endl;
   }
cout<<"   nb.permutations:"<<b<<endl;

nt1=4; t1[0]=3; t1[1]=5; t1[2]=7; t1[3]=9;
b=1; affTableau(nt1,t1);
while(permSuivante(t1,nt1)) {
   b++;
   affTableau(nt1,t1);
   if(b%6==0)cout<<endl;
   }
cout<<"   nb.permutations:"<<b<<endl;
*/


/* Combinaisons
int t[MAX],n,p;
n=4; p=2; combInit(n,p,t);
combSuivante(n,p,t); affTableau(p,t);
combSuivante(n,p,t); affTableau(p,t);
combSuivante(n,p,t); affTableau(p,t);
combSuivante(n,p,t); affTableau(p,t);
combSuivante(n,p,t); affTableau(p,t);
combSuivante(n,p,t); affTableau(p,t);
cout<<(combSuivante(n,p,t)?"  ":"  fin")<<endl;

n=6; p=2; combInit(n,p,t);
while(combSuivante(n,p,t)) affTableau(p,t);
cout<<endl;

n=5; p=3; combInit(n,p,t);
while(combSuivante(n,p,t)) affTableau(p,t);
cout<<endl;
*/


//  =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =  +
cout<<"\n> > >"; cin.getline(new char[80],80);
return 0;
}

//fin generationCPS.cpp </xmp>