Discussion :

[siempre]

Bonjour,

Je voulais afficher toutes les combinaisons possibles de taille 2, de taille 3 jusqu'à taille N.
par exemple on a 4 mots(chaine de caractère):

un
deux
trois
quatre

les combinaisons possibles de taille 2 jusqu'à taille 4 sont :

un deux
un trois
un quatre
deux trois
deux quatre
trois quatre
un deux trois
un deux quatre
un trois quatre
deux trois quatre
un deux trois quatre

On a N = 4 et le nombre de combinaisons = 11

Avez vous une idée?


Merci.

[Jedai]

C'est l'ensemble des parties de taillle donnée ton algorithme. Tu peux faire ça récursivement :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
nparts :: Int -> [a] -> [[a]]
nparts 0 _ = [[]]
nparts n xs = [y : ys | y : tl <- tails xs, ys <- nparts (n-1) tl]

Autrement dit :

Code Algo :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
nparts(0,anything) = {emptyset}
nparts(n, {x1..xk}) = { {xi} U subpart / i in [1,k], subpart in nparts(n-1, {x(i+1)..xk} }

Après tu peux juste faire l'union des nparts(2..4) ou adapter cet algo pour éviter de recalculer plusieurs fois les mêmes tailles.

--
Jedaï

[siempre]

Bonjour,

J'ai trouvé dans cette solution dans le net:

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
#define N 5
void afficher(int etat[], char *t[])
{
  int i;
  for (i = 0; i < N; i++)
    if (etat[i])
      printf("%s ", t[i]);
  puts("");
}
 
void partie(int h, int etat[], char *t[])
{
  enum { ABSENT, PRESENT };
  if (h < 0)
    afficher(etat, t);
  else
    {
      etat[h] = ABSENT;
      partie(h - 1, etat, t);
      etat[h] = PRESENT;
      partie(h - 1, etat, t);
    }
}
 
int main(void)
{
  char *t[N] = { "nom", "prenom", "age", "adresse", "emploi" };
  int etat[N];
  partie(N - 1, etat, t);
  return 0;
}

- Je ne sais pas pourquoi le résultat n'affiche pas les combinaisons dans l'ordre taille2, taille3,taille4,taille5 ?

- Quelles modification à faire pour obtenir les combinaisons dans l'ordre car ceci m'aider à ne parcourir toutes les combinaisons par exemple si je voulais parcourir jusqu'à taille2 alors je boucle seulement jusqu'à taille 2 ?

Je vois que le code de cette solution est réduit. Est ce que c'est la meilleure solution au niveau la moins consommation en mémoire par rapport aux autres solutions ?

Merci.

[souviron34]

c'est pas beau de poster en double


Maintenant, comme je te l'ai dit sur le forum C, si tu écrivais EN TEXTE ton algprithme en faisant marcher ton cerveau et ta rflexion au lieu de prendre un code récupéré et de le modifier, cela fait déjà un moment que tu aurais la solution..

Et ici, sur ce forum Algorithme, on ne s'occupe pas du code mais de la description de l'algorithme..

Ce qu'on attend de toi