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
Les tableaux (ou mots) en retour sont composés de 3 lettres chacun.
Un problème que vous rencontrerez est bien sûr la mémoire et assez rapidement, vous aurez des problèmes avec 20 éléments dans votre ensemble -- 20C3 = 1140. Et si vous voulez itérer sur l’ensemble, il est préférable d’utiliser un algorithme de code gris modifié pour ne pas avoir à les garder tous en mémoire. Ceux-ci génèrent la combinaison suivante à partir de la précédente et évitent les répétitions. Il en existe de nombreux pour différents usages. Veut-on maximiser les différences entre les combinaisons successives ? minimiser ? et cetera. Quelques-uns des articles originaux décrivant les codes gris :
Vous pouvez également référencer une combinaison par son index (dans l'ordre lexicographique). En réalisant que l'indice doit être une certaine quantité de changement de droite à gauche basée sur l'indice, nous pouvons construire quelque chose qui devrait récupérer une combinaison. Ainsi, nous avons un ensemble {1,2,3,4,5,6}... et nous voulons trois éléments. Disons que {1,2,3} nous pouvons dire que la différence entre les éléments est de un et dans l'ordre et minimale. {1,2,4} a un changement et est lexicographiquement numéro 2. Ainsi, le nombre de 'changements'dans la dernière place représente un changement dans l'ordre lexicographique. La deuxième place, avec un changement {1,3,4} a un changement mais représente plus de changement puisqu'elle est à la deuxième place (proportionnellement au nombre d'éléments dans l'ensemble original). La méthode que j'ai décrite est une déconstruction, car il semble que, de l'ensemble à l'indice, il faille faire l'inverse - ce qui est beaucoup plus délicat. Voici comment [Buckles][10] résout le problème. J'ai écrit un peu de [C pour les calculer][11], avec des changements mineurs - j'ai utilisé l'indice des ensembles plutôt qu'une plage de nombres pour représenter l'ensemble, de sorte que nous travaillons toujours à partir de 0...n. Note :
Il existe [une autre méthode][12] : son concept est plus facile à comprendre et à programmer, mais il ne bénéficie pas des optimisations de Buckles. Heureusement, elle ne produit pas non plus de combinaisons en double :
L'ensemble [ ![x_k...x_1 dans N][13]] qui maximise [ ![i = C(x_1,k) + C(x_2,k-1) + ... + C(x_k,1)][14]][14], où [ ![C(n,r) = {n choisir r}][15]][15].
Par exemple : 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1)
. Ainsi, la 27ème combinaison lexicographique de quatre choses est : {1,2,5,6}, ce sont les indices de l'ensemble que vous voulez regarder. L'exemple ci-dessous (OCaml), nécessite la fonction choose
, de gauche à droite :
(* this will find the [x] combination of a [set] list when taking [k] elements *)
let combination_maccaffery set k x =
(* maximize function -- maximize a that is aCb *)
(* return largest c where c < i and choose(c,i) <= z *)
let rec maximize a b x =
if (choose a b ) <= x then a else maximize (a-1) b x
in
let rec iterate n x i = match i with
| 0 -> []
| i ->
let max = maximize n i x in
max :: iterate n (x - (choose max i)) (i-1)
in
if x < 0 then failwith "errors" else
let idxs = iterate (List.length set) x k in
List.map (List.nth set) (List.sort (-) idxs)
Les deux algorithmes suivants sont fournis à des fins didactiques. Ils implémentent un itérateur et un dossier (plus général) de combinaisons globales.
Ils sont aussi rapides que possible, ayant la complexité O(nCk). La consommation mémoire est limitée par k
.
Nous commencerons par l'itérateur, qui appellera une fonction fournie par l'utilisateur pour chaque combinaison
let iter_combs n k f =
let rec iter v s j =
if j = k then f v
else for i = s to n - 1 do iter (i::v) (i+1) (j+1) done in
iter [] 0 0
Une version plus générale appellera la fonction fournie par l'utilisateur avec la variable d'état, en commençant par l'état initial. Puisque nous devons faire passer l'état entre différents états, nous n'utiliserons pas la boucle for, mais plutôt la récursion,
let fold_combs n k f x =
let rec loop i s c x =
if i < n then
loop (i+1) s c @@
let c = i::c and s = s + 1 and i = i + 1 in
if s < k then loop i s c x else f c x
else x in
loop 0 0 [] x
[1] : http://portal.acm.org/citation.cfm?id=1036677&dl=&coll= [2] : http://portal.acm.org/citation.cfm?id=2422.322413 [3] : http://portal.acm.org/citation.cfm?id=49203&jmp=indexterms&coll=GUIDE&dl=GUIDE&CFID=81503149&CFTOKEN=96444237 [4] : http://www.cs.uvic.ca/~ruskey/Publications/EHR/HoughRuskey.pdf (en anglais) [5] : http://portal.acm.org/citation.cfm?doid=355826.355830 [6] : http://www4.ncsu.edu/~savage/AVAILABLE_FOR_MAILING/survey.ps [7] : http://www.springerlink.com/content/7lvmm575n85xv5v0/ [8] : http://portal.acm.org/citation.cfm?id=362502 [9] : http://www.netlib.no/netlib/toms/382 [10] : http://portal.acm.org/citation.cfm?id=355739 [11] : https://stackoverflow.com/questions/561/using-combinations-of-sets-as-test-data#794 [12] : https://web.archive.org/web/20170325012457/https://msdn.microsoft.com/en-us/library/aa289166.aspx [13] : http://i.stack.imgur.com/Txetz.gif [14] : http://i.stack.imgur.com/HOj5o.gif [15] : http://i.stack.imgur.com/vIeiI.gif
Supposons que votre tableau de lettres ressemble à ceci : "ABCDEFGH" ;. Vous avez trois indices (i, j, k) indiquant les lettres que vous allez utiliser pour le mot en cours, Vous commencez par :
A B C D E F G H ^ ^ ^ i j k
D'abord vous faites varier k, donc l'étape suivante ressemble à ça :
A B C D E F G H ^ ^ ^ i j k
Si vous avez atteint la fin, vous continuez et faites varier j puis k à nouveau.
A B C D E F G H ^ ^ ^ i j kA B C D E F G H ^ ^ ^ i j k
Une fois que vous avez atteint G, vous commencez aussi à faire varier i.
A B C D E F G H ^ ^ ^ i j kA B C D E F G H ^ ^ ^ i j k ...
Écrit en code, cela ressemble à quelque chose comme ça
void print_combinations(const char *string)
{
int i, j, k;
int len = strlen(string);
for (i = 0; i < len - 2; i++)
{
for (j = i + 1; j < len - 1; j++)
{
for (k = j + 1; k < len; k++)
printf("%c%c%c\n", string[i], string[j], string[k]);
}
}
}
static IEnumerable<string> Combinations(List<string> characters, int length)
{
for (int i = 0; i < characters.Count; i++)
{
// only want 1 character, just return this one
if (length == 1)
yield return characters[i];
// want more than one character, return this one plus all combinations one shorter
// only use characters after the current one for the rest of the combinations
else
foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))
yield return characters[i] + next;
}
}