Outils pour utilisateurs

Outils du site


informatique:permuration

Permutation

Et non Combinatoire parait-il ; je ne sais pas, je suis nul en math.

Les permutations donnent rapidement de grands nombres de possibilités:

Numérique Num+alpha num+alpha min+ Alpha maj num+alpha min+ Alpha maj + Symb
nb positions 10 chars 36 chars 62 chars 104 chars
4 10 000 1 679 616 14 776 336 116 985 856
5 100 000 60 466 176 916 132 832 12 166 529 024
6 1 000 000 2 176 782 336 56 800 235 584 1 265 319 018 496
7 10 000 000 78 364 164 096 3 521 614 606 208 131 593 177 923 584
8 100 000 000 2 821 109 907 456 218 340 105 584 896 13 685 690 504 052 736
9 1 000 000 000 101 559 956 668 416 13 537 086 546 263 552 1 423 311 812 421 484 544
10 10 000 000 000 3 656 158 440 062 976 839 299 365 868 340 224 148 024 428 491 834 392 576
12 1 000 000 000 000 4 738 381 338 321 616 896 3 226 266 762 397 899 816 960 1 601 032 218 567 680 790 102 016

Exploration de toutes les possibilités autour d'un jeu de caractères et d'un nombre de position:

import java.util.ArrayList;
import java.util.List;
 
/**
 * build & run:
 * javac -Xlint:unchecked Permutations.java && java -Xmx4096m Permutations
 * with CPU afinity :
 * javac -Xlint:unchecked Permutations.java && taskset -c 1 java -Xmx4096m Permutations
 * 
 * @author cyrille
 */
class Permutations {
 
    static long resultCount = 0;
 
    public static void main(String args[]) {
 
        /*
        // 104 chars
        char[] choices = new char[] {
        'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
        'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
        '0','1','2','3','4','5','6','7','8','9',
        ',',';',':','!','?','.','/','§','&','é','"','\'', '(','-','è','_','ç','à',')','=',
        '~','²','#','{','[','|','`','\\','^','@',']','}','^','"','$','£','ù','%','*','µ','<','>'
        };
         */
        // 10 chars
        char[] choices = new char[]{
            '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'
        };
        int nMin = 2;
        int nMax = 9;
 
        WL("Computing ...");
        WL("Parameters: nMin=" + nMin + ", nMax=" + nMax + ", choices=" + choices.length);
 
        long start = System.nanoTime();
 
        List<String> result = new ArrayList<String>();
 
        permute(choices, result, nMin, nMax);
 
        long elapsedTime = System.nanoTime() - start;
 
        //for (String s : result) {
        //    WL(padLeft(s, nMax));
        //}
 
        WL("Parameters: nMin=" + nMin + ", nMax=" + nMax + ", choices=" + choices.length + ", result=" + result.size() + ", resultCount=" + resultCount);
        WL("Elapsed time= " + (elapsedTime / 1000.0 / 1000.0) + " ms, " + (elapsedTime / 1000.0 / 1000.0 / 1000.0) + " s");
    }
 
    public static void WL(String s) {
        System.out.println(s);
    }
 
    public static String padRight(String s, int n) {
        return String.format("%1$-" + n + "s", s);
    }
 
    public static String padLeft(String s, int n) {
        return String.format("%1$#" + n + "s", s);
    }
 
    public static void permute(char[] choices, List<String> result, int min, int max) {
 
        //
        // nombre de résultats : choices.length ^ i
        //
        for (int i = min; i <= max; i++) {
            //List<String> tmpResult = new ArrayList<String>();
            long stepCount = resultCount;
            long start = System.nanoTime();
 
            permuteDepth(choices, result, "", i);
 
            long elapsedTime = System.nanoTime() - start;
            WL("step: i=" + i + ", result=" + result.size() + ", stepCount=" + (resultCount - stepCount)+", elapsedTime="+(elapsedTime / 1000.0 / 1000.0) + " ms");
        }
    }
 
    public static void permuteDepth(char[] choices, List<String> result, String prefix, int pos) {
 
        for (int i = 0; i < choices.length; i++) {
            String newPrefix = prefix + choices[i];
            if (pos == 1) {
 
                addResult(result, newPrefix);
 
            } else {
                permuteDepth(choices, result, newPrefix, pos - 1);
            }
        }
 
    }
 
    public static void addResult(List<String> result, String resStr) {
 
        resultCount++;
        //result.add(resStr);
    }
}
informatique/permuration.txt · Dernière modification: 19/05/2012 00:18 (modification externe)