Algo pour générer tous les couples, triplets, ... n-uplet d'une liste, n étant une variable

La question :

Bonjour,

Je dispose d'une liste de nombre stockés dans un tableau Tab[1000].
Comment faire pour générer tous les couples possibles, triplets, ...
n-uplet, n étant une variable ? (L'ordre des éléments dans le couple,
triplet ... est sans importance)

Générer tous les couples:

for (i=0; i<999; i++) {
for (j=i+1; j<1000; j++) {
considérer le couple (Tab[i], Tab[j]);
}
}

Générer tous les triplets:

for (i=0; i<998; i++) {
for (j=i+1; j<999; j++) {
for (k=j+1; k<1000; k++) {
considérer le triplet(Tab[i], Tab[j], Tab[k]);
}
}
}

mais pour avoir les n-uplets, n étant une variable, il me faudrait
un nombre variable de boucles "for", ce n'est pas possible. Auriez
vous une idée ?

Poser votre question sur le forum Programmation

Les 18 réponses :

"ast" a écrit dans le message de news:4d306ea6$0$18698$...


Bonjour,

Je dispose d'une liste de nombre stockés dans un tableau Tab[1000].
Comment faire pour générer tous les couples possibles, triplets, ...
n-uplet, n étant une variable ? (L'ordre des éléments dans le couple,
triplet ... est sans importance)

Générer tous les couples:

for (i=0; i<999; i++) {
for (j=i+1; j<1000; j++) {
considérer le couple (Tab[i], Tab[j]);
}
}

Générer tous les triplets:

for (i=0; i<998; i++) {
for (j=i+1; j<999; j++) {
for (k=j+1; k<1000; k++) {
considérer le triplet(Tab[i], Tab[j], Tab[k]);
}
}
}

mais pour avoir les n-uplets, n étant une variable, il me faudrait
un nombre variable de boucles "for", ce n'est pas possible. Auriez
vous une idée ?


J'ai bien une idée, un programme pourrait écrire un programme
générant tous les n-uplets, n étant une variable, puis avec un script
exécuter ces 2 programmes l'un après l'autre.

"ast" a écrit :


"ast" a écrit dans le message de news:4d306ea6$0$18698$...


Bonjour,

Je dispose d'une liste de nombre stockés dans un tableau Tab[1000].
Comment faire pour générer tous les couples possibles, triplets, ...
n-uplet, n étant une variable ? (L'ordre des éléments dans le couple,
triplet ... est sans importance)

Générer tous les couples:

for (i=0; i<999; i++) {
for (j=i+1; j<1000; j++) {
considérer le couple (Tab[i], Tab[j]);
}
}

Générer tous les triplets:

for (i=0; i<998; i++) {
for (j=i+1; j<999; j++) {
for (k=j+1; k<1000; k++) {
considérer le triplet(Tab[i], Tab[j], Tab[k]);
}
}
}

mais pour avoir les n-uplets, n étant une variable, il me faudrait
un nombre variable de boucles "for", ce n'est pas possible. Auriez
vous une idée ?


J'ai bien une idée, un programme pourrait écrire un programme
générant tous les n-uplets, n étant une variable, puis avec un script
exécuter ces 2 programmes l'un après l'autre.


Effectivemenet. Mais on peut le faire dynamiquement aussi.

Tu peux remplacer:


for(i=0;i<lim0;i++){

... i ...

}

par:


typedef struct {
int counter;
int limit;
} Iterator;

void iterator_init(Iterator* i,int limit){
i->counter=0;
i->limit=limit;
}

bool iterator_done(const Iterator* i){
return(i->counter>=i->limit);
}

void iterator_increment(Iterator* i){
i->counter++;
}

int iterator_value(Iterator* i){
return(i->counter);
}


Iterator i;
for(iterator_init(&i,lim0);!iterator_done(&i);iterator_increment(&i)){

... iterator_value(&i) ...

}


et donc, si on a un nombre variable de boucles imbriquées à faire:

typedef struct {
int n;
int* limits;
Iterator* is;
bool done;
} Iterators;


on peut facilement implémenter les operations nécessaire:


void iterators_init(Iterators* i,int n,int* limits){
i->n=n;
i->limits=limits;
i->is=malloc(sizeof(Iterator)*n);
i->done=false;
}

bool iterators_done(Iterators* i){
return(i->done);
}

void iterator_increment(Iterators* i){
i->done=true;
for(k=i->n-1;0<=k;k--){
iterator_increment(&(i->is[k]));
if(iterator_done(i->is[k])){
iterator_init(&(i->is[k]),i->limits[k]);
}else{
i->done=false;
return;
}
}
}

int iterator_values(Iterators* i,int k){
return(iterator_value(&(i->is[k])));
}



Iterators i;
for(iterators_init(&i,n,limits);!iterators_done(&i);iterators_increment(&i)){

... for(k=0;k<n;k++){ ... iterators_value(&i,k) ... } ...

}



--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.

Pascal J. Bourguignon a écrit :


Effectivemenet. Mais on peut le faire dynamiquement aussi.


On peut le faire de manière beaucoup plus simple et sans aucune
programmation dynamique

for ( i = 0; i < 2^n; ++i ) {
nuplet = {}
for ( j = 0; j < n; ++j ) {
if ( i && ( 1 << j ) ) {
nuplet.add(Tab[j])
}
}
considerer(nuplet)
}

Aeris a écrit :


Pascal J. Bourguignon a écrit :


Effectivemenet. Mais on peut le faire dynamiquement aussi.


On peut le faire de manière beaucoup plus simple et sans aucune
programmation dynamique

for ( i = 0; i < 2^n; ++i ) {
nuplet = {}
for ( j = 0; j < n; ++j ) {
if ( i && ( 1 << j ) ) {
nuplet.add(Tab[j])
}
}
considerer(nuplet)
}


C'est la méthode que j'emploie et que je trouve de loin la plus élégante.

--
Jean-marc

"ast" a écrit dans le message de groupe de discussion :
4d306ea6$0$18698$...

Bonjour,

Je dispose d'une liste de nombre stockés dans un tableau Tab[1000].
Comment faire pour générer tous les couples possibles, triplets, ...
n-uplet, n étant une variable ? (L'ordre des éléments dans le couple,
triplet ... est sans importance)

Générer tous les couples:

for (i=0; i<999; i++) {
for (j=i+1; j<1000; j++) {
considérer le couple (Tab[i], Tab[j]);
}
}

Générer tous les triplets:

for (i=0; i<998; i++) {
for (j=i+1; j<999; j++) {
for (k=j+1; k<1000; k++) {
considérer le triplet(Tab[i], Tab[j], Tab[k]);
}
}
}

mais pour avoir les n-uplets, n étant une variable, il me faudrait
un nombre variable de boucles "for", ce n'est pas possible. Auriez
vous une idée ?


============================ Voili, voilou
Tu declares un tableau qui va te servir d'index sur ton tableau
Tu l'initialises comme ca
UNO={0,1,2,3,4,5,6,7,8,9};
SI tu veux generer les doublons tu mets -1 dans l'element 2, les triplets -1
dans l'element 3, ...
Puis tu fait un NEXT
Et tu t'arretes quand la valeur du derniers element est egale a ta taille de
ton tableau

Ca fait +/-
N=2, ....
INIT(Index)
While (STILLTODO(Index)) {
print Tab[Index[0]], Tab[Index[1]], .....
NEXT(Index)
}


#define INIT(CUR) {COPY(CUR,UNO) ; CUR[N]=-1 ; }
#define NEXT(CUR) { int zz ; zz=0 ; while ((1+CUR[zz]) == CUR[zz+1])
{CUR[zz]=zz; zz++;} ; CUR[zz]++ ; }
#define STILLTODO(CUR) CUR[N-1] < TailleDuTableauIndexe

Poser votre question sur le forum Programmation

Questions similaires :

Algorithme de minimisation de variable.

Salut. j'ai 275 équations (qui ne sont que des additions, mais bon a aurait pu être autre chose), lesquels sont dépendantes les unes des autres voila une portion du...

Algo de stat

Bonjour, Je voudrais faire des statistiques comme ceci : J'ai un tableau de ce style (plus de colonnes et quelques miliers de lignes) +---+---+ | A | B | +---+---+ | A | C | +---+---+ | B | A | +---+---+ | A | C | +---+---+ | B | A | +---+---+ | C | B | +---+---+ | A | C | +---+---+ | B | A...

Variable arbre

Bonjour. Existe-t-il (sous Visual Basic) une méthode pour définir une collection sous forme d'arbre (un arbre généalogique par exemple) ? Merci.

[C/algo] Cumul des termes d'un vecteur

Le 02-02-2009, ? propos de Re: [C/algo] Cumul des termes d'un vecteur, Jean-Marc Bourguet ?crivait dans fr.comp.lang.c : Ça, c'est une question pour Vincent. En attendant un spécialiste d'analyse numérique, tu peux faire quelque chose qui s'approche de la double précision (et que j'ai trouvé si...

Générer les 30% meilleurs carrés d'une image

Bonjour, On considère une image monochrome avec disons 20 niveaux de gris. Le problème consiste simplement à générer les sous-carrés de côté n (n fixé) dont la somme des pixels est maximale. On veut seulement les 30% meilleurs. L'image n'est pas quelconque, elle est vallonnée un peu comme...