Permutationen

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