Permutationen

Wir benutzen dafür die STL-Funktion stable_sort(). Im Durchschnitt ist die auf Qicksort basierende sort()-Funktion zwar etwas schneller, kann aber unter Umständen das Laufzeitverhalten des Programms negativ beeinflussen.

sort ist im Durchschnitt schneller, wie kann es dann das Laufzeitverhalten negativer beeinflussen als stable_sort?

Jester

sort verwendet intern ein modifiziertes Quicksort. Das kann im Extremfall zu quadratischer Laufzeit führen (auch wenn sich einige Implementierungen versuchen dagegen zu schützen). stable_sort verwendet was anderes, vermutlich ein merge_sort oder ähnliches, was sich leicht stabil implementieren lässt. merge_sort hat immer nur eine Laufzeit von n*log(n). Vermutlich soll das die Begründung sein.

Ich muß aber zugeben, dass mich das auch nicht wirklich überzeugt. Ich würde einfach std::sort verwenden. In allen praktischen Fällen dürfte man damit schneller sein.

Ben04

Die Permutationen einer ungrordneten Sequenz lassen sich auch ganz leicht mit std::next_permutation ohne sort realisieren:

vector<string> SSTL_Permutation(const char *input)
{
    vector<string> result;
    string str = input, start = str;

    do{
        result.push_back(str);
        next_permutation(str.begin(), str.end());
    }while(str != start);

    return result;
}

Aber da es n! Permutationen gibt ist die Laufzeit mindestens O(n!) da fällt das O(n*log(n)) gar nicht mehr ins Gewicht und daher wird hier am falschen Ende optimiert.

result.insert(result.end(), cs);

Wieso nicht einfach push_back?

Im Default-Modus ist das Flag true und die Template-Funktion _next_permutation verhält sich wie die Standard-Implementierung aus der STL. Wird allerdings explizit false übergeben, generiert die Funktion auch für unsortierte input strings alle Permutationen.

das tut next_permutation doch auch.

C++98 25.3.9 schrieb:

Takes a sequence defined by the range [first, last) and transforms it into the next permutation.
The next permutation is found by assuming that the set of all permutations is lexicographically sorted with respect to operator< or comp. If such a permutation exists, it returns true. Otherwise, it transforms the sequence into the smallest permutation, that is, the ascendingly sorted one, and returns false.

Beim multinomial Coeffizient wäre es nicht schlecht ausdrücklich anzugeben, dass es sich um verschiedene ks handelt und dies durch k_1, k_2, ... k_n deutlich zu machen.

Eine Text Beschreibung wie man next_permutation und Phillip P. Fuchs' Algorithmus implementieren kann wäre interessant gewesen.

Hallo habe folgendes Problem: Ich have ein array mit n Elementen somit habe ich 2^n-1 ergebnisse die in einem bsp so ausshene:

string array={"a","b","c"}

ausgabe:(sollte so sein)
a
b
c
ab
ac
bc
abc

2^n-1=23-1=7 OK

Jedoch wie berechne ich das

Neues bsp:

string array={"a","b","c","2"}

ausgabe:(sollte so sein)
a
b
c
2
ab
ac
a2
bc
b2
.
.
.
abc2

2^n-1=22-1=15 OK

Bitte um Code oder Hilfe!!!

Am besten iterativ lösen!!

Mfg Peter

#include <stdio.h>

void inc (int *a, int max)
{
   (*a)++;
   if (*a == max)
   {
      *a=0;
      inc (a+1, max);
   }
}

void show (int *a, char *str)
{
   if (*a != -1)
   {	
      show (a+1, str);
      putchar (str[*a]);
   }
}

void main (void)
{
   char *str = "abc";
   int out[256];
   memset (out, 0xff, sizeof(out));
   for (;;)
   {
      inc (out, sizeof(str)-1);
      show (out, str);
      printf ("\n");
   }
}

spacerat

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

knivil

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

GPC

Ich schau mal was ich tun kann...

GPC

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.

SeppJ

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?

MichelRT

SeppJ schrieb:

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

Wahrscheinlich fährt er Toyota

xeroe

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));