Trouver toutes les combinaisons d'un ensemble donné de chiffres

Pour examiner toutes les combinaisons sans savoir à l'avance combien de chiffres doivent avoir la sortie, j'ai écrit une fois ce code: xxx pré>

Il fait tout simplement dans un cycle pour éviter les appels de récursivité et de fonction frais généraux, toujours si "façonne" les besoins nécessaires pour des boucles à l'aide du tableau de pile.
Il se produit assez bien, sur mes 4 ans Athlon64 3800+, il prend 2 "4" de temps utilisateur (=> temps de calcul réel) pour générer des combinaisons 36 ^ 6 = 2176782336, il calcule donc environ 17,5 millions de combinaisons par seconde. P>

matteo@teoubuntu:~/cpp$ gcc -Wall -Wextra -ansi -pedantic -O3 combinations.c -o combinations.x
matteo@teoubuntu:~/cpp$ time ./combinations.x > /media/Dati/combinations.txt
Length of a combination: 6
Possible digit values (36 max): 36

real    13m6.685s
user    2m3.900s
sys 0m53.930s
matteo@teoubuntu:~/cpp$ head /media/Dati/combinations.txt
000000
000001
000002
000003
000004
000005
000006
000007
000008
000009
matteo@teoubuntu:~/cpp$ tail /media/Dati/combinations.txt
zzzzzq
zzzzzr
zzzzzs
zzzzzt
zzzzzu
zzzzzv
zzzzzw
zzzzzx
zzzzzy
zzzzzz
matteo@teoubuntu:~/cpp$ ls -lh /media/Dati/combinations.txt 
-rwxrwxrwx 1 root root 15G 2010-01-02 14:16 /media/Dati/combinations.txt
matteo@teoubuntu:~/cpp$ 

Voici mon implémentation C # 3.0 de permutations Vous pouvez trouver utile xxx

Vous devez écrire une fonction récursive qui se transforme dans la liste et chaque fois l'appelle à une liste mise à jour. Cela signifie qu'il doit créer une copie de la liste avec N-1 éléments pour passer à la prochaine itération. Pour les résultats, vous devez ajouter le numéro actuellement sélectionné dans chaque itération.

string Permutations(List numbers, string prefix)
{
   foreach (current_number in numbers)
   {
      new_prefix = prefix+"-"+number;
      new_list=make_copy_except(numbers,  current_number)
      if (new_list.Length==0)
           print new_prefix
      else
           Permutations(new_list, new_prefix)
   }
}

import Data.List (inits, tails)

place :: a -> [a] -> [[a]]
place element list = zipWith (\front back -> front ++ element:back)
                             (inits list)
                             (tails list)

perm :: [a] -> [[a]]
perm = foldr (\element rest -> concat (map (place element) rest)) [[]]

test = perm [1, 3, 14]

Combien de chiffres et lesquels ne sont pas deux questions. Si vous savez quels chiffres, vous savez combien.

Et les noms des chiffres ne sont pas très intéressants. 1-3-14 ou 0-1-2 ou FOO-BAR-BAZ - C'est toujours le même problème, le même problème que les permutations de 0-1-2 et avec une matrice, où rechercher le résultat. p> xxx pré>

La solution la plus pratique est, pour écrire un générique itérable. Ensuite, vous pouvez utiliser la boucle de la boucle simplifiée pour accéder à chaque permutation. P>

import java.util.*;

class PermutationIterator <T> implements Iterator <List <T>> {

    private int  current = 0;
    private final long last;
    private final List <T> lilio;

    public PermutationIterator (final List <T> llo) {
        lilio = llo;
        long product = 1;
        for (long p = 1; p <= llo.size (); ++p) 
            product *= p; 
        last = product;
    }

    public boolean hasNext () {
        return current != last;
    }

    public List <T> next () {
        ++current;
        return get (current - 1, lilio);
    }

    public void remove () {
        ++current;
    }

    private List <T> get (final int code, final List <T> li) {
        int len = li.size ();
        int pos = code % len;
        if (len > 1) {
            List <T> rest = get (code / len, li.subList (1, li.size ()));
            List <T> a = rest.subList (0, pos);
            List <T> res = new ArrayList <T> ();
            res.addAll (a);
            res.add (li.get (0));
            res.addAll (rest.subList (pos, rest.size ()));
            return res;
        }
        return li;
    }
}

class PermutationIterable <T> implements Iterable <List <T>> {

    private List <T> lilio; 

    public PermutationIterable (List <T> llo) {
        lilio = llo;
    }

    public Iterator <List <T>> iterator () {
        return new PermutationIterator <T> (lilio);
    }
}

class PermutationIteratorTest {

    public static void main (String[] args) {
        List <Integer> la = Arrays.asList (new Integer [] {1, 3, 14});
        PermutationIterable <Integer> pi = new PermutationIterable <Integer> (la);
        for (List <Integer> lc: pi)
            show (lc);
    }

    public static void show (List <Integer> lo) {
        System.out.print ("(");
        for (Object o: lo)
            System.out.print (o + ", ");
        System.out.println (")");
    }
}