Permutationen



  • std::string default = "12345";
    
    int perm=1, digits=default.size();
    for (int i=1;i<=digits;perm*=i++);
    for (int a=0;a<perm;a++)
    {
    	std::string avail=default;
    	for (int b=digits,div=perm;b>0; b--) 
    	{
    		div/=b;
    		int index = (a/div)%b;
    		printf("%c", avail[index] );
    		//avail[index]=avail[b-1]; // fast but not lexigraphic order
    		avail.erase(index,1) ; // lexigraphic correct order
    	}
    	printf("\n");
    }
    printf("permutations:%d\n",perm);
    

    Fast, non-recursive & simple

    (c) Sven Forstmann



  • Link zu Permutation.zip ist tot.

    -- perm.hs
    import Data.List
    
    main :: IO ()
    main = do line <- getLine
              putStrLn $ show $ length $ permutations line
    
    > ghci perm.hs -O3
    > time echo "ABCDJAFGIH" | ./a.out
    3628800
    
    real    0m0.383s
    user    0m0.352s
    sys     0m0.009s
    

    Das Testsystem war ein Pentium 4 mit 2.8 GHz. Wie vergleichbar diese Werte mit der C/C++ Variante sind, ist wegen Haskells Laziness nicht zu sagen.



  • knivil schrieb:

    Link zu Permutation.zip ist tot.

    -> Ich wiederhole: Link zu Permutation.zip ist tot.
    Over&Out



  • Ich schau mal was ich tun kann...



  • Permutationen.zip ist wieder verfügbar.



  • Kurze (eher nebensächliche) Frage:
    Ist das Beispiel mit dem Zahlencode und den Fingerabdrücken nicht ein wenig scheiße? Wenn die vier Tasten bekannt sind, könnte sich eine Taste ja durchaus wiederholen, dann ist die Berechnung der kombinatorischen Möglichkeiten eben keine Fakultät.


  • Mod

    LOLAlter schrieb:

    Kurze (eher nebensächliche) Frage:
    Ist das Beispiel mit dem Zahlencode und den Fingerabdrücken nicht ein wenig scheiße? Wenn die vier Tasten bekannt sind, könnte sich eine Taste ja durchaus wiederholen, dann ist die Berechnung der kombinatorischen Möglichkeiten eben keine Fakultät.

    Wie willst du denn aus vier verschiedenen Ziffern eine vierstellige Folge generieren, bei der es Wiederholungen gibt?



  • SeppJ schrieb:

    Wie willst du denn aus vier verschiedenen Ziffern eine vierstellige Folge generieren, bei der es Wiederholungen gibt?

    Wahrscheinlich fährt er Toyota 😃



  • Erstmal vielen Dank für den super Beitrag an den Threadersteller.

    Ich hätte jedoch eine kleine Frage zu dem STL Algorithmus und zwar möchte ich gerne das ergebnis in ein Array übergeben anstatt es mit cout in die Console zu schreiben.
    Das ganze findet ja in folgender Zeile statt:

    copy(f, fn, std::ostream_iterator<char>(std::cout, " "));
    

    Ich bin jedoch mit den verwendeten Befehlen nicht vertraut, von daher wäre es schön wenn mir jemand hierbei behilflich sein könnte



  • Es ist immer besser, wenn du noch konkret beschreibst was du vor hast.

    Folgendes schreibt es in einen std::vector und gibt diesen std::vector danach aus:

    do
        {
    		std::vector<char> v(f, fn);
    
            std::cout << ++i << ". Permutation: ";
    
    		std::copy(v.begin(), v.end(), std::ostream_iterator<char>(std::cout, " "));
    
            std::cout << std::endl;
        }
        while(std::next_permutation(f, fn));
    

Log in to reply