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
A voir également:
Fonction combinaison en c
Algorithme combinaison p parmi n - Meilleures réponses
Algorithme combinaison k parmi n - Meilleures réponses
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:
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)
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);
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.
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
- 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.
#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--; } }
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
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?
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...
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
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;
}