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

Question

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.

Answer 1

Version de Clojure :

(defn comb [k l]
  (if (= 1 k) (map vector l)
      (apply concat
             (map-indexed
              #(map (fn [x] (conj x %2))
                    (comb (dec k) (drop (inc %1) l)))
              l))))

Answer 2

Code python court, donnant des positions d'indice

def yield_combos(n,k):
    # n is set size, k is combo size

    i = 0
    a = [0]*k

    while i > -1:
        for j in range(i+1, k):
            a[j] = a[j-1]+1
        i=j
        yield a
        while a[i] == i + n - k:
            i -= 1
        a[i] += 1

Answer 3

Algorithme :

• Comptez de 1 à 2^n.
• Convertir chaque chiffre en sa représentation binaire.
• Traduisez chaque bit "on" en éléments de votre jeu, en fonction de leur position.

En C# :

void Main()
{
    var set = new [] {"A", "B", "C", "D" }; //, "E", "F", "G", "H", "I", "J" };

    var kElement = 2;

    for(var i = 1; i < Math.Pow(2, set.Length); i++) {
        var result = Convert.ToString(i, 2).PadLeft(set.Length, '0');
        var cnt = Regex.Matches(Regex.Escape(result),  "1").Count; 
        if (cnt == kElement) {
            for(int j = 0; j < set.Length; j++)
                if ( Char.GetNumericValue(result[j]) == 1)
                    Console.Write(set[j]);
            Console.WriteLine();
        }
    }
}

Pourquoi cela fonctionne-t-il ?

Il existe une bijection entre les sous-ensembles d'un ensemble à n éléments et les séquences à n bits.

Cela signifie que nous pouvons déterminer combien de sous-ensembles il y a en comptant les séquences.

Par exemple, l'ensemble de quatre éléments ci-dessous peut être représenté par {0,1} X {0, 1} X {0, 1} X {0, 1} (ou 2^4) séquences différentes.

Alors tout ce que nous avons à faire est de compter de 1 à 2^n pour trouver toutes les combinaisons. (Nous ignorons l'ensemble vide.) Ensuite, traduisez les chiffres en leur représentation binaire. Ensuite, remplacez les éléments de votre ensemble par des bits "on".

Si vous ne voulez que les résultats de k éléments, n'imprimez que lorsque k bits sont activés.

(Si vous voulez tous les sous-ensembles au lieu des sous-ensembles de longueur k, supprimez la partie cnt/kElement).

(Pour la preuve, voir le didacticiel gratuit du MIT Mathematics for Computer Science, Lehman et al, section 11.2.2. https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/ )

Answer 4

Voici une méthode qui vous donne toutes les combinaisons de taille spécifiée à partir d'une chaîne de longueur aléatoire. Similaire à la solution de quinmars, mais fonctionne pour des entrées et k variés.

Le code peut être modifié pour être enveloppé, par exemple 'dab' à partir de l'entrée 'abcd' avec k=3.

public void run(String data, int howMany){
    choose(data, howMany, new StringBuffer(), 0);
}

//n choose k
private void choose(String data, int k, StringBuffer result, int startIndex){
    if (result.length()==k){
        System.out.println(result.toString());
        return;
    }

    for (int i=startIndex; i<data.length(); i++){
        result.append(data.charAt(i));
        choose(data,k,result, i+1);
        result.setLength(result.length()-1);
    }
}

Sortie pour "abcde" :

abc abd abe acd ace ade bcd bce bde cde

Answer 5

Tout est dit et fait, voici le code O'caml pour cela. L'algorithme est évident à partir du code

let combi n lst =
    let rec comb l c =
        if( List.length c = n) then [c] else
        match l with
        [] -> []
        | (h::t) -> (combi t (h::c))@(combi t c)
    in
        combi lst []
;;