-

Salut,

euh y'a un truc qui déconne dans ta formulaire déjà !
quand je vois n! / n! j'ai envie de simplifier ... donc ça devenait simple :aie:
Par contre...
(n) = n! / (k! (n-k)!) est plus juste !
(k)


Bonne chance pour l'algorithme !

@+,
Emilien.

-

Salut,

Si j'ai bien compris, tu veux faire un algorithme récursif qui à partir de la liste {a,b,c,d,e} calcule les différentes combinaisons avec un caractère de plus.
C'est à dire si tu demande à ton algorithme, un niveau 3, tu aura :
{a,b,c,d,e} -> {(ab),(ac),...} -> {(abc),(abd),(abe),...}

Dans ce cas, il faut rajouter à chaque élément du niveau précédent, un caractère qui n'est pas déjà présent. Et ceci en testant tous les caractères.

Pour un niveau 2, on regarde le résultat du niveau 1 : {a,b,c,d,e}, on essaye de mettre un 'a' au premier élément, ça marche pas, on passe au 'b'. On obtient (ab) et on continue comme ca jusqu'à avoir essayer tous les caractères.

Pour un niveau 3, on a le niveau 2 {(ab),(ac),..}.
Idem on teste 'a' pour (ab), ça marche pas,..., on teste pour 'c', c'est bon, on rajoute donc (abc).

Je ne sais pas si t'arrive à comprendre mon algorithme mais si ca t'intéresse je pourrais le coder.

-

Oui j'avais bien compris en fait mais je me suis rendu compte que mon algorithme ne marchait pas comme il fallait. Mais dans l'idée l'algorithme récursif se sert du résultat du niveau inférieur.

Il faut donc trouver le moyen de passer de {a,b,c,d,e} à {(ab),(ac),...} sans savoir à quel niveau on est.

Avec mon idée, ça rajoutait sans se soucier si (ab) + c et (ac) + b allait faire la même chose. Donc peut être avec un contrôle derrière ça pourrait marcher mais ca fait lourd de passer par tous les niveaux pour un niveau 5!

Il faut que je réfléchisse encore un peu ^^!

-

Voilà, j'ai trouvé un petit algorithme récursif qui effectue ce que tu demande.
Il suffit de modifier "niveau" pour choisir combien tu veux prendre de caractère parmi "liste".
L'algorithme gère automatiquement le changement de taille de "liste" donc il n'y a presque rien à faire pour avoir les combinaisons demandées.

J'ai fait ça rapidement donc le code est pas nickel mais j'espère que ça t'aidera et si tu veux des précisions, n'hésite pas.

public class Combi {

	static char[] liste = new char[] {'a','b', 'c', 'd', 'e' };//, 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
	static int[] nb;
	static int i=0,niveau;
	
	public static void main(String[] args) {
		niveau=5;
		nb= new int[liste.length];
		for(nb[0]=0; nb[0]<liste.length;nb[0]++){
			algorithme(1,niveau);
		}
	}

	public static void algorithme(int k,int max){
		if(k<max){
			for(nb[k]=nb[k-1]+1; nb[k]<liste.length;nb[k]++){
				algorithme(k+1,max);
			}

		}
		else{
			boolean premier=true;
			i++;
			String ligne = "L" + i + ":{";
			for(int i=0;i<niveau;i++){
				if(premier){
					ligne += liste[nb[i]];
					premier=false;
				}else{
					ligne+=";" + liste[nb[i]];
				}
			}
			ligne += "}";
			System.out.println(ligne);
		}
	}
}

-

Pour ceux qui sont intérréssés par le problème avec une solution qui n'utilise pas la récursivité :

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] tabvariable = { "A","B","C","D","E"};
            double NbrCombinaison = Math.Pow(2, tabvariable.Length);
            string[,] tab = new string[(int)NbrCombinaison,(int)tabvariable.Length];
            tab = FabrikCombinaison(tabvariable,(int)(NbrCombinaison));
            affichage(tab,(int)NbrCombinaison,(int)tabvariable.Length);
            Console.Read();
        }

        public static void affichage(string[,] tab,int NbrLigne,int NbrVariable)
    {
        for (int ligne = 0; ligne <= NbrLigne - 1; ligne++)
        {
            for (int colonne = 0; colonne <= NbrVariable - 1; colonne++)
            {
                Console.Write(tab[ligne, colonne]+" ");
            }
            Console.WriteLine("");
        }
    }

        public static string[,] FabrikCombinaison(string[] TableauDeValeur, int NbrCombiPossible)
        {
            string[,] Tableau = new string[NbrCombiPossible,TableauDeValeur.Length];

            for (int indexcol = 0; indexcol <= TableauDeValeur.Length - 1; indexcol++)
            {
                // Ligne
                double NbrBloc = Math.Pow(2,indexcol+1);// Calcul le nombre de bloc dans une colonne
                int BlocActuel = 0;
                for (int ligne = 0; ligne <= NbrCombiPossible-1; ligne++)
                {
                    if(ligne%(NbrCombiPossible/NbrBloc)==0 && ligne !=0)
                    {
                        BlocActuel++;
                    }
                    if (BlocActuel % 2==0)
                    {
                        Tableau[ligne, indexcol] = TableauDeValeur[indexcol];
                    }
                    else
                    {
                        Tableau[ligne, indexcol] = " ";
                    }
                }
            }
            return Tableau;
        }
    }
}

-
Edité par aureo91 10 janvier 2014 à 14:20:09

comment faire marcher cet algo quand on a 100 valeurs differentes ?

Bonjour,

@astron Merci de ne pas supprimer vos interventions cela rend la discussion incompréhensible. 

@SimonLeclercq Merci de ne pas déterrer d'anciens sujet résolu

Déterrage

Citation des règles générales du forum :

Avant de poster un message, vérifiez la date du sujet dans lequel vous comptiez intervenir.

Si le dernier message sur le sujet date de plus de deux mois, mieux vaut ne pas répondre.
En effet, le déterrage d'un sujet nuit au bon fonctionnement du forum, et l'informatique pouvant grandement changer en quelques mois il n'est donc que rarement pertinent de déterrer un vieux sujet.

Au lieu de déterrer un sujet il est préférable :

• soit de contacter directement le membre voulu par messagerie privée en cliquant sur son pseudonyme pour accéder à sa page profil, puis sur le lien "Ecrire un message"
• soit de créer un nouveau sujet décrivant votre propre contexte
• ne pas répondre à un déterrage et le signaler à la modération

Je ferme ce sujet. En cas de désaccord, me contacter par MP.