Trouver les combinaisons possibles

zinou76 Messages postés 5 Date d'inscription vendredi 9 mai 2003 Statut Membre Dernière intervention 19 août 2004 - 17 août 2004 à 13:34
magic_Nono Messages postés 1878 Date d'inscription jeudi 16 octobre 2003 Statut Membre Dernière intervention 16 mars 2011 - 10 nov. 2005 à 00:30
Bonjour tt le monde,

je cherche un algorithme pour calculer et lister tt les combinaisons possibles de n éléments d'un ensemble E de x éléments tel que n<x

Ex: E=13,2,4,7,10
n=3

combin possibles:

13,2,4
13,2,7
13,2,10
13,4,7
...

d'après ce cas de figures on a 60 combin. possibles
A voir également:

17 réponses

vecchio56 Messages postés 6535 Date d'inscription lundi 16 décembre 2002 Statut Membre Dernière intervention 22 août 2010 14
17 août 2004 à 14:42
13,2,4 ne fait pas partie des possibilité puisque 2<3.
En fait pour cet exemple, je trouve 24 possibilités:
1) on choisit les 3 éléments: C4,3 = 4 possibilités
2) on choisit l'ordre des éléments: 3! = 6
3) 6*4=24
0
Rusalie Messages postés 21 Date d'inscription dimanche 18 juillet 2004 Statut Membre Dernière intervention 24 août 2004
17 août 2004 à 14:43
Informatique pour rire.

Le plus simple: tu as tes 5 chiffres dans un tableau de 1 à 5.

3 boucles for imbriquées qui compte de 1 à n-3 (5 pour n) en partant de la boucle externe, avec l'indice de la boucle suivante initialisée avec la valeur+1 de l'indice la boucle précédente.

Dans la boucle la plus interne tes combinaisions sont les valeurs à l'indice de tableau.

L'autre méthode, plus accadémique, plus abstraite, fait appel à la pile, en code réentrant.

Cupboard expert.
0
Rusalie Messages postés 21 Date d'inscription dimanche 18 juillet 2004 Statut Membre Dernière intervention 24 août 2004
17 août 2004 à 14:47
(-2) s'entend,

Cupboard expert.
0
pinderlot Messages postés 59 Date d'inscription jeudi 1 juillet 2004 Statut Membre Dernière intervention 1 septembre 2004 1
17 août 2004 à 15:38
Si je comprends bien tu veux choisir n éléments parmis un ensemble de x éléments (avec n<x). A mon avis, il y a C(n,x) combinaisons.

tu mets tes x éléments dans un tableau tab[x] puis tu fais des boucles en prenant n éléments à la fois...

int total = 0;
for (i=0; i<x; i++)
for (j=i+1; j<x-1; j++)
for (k=j+1; k<x-2; k++)
{
écrire_a_l_ecran (tab, tab[j], tab[k];
total ++; // stocke le nombre de combinaisons totales
}

-----------------------------------------------
[i]Tout ce qui ne tue pas rend plus fort !
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
zinou76 Messages postés 5 Date d'inscription vendredi 9 mai 2003 Statut Membre Dernière intervention 19 août 2004
17 août 2004 à 15:43
j'ai déjà pensé à cette algo, mais n n'est pas fixe, il peut prendre des valeurs de 1 à x-1. ds ce cas là on peut avoir de 1 à x-1 boucles imbriquées.

Et je cherche 1 algo ki fais ça dynamiquement (en fonction de n)
0
magic_Nono Messages postés 1878 Date d'inscription jeudi 16 octobre 2003 Statut Membre Dernière intervention 16 mars 2011
17 août 2004 à 15:59
vive l'ordo :sad)

va sur le site de mon école, ils ont des équipes de recherches très forte qui ne font que ça

recherche google :
polytech'Tours DI - E3I - Ordo

Magic Nono: l'informagicien!
0
zinou76 Messages postés 5 Date d'inscription vendredi 9 mai 2003 Statut Membre Dernière intervention 19 août 2004
17 août 2004 à 16:17
sur ce site y a ke des demandes d'inscriptions, de stages ...

t'as pas mieu?
0
magic_Nono Messages postés 1878 Date d'inscription jeudi 16 octobre 2003 Statut Membre Dernière intervention 16 mars 2011
17 août 2004 à 16:24
mdr, y zon fé un nv site pdt les vacances

avant, tt partait de la : http://www.di.polytech.univ-tours.fr/

maintenant, vive les fourmis ! http://www.antsearch.univ-tours.fr/earo/default.asp?FCT=DP&ID_PAGE=1

normatlement, tu devrait trouver ton bonheur ds ces pages

http://www.li.univ-tours.fr/Equipes/IndexEquipe.asp?Equipe=1

++

sinon, fé une recherche sur ordonnancement, combinaison, algo

++

Magic Nono: l'informagicien! 8-)
0
Rusalie Messages postés 21 Date d'inscription dimanche 18 juillet 2004 Statut Membre Dernière intervention 24 août 2004
17 août 2004 à 16:55
Question bateau et exigeante, le yeux pas en face des trous.

Il faut utilier la récurence. (la pile) pour pour allrr à n-1 n indifférent

Cupboard expert.
0
pinderlot Messages postés 59 Date d'inscription jeudi 1 juillet 2004 Statut Membre Dernière intervention 1 septembre 2004 1
17 août 2004 à 17:00
bin vi tu crées une fonction qui contient seulement la boucle dont les variables sont les paramètres... et tu appelles autant de fois ta fonction que la valeur de ton entier n.
-----------------------------------------------
Tout ce qui ne tue pas rend plus fort !
0
Rusalie Messages postés 21 Date d'inscription dimanche 18 juillet 2004 Statut Membre Dernière intervention 24 août 2004
17 août 2004 à 17:43
... et bin vi aussi ne oublier de multiplier la boucle par l'age du capitaine.

Charmant très mature !

Cupboard expert.
0
pinderlot Messages postés 59 Date d'inscription jeudi 1 juillet 2004 Statut Membre Dernière intervention 1 septembre 2004 1
18 août 2004 à 09:23
lol, je ne suis pas capitaine mais lieutenant-colonel !

réponse bateau.

charmant... très nature.
-----------------------------------------------
Tout ce qui ne tue pas rend plus fort !
0
zinou76 Messages postés 5 Date d'inscription vendredi 9 mai 2003 Statut Membre Dernière intervention 19 août 2004
18 août 2004 à 16:29
trêve de bavardage les gars. J'ai trouvé...

on met la séquence à combiner dans un tableau, puis en appel un fonction récursive.

Cette fonction part du principe qu'on fixe le premier élément puis on le combine avec le reste, ensuite on fixe le 2eme ...

Ex: soit la séquence {1,2,3,4}
dabord on fixe le 1 ->on fixe le 2 ->on combine le 3 et le4
ensuite ->on fixe le 3 ->on combine le 2 et le 4
->on fixe le 4 ->on combine le 2 et le 3
ensuite on fixe le 2 -> ..
..
etc

voici le code:

/**********************************************/
#include <stdio.h>

void print_tab(unsigned char tab[],int size_tab)
{
int i;

for(i=0;i<size_tab;i++)
printf("%d",tab[i]);
printf("\n"); //retour à la ligne
}

void permute(unsigned char tab[],unsigned char i,unsigned char j)
{
unsigned char c;

c=tab[i];
tab[i]=tab[j];
tab[j]=c;

}

void combin(unsigned char tab[],int i, int size_tab)
{
unsigned char j;

if (i==size_tab)
{
print_tab(tab,size_tab);
}
else
for(j=i;j<size_tab;j++)
{
permute(tab,i,j);
combin(tab,i+1,size_tab);
permute(tab,i,j);
}
}

main()
{
unsigned char tab[]={1,2,3,4};

combin(tab,0,4);
}
0
Strick9 Messages postés 40 Date d'inscription mardi 8 novembre 2005 Statut Membre Dernière intervention 9 mai 2007
9 nov. 2005 à 18:21
merci pour ta solution zinou76 mais pourrez vous svp changer cette solution pour qu'on puisse utiliser n valeur (par exemple l 'utilisateur donne le nombre de valeur a donner ainsi que les valeurs) au lieu de ce tableau a 4 valeur.
0
magic_Nono Messages postés 1878 Date d'inscription jeudi 16 octobre 2003 Statut Membre Dernière intervention 16 mars 2011
9 nov. 2005 à 20:11
avec un joli malloc et 2 sorte de scanf, C tout à fait faisable



cf bases de C

___________________________________________________________
Magicalement
Nono
0
Strick9 Messages postés 40 Date d'inscription mardi 8 novembre 2005 Statut Membre Dernière intervention 9 mai 2007
9 nov. 2005 à 20:44
je C bien que c'est tout a fait faisable mais je suis débutant, débutant parmi les débutant donc si une âme charitable accepte bien de me montrer comment l'utiliser avec n éléments et merci d'avance.
0
magic_Nono Messages postés 1878 Date d'inscription jeudi 16 octobre 2003 Statut Membre Dernière intervention 16 mars 2011
10 nov. 2005 à 00:30
pour moins de pb, j'utilise des macros.



tu les trouveras dans mes premieres sources publiées ici (suis les liens)



transforme le main

en :

<

int main()

{

unsigned int nb,i;

unsigned char *tab;

//définition

printf("nombres d'elements à trier");

//rq : peut etre des fflush à faire pour nettoyer les tampons.

scanf("%ud",&nb);

ALLOUEn(tab,unsigned char,nb);

//remplissage:

for(i=0;i<nb;i++)

{

printf("\nvaleur elt %d : ",i);


//rq : peut etre des fflush à faire pour nettoyer les tampons.


scanf("%ud",&tab[i]);

}

combin(tab,0,nb);

return 0;

>





nota: j'ai écris ceci à la volé , sans compilo, et n'ai pas fait de la prog console depuis lgt

et comme je n'ai pas la science infuse, erreurs possibles.
___________________________________________________________
Magicalement
Nono
0
Rejoignez-nous