Algo affichage combinaison de p elemt parmi n

[Fermé]
Signaler
-
Messages postés
1
Date d'inscription
lundi 6 août 2012
Statut
Membre
Dernière intervention
6 août 2012
-
Bonjour,
je cherche un algo ou code (c# ou c++) dont le but est d'afficher toutes les combinaisons possible de p element d'un tableau d'entiers de n
elements exemple :
j'ai un tableau de 3 element int[] tab = {1,2,3} et que je veux les combinaisons de 2 elements.
resultats
12
12
23

je veux un algo generique pour un tableau de n entier, et le nombre d'element des combinaisons est p (C(n,p))
merci

9 réponses

Messages postés
4
Date d'inscription
mardi 17 novembre 2009
Statut
Membre
Dernière intervention
22 novembre 2009
2
Salut
je cherche un programme c ou c++ ou pascal ou basic ou n'inporte quels langage informatique qui permet de resoudre le probleme suivante:
je cherhe les combinaisons des X entiers a base de N

le programme doit me demander de:
* définir X (de type entier )
*saisir le x elements
* définir N (de type entier)
et affiche:
*les nombres des combinaisons possibles
*surtout affichée les différentes combinaisons possibles de X entier a base de N

exemple:
si X=3 ( 1 ; 3 ; 5 )
N=3
le programme affiche:

111 113 131 115 151 133 155 135 153
333 331 313 335 353 311 355 315 351
555 551 515 553 535 511 533 513 531

27 combinaisons

remarques:
*les combinaisons possibles peuvent contenir avec les combinaisons dont lequel il y a tout les X éléments d'autre combinaisons dont lequel on répète le même entier 2 fois ou 3 fois jusqu'à N fois.

* étant donner que la solution et un peut délicat dans le cas général (si il y a une solution dans le cas général avec X et N saisis au clavier sinon on fixe X=3 et je laisse N saisie au clavier et je cherche la solution de ce problème)

si quelqu'un pouvez me aider merci d'avance.
2
Merci

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

CCM 41713 internautes nous ont dit merci ce mois-ci

Salut,

je te propose un code qui devrait résoudre ton problème (la mise en forme ne ressemble peut-être pas exactement à ce que tu souhaites faire, mais ce sera facile de l'adapter). Il affiche des p-listes de n éléments où p et n sont quelconques. Bon courage.

Sinon, un algo récursif s'appelle lui-même (exemple factorielle) et admet une séquence de fin. Il n'est pas nécessaire d'utiliser la récursivité pour écrire le programme qui t'intéresse.

#include <stdio.h> // scanf et printf
#include <math.h> // pow
#include <stdlib.h> // malloc et free

int main()
{
long int *tab; // vecteur contenant les éléments à combiner
long int **liste; // matrice destinée à contenir les combinaisons
long int i,j; // indices de boucle
long int n = 3; // nombre d'éléments de tab
long int p = 3; // nombre d'éléments à combiner
char touche; // ne sert que pour la mise au point

// Allocation dynamique de tab
tab = (long int *) malloc(n*sizeof(long int));

// Allocation dynamique de liste
liste = (long int **) malloc((long int ) pow((double )n, (double )p)* sizeof(long int *));
for (i=0;i<(long int ) pow((double )n, (double )p);i++)
{
liste[i] = (long int *) malloc(p*sizeof(long int));
}

// Initialisation de tab
for (i=0;i<n;i++)
{
tab[i] = i + 1;
}

// Remplissage de la liste
for (i=0;i<(long int ) pow((double )n, (double )p);i++)
{
for (j=0;j<p;j++)
{
liste[i][j] = tab[(i/(long int )pow((double )n,(double )(p-(j+1))))%n];
printf("%ld\t",liste[i][j]);
}
printf("\n");
}

// Libération de tab
free(tab);

// libération de liste
for (i=0;i<(long int ) pow(n,p);i++)
{
free(liste[i]);
}
free(liste);

// Fin du programme
printf("Appuyez sur une touche pour continuer...");
scanf("%c",&touche);

return 0;
}

    
Bonjour,

je ne sais pas si vous attendez toujours une réponse mais j'ai une proposition de solution basée sur l'emploi d'un algorithme récursif codée en langage c.

Bonne journée.
Messages postés
4
Date d'inscription
mardi 17 novembre 2009
Statut
Membre
Dernière intervention
22 novembre 2009
2
merci beaucoup proto ;
dans ce programme, le nombre d'éléments de tab (n) est choisie arbitrairement(si je écrit 3 le programme fais les combinaisons possibles avec 1 2 et 3 et si je écrit n=4 (1 2 3 et 4)
est que se possibles de ecrire moi meme les n elements( par exemple si je ecrit 3 je doit obligatoirement choisit 3 entiers avec lesquels je fait les combinaisons possibles) c-a-d il faut lorsque je clic sur Run le programme doit m'écrit :
definir n (nombre d'elements de tab ):
saisir les n éléments:
définir p ( nombre d'éléments à combiner ):
et après le programme affiche les combinaisons possibles de n éléments a base de p


remarques:
par exemple si j'ecrit n=3 et p = 8 lorsque le conteur tourne au début je voit les premiers combinaisons et lorsqu'il s'arrête je voit seulement les derniers combinaisons c-a-d le programme n'affiche pas tout les combinaisons si p>=6 et n= 3 et dans beaucoup d'autre cas lorsque je agrandit n et p
et d'autre par le programme n'affiche pas les combinaisons si p>10 parce que les éléments de tableau sont un peut décalé
en conclusion le programme que je suit entraine de recherchée semble beaucoup au programme que tu m'envoie avec seulement n , les n éléments et p saisie au clavier et le programme affiche tout les combinaisons possibles même si n et p sont grande
si n'est pas possible de réaliser ce programme je fixe n = 3 et je laisse p variable(saisie au clavier).


ce qui concerne la récursivité je ne sait pas qu'est que sa fait dire récursivité et à quoi ça sert?

je vous remercie une autre fois proto et a bientôt
Salut,

- pour la récursivité : ftp://ftp-developpez.com/franckh/pdf/recursivite-en-langage-c.pdf. On faire une recherche sur la récursivité.

- le programme que je t'ai fourni, les modifications que tu demandes nécessitent de faire appel au fonctions scanf et printf (qui sont très largement documentées par ailleurs). N'importe quel moteur de recherche te permettra de trouver des pages qui te permettront de les utiliser.

- j'ai utilisé un type long int. Ce type ne peut pas coder des nombres approximativement supérieurs à 2 milliards, donc bien que le programme fasse l'affichage pour n et p quelconques, en pratique n et p doivent être tels que n à la puissance p soit inférieur à deux milliards.

- pour le décalage, cela est du à la taille de la fenêtre de commande (dont on peut paramètrer la taille avec un clic droit puis propriétés me semble-t-il).

- tu peux éventuellement proposer tes modifications pour que l'on puisse les commenter, mais je n'écrirai pas le programme à ta place.

A bientôt.
Messages postés
1
Date d'inscription
lundi 6 août 2012
Statut
Membre
Dernière intervention
6 août 2012
1
Voici un programme tres court et tres efficace:

#include <stdio.h>
void main(int argc, char *argv[]) {
const int n = 5; const int k = 3;
int comb[40] = {0};
int i = 0;
while (i >= 0) {
if (comb[i] < n + i - k + 1) { comb[i]++;
if (i == k - 1) {
for (int j = 0; j < k; j++) printf("%d ", comb[j]); printf("\n");
} else { comb[++i] = comb[i - 1]; }
} else i--; } }
Oups je me suis trompé
les combinaisons de 1.2.3 avec p=2 sont :
12
13
23
Bonjour brah,

Est-ce que tu as trouvé un algorithme? Je recherche la même chose que toi par exemple si on a les boules 2,5,7
Faire une combinaison sans arrangement, sans répéition
2;5
2;7
5;7
Je recherche aussi un ensemble possible de 22 numéros et d'en faire sortir seulement 4 chiffres
Pas numéroté de 1 à 22.

Comme tu le mentionnes un semble de P éléments et en faire sortir n parmi les P et non de 1 à 49 ou 1 à 70
Merci!
Bonjour à tous je me suis à mon tour, penché sur cette question et je suis tombé sur ce post.
J'ai donc pris mon mal en patiente et tenté d'en faire un moi même. ce code est en Action script 2.0 (langage de flash) mais je pense que la syntaxe est proche du C à la déclaration de quelques variables près. j'ai tenté de commenter le code et je demeure ouvert à toute suggestion/optimisation:

//pour connaitre le nombre de combinaisons possibles
function c(k,n){
tot=1;
for(r=n;r>k;r--){tot*=r;}
for(r=(n-k);r>1;r--){tot/=r;}
return(tot);
}

//la fonction suivante retourne un tableau de longueur c(k,n),ou k représente la longueur du tableau passé en //paramètre, contenant pour chaque indice un tableau contenant n elements constituant une combinaison unique


function combi(arr_in,n){

//initialisation du tableau detiné à recevoir une combinaison par indice
//pour les languages n'autorisant pas la création de tableaux de longueur dynamique: //C(k,n)=n!/(k!(n-k)!),cf:fonction donnée plus haut
comb=[];

fini=false;
//initialisation d'un tableau de longueur n destiné à recevoir les n indices du tableau d'entrée reçu en paramètre //constituant un élément de la combinaison en cours
id=Array(n);
//affectation de valeurs croissantes -1 pour le dernier indice
for(cptid=0;cptid<n;cptid++){id[cptid]=cptid;}
id[n-1]=id[n-1]-1;

//l'algorithme avec k fixé prendrait l'allure de k boucles for imbriquées
//j'ai ici simulé un tel comportement par l'utilisation d'une boucle parcourant k avec une structure conditionnelle //testant le non dépassement des indices:
//incrémentation si non dépassement,changement de dimension de la boucle dans la clause else

while(!fini){
exit=false;
for(i=n-1;i>=0 && !exit;i--){
if(id[i]<arr_in.length-n+i){
id[i]++;
exit=true;
}else{
fini=(i==0);
first=true;
for(cpt=(n-i);cpt>0;cpt--){
id[n-cpt]=id[(n-1)-cpt]+((first)?2:1);
first=false;
}
}
}
if(!fini){
//construction du tableau contenant la combinaison en cours
arr_aux=Array(n);
for(cptid=0;cptid<n;cptid++){arr_aux[cptid]=arr_in[id[cptid]];}

//ajout de cette combinaison au tableau en contenant l'intégralité
comb.push(arr_aux);
}
}
return comb;
}

//test de la fonction
trace("["+combi(["A","B","C","D","E","F","G"],5).join("]"+chr(13)+"[")+"]");


voilà ceci fonctionne aussi avec un tableau d'entiers, ou même d'objets
attention, je n'ai pas mis de gestion d'erreur dans le cas ou le tableau serait plus petit que k, sous flash cela retourne un tableau vide, mais génèrera sans doute des erreurs dans un langage tel que C
Salut,

Pourrais-tu m'expliquer ton code en pseudocode car je ne connais pas du tout Action script. Je connais C, C++ et Java. Merci.
bonjour,

j'essaye de transcrire le code Action Script en C.
mais je suis bloqué sur " ((first)?2:1); ", pouvez vousme dire ce à quoi ca correspond en C, si vous savez bien sur?

Merci d'avance

Hugo
> hugo
Malheureusement je ne sais pas ce que veut dire ce code en C
Je ne sais pas si tu as trouvé ta solution mais j'ai fais un petit algo qui fait ca...
J'ai posté un petit résumé sur mon site : http://www.ogulrok.com/post/Petit_algo_pour_me_faire_perdre_mon_temps/102/default.aspx
Comme je dis dans mon "résumé", c'est pas l'algo du siècle mais bon ca fait la job (et c'est du C#)...
J'espère que ca t'aidera...
salut
sais-tu ce qu'est la récursivité ? à quoi ça sert ? comment s'en servir ?
Voilà un algorithme possible mais qui ne me satisfait pas vraiment car il faut éliminer les doublons, ce que fait la ligne "Instr......"

en VB

Sub Form_Load()

combinaison mot
End Sub

Sub combinaison(mot)

If Len(mot) = 1 Then Exit Sub
For i = 1 To Len(mot)
tmp = Left(mot, i - 1) & Mid(mot, i + 1)
If InStr(1, x, " " & tmp & " ") = 0 Then x = x & tmp & " ": Msgbox tmp :combinaison tmp
Next
End Sub