642 votes

Algorithme permettant de retourner toutes les combinaisons de k éléments parmi n

Je veux écrire une fonction qui prend un tableau de lettres comme argument et un nombre de ces lettres à sélectionner.

Disons que vous fournissez un tableau de 8 lettres et que vous voulez en sélectionner 3. Alors vous devriez obtenir :

8! / ((8 - 3)! * 3!) = 56

Des tableaux (ou mots) en retour composés de 3 lettres chacun.

4 votes

Une préférence pour un langage de programmation ?

9 votes

Comment voulez-vous traiter les lettres en double ?

0 votes

Pas de préférence de langage, je vais le coder en ruby mais une idée générale des algorithmes à utiliser serait bien. Deux lettres de même valeur peuvent exister mais pas la même lettre deux fois.

3voto

user2648503 Points 3

Une solution Javascript concise :

Array.prototype.combine=function combine(k){    
    var toCombine=this;
    var last;
    function combi(n,comb){             
        var combs=[];
        for ( var x=0,y=comb.length;x<y;x++){
            for ( var l=0,m=toCombine.length;l<m;l++){      
                combs.push(comb[x]+toCombine[l]);           
            }
        }
        if (n<k-1){
            n++;
            combi(n,combs);
        } else{last=combs;}
    }
    combi(1,toCombine);
    return last;
}
// Example:
// var toCombine=['a','b','c'];
// var results=toCombine.combine(4);

2voto

daveb Points 24831

http://web.archive.org/web/20120608031204/http://www.merriampark.com/comb.htm

Ce lien contient une explication et le code source d'un CombinationGenerator.

2voto

Bob Bryan Points 1312

J'ai écrit une classe pour gérer les fonctions courantes pour travailler avec le coefficient binomial, qui est le type de problème dont votre problème relève. Elle effectue les tâches suivantes :

  1. Produit tous les K-index dans un format agréable pour tout N choisi K vers un fichier. Les indices K peuvent être remplacés par des chaînes de caractères ou des lettres plus descriptives. Cette méthode rend la résolution de ce type de problème assez triviale.

  2. Convertit les indices K en l'indice approprié d'une entrée dans la table des coefficients binomiaux triés. Cette technique est beaucoup plus rapide que les anciennes techniques publiées qui reposent sur l'itération. Pour ce faire, elle utilise une propriété mathématique inhérente au triangle de Pascal. Mon article en parle. Je pense être le premier à avoir découvert et publié cette technique, mais je peux me tromper.

  3. Convertit l'indice d'une table de coefficients binomiaux triés en indices K correspondants.

  4. Utilisations Mark Dominus pour calculer le coefficient binomial, qui est beaucoup moins susceptible de déborder et fonctionne avec de plus grands nombres.

  5. La classe est écrite en .NET C# et fournit un moyen de gérer les objets liés au problème (s'il y en a) en utilisant une liste générique. Le constructeur de cette classe prend une valeur bool appelée InitTable qui, lorsqu'elle est vraie, crée une liste générique pour contenir les objets à gérer. Si cette valeur est false, alors il ne créera pas la table. La table n'a pas besoin d'être créée pour exécuter les 4 méthodes ci-dessus. Des méthodes accesseurs sont fournies pour accéder à la table.

  6. Il existe une classe de test associée qui montre comment utiliser la classe et ses méthodes. Elle a été testée de manière approfondie avec 2 cas et il n'y a pas de bogues connus.

Pour en savoir plus sur cette classe et télécharger le code, voir Tabulation de la coefficience binomiale .

Il ne devrait pas être difficile de convertir cette classe en C++.

2voto

q81 Points 431

Algorithme php court pour retourner toutes les combinaisons de k éléments de n (coefficient binomial) basé sur la solution java :

$array = array(1,2,3,4,5);

$array_result = NULL;

$array_general = NULL;

function combinations($array, $len, $start_position, $result_array, $result_len, &$general_array)
{
    if($len == 0)
    {
        $general_array[] = $result_array;
        return;
    }

    for ($i = $start_position; $i <= count($array) - $len; $i++)
    {
        $result_array[$result_len - $len] = $array[$i];
        combinations($array, $len-1, $i+1, $result_array, $result_len, $general_array);
    }
} 

combinations($array, 3, 0, $array_result, 3, $array_general);

echo "<pre>";
print_r($array_general);
echo "</pre>";

La même solution mais en javascript :

var newArray = [1, 2, 3, 4, 5];
var arrayResult = [];
var arrayGeneral = [];

function combinations(newArray, len, startPosition, resultArray, resultLen, arrayGeneral) {
    if(len === 0) {
        var tempArray = [];
        resultArray.forEach(value => tempArray.push(value));
        arrayGeneral.push(tempArray);
        return;
    }
    for (var i = startPosition; i <= newArray.length - len; i++) {
        resultArray[resultLen - len] = newArray[i];
        combinations(newArray, len-1, i+1, resultArray, resultLen, arrayGeneral);
    }
} 

combinations(newArray, 3, 0, arrayResult, 3, arrayGeneral);

console.log(arrayGeneral);

2voto

Akkuma Points 2013

Voici ma solution JavaScript qui est un peu plus fonctionnelle grâce à l'utilisation de reduce/map, qui élimine presque toutes les variables.

function combinations(arr, size) {
  var len = arr.length;

  if (size > len) return [];
  if (!size) return [[]];
  if (size == len) return [arr];

  return arr.reduce(function (acc, val, i) {
    var res = combinations(arr.slice(i + 1), size - 1)
      .map(function (comb) { return [val].concat(comb); });

    return acc.concat(res);
  }, []);
}

var combs = combinations([1,2,3,4,5,6,7,8],3);
combs.map(function (comb) {
  document.body.innerHTML += comb.toString() + '<br />';
});

document.body.innerHTML += '<br /> Total combinations = ' + combs.length;

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X