De quel type d'algorithme ai-je besoin?

Question

J'essaie de comprendre toutes les différentes façons que je peux créer des groupes de 4 à partir de 6 objets en utilisant l'objectif-c.

Par exemple, si j'avais les objets suivants: a, b, c, d, e, f

Je pourrais créer des groupes comme

a, b, c, d

b, c, d, e

a, d, e, f

et ainsi de suite. L'ordre n'a pas d'importance. Si je voulais comprendre toutes les différentes possibilités, de quel type d'algorithme ai-je besoin? Au début, je pensais aux permutations, mais je ne pense pas que ce soit ça. Je pense qu'il pourrait y avoir quelque chose de plus rapide ou de plus approprié, mais j'ai oublié comment ça s'appelle.

Answer 1

Si vous devez sélectionner 4 objets différents de toutes les manières possibles, cela signifie que vous devez supprimer (ne pas sélectionner) deux autres objets de toutes les manières possibles. Juste deux boucles:

for (int i = 0; i < 6; ++i) { 
    for (int j = i + 1; j < 6; ++j) { 
     // here we select all elements except i and j 
    } 
} 

Pas très extensible si le nombre d'objets augmente, mais assez simple.

(je suppose que l'ordre n'a pas d'importance: il semble donc de vos exemples)

Answer 2

Permutation est le bon endroit pour commencer. Une méthode de force brute serait de trouver toutes les six permutations de chaîne et de saisir les quatre premiers et de les ajouter à un ensemble. Terriblement inefficace, cependant.

L'algorithme de permutation de base pourrait être modifié pour générer seulement des groupes de quatre.

Consultez cette page: http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

Answer 3

Voici une approche récursive, écrit en Java, adapté pour le cas général:

public static void comb(int[] arr, int m) { 
    comb(arr, m, 0, new ArrayList<Integer>()); 
} 

public static void comb(int[] arr, int m, int ind, ArrayList<Integer> s) { 
    int left = m - s.size(); 
    if (left == 0) { 
     System.out.println(s); 
     return; 
    } 

    if (left > arr.length - ind) 
     return; 
    comb(arr, m, ind + 1, s); 
    s.add(arr[ind]); 
    comb(arr, m, ind + 1, s); 
    s.remove(s.size()-1); 
} 

branches Il identifie chaque fois qu'il trouve un élément et doit décider si pour l'inclure ou non. Il existe également une optimisation de l'élagage pour éviter les impasses.