Hallo Leute,

ich muss ein Programm erstellen, für welches ich alle Möglichen kombinationen der Zahlen 0-9 benötige.
Keine Zahl soll doppelt Vorkommen.
Die Funktion Permutation soll einmal aufgerufen werden können und dann verändertaust sie genau 2 Zahlen in meinem String. Um also alle Kombinationen von 0-9 zu erhalten, muss Permutation 3628800mal aufgerufen werden.

Ich hab mich schon über Permutation bei Google schlau gemacht, jedoch komme ich da der Lösung meines Problems nicht näher.

Ich hoffe ihr könnt mir helfen, steh momentan echt auf dem Schlauch.

Grüsse

Ehm das ist natürlich krank Aber am einfachsten geht es durch:

Code cpp:

1 2 3 4 5 6 7 8 9 10 11 12 13

unsigned char[3628800][10];   for (unsigned int i(0); i < 10; ++i)     for (unsigned int j(0); j < 10; ++j)         for (unsigned int k(0); k < 10; ++k)             for (unsigned int l(0); l < 10; ++l)                 for (unsigned int m(0); m < 10; ++m)                     for (unsigned int n(0); n < 10; ++n)                         for (unsigned int o(0); o < 10; ++o)                             for (unsigned int p(0); p < 10; ++p)                                 for (unsigned int q(0); q < 10; ++q)                                     for (unsigned int r(0); r < 10; ++r)                                         std::cout << i << j << k  << l << m << n << o << p << q << r << "\n";

aber das std::cout ist sehr langsam ... vllt hier auf C zurück greifen ... oder sogar auf putchar und selbst + '0' zu i usw. addieren um das richtige Zeichen zu bekommen ...

Code cpp:

1	std::putchar(i + '0');

...

Hallo,

schau mal hier:

Code c:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

/*  * File:   Main.c  * Author: Tom  *  */   #include <stdio.h> #include <stdlib.h>   void swap(char *c, int firstIndex, int secondIndex); void permut(char *c, int endIndex);   int main(int argc, char** argv) {     char c[20];     printf("Chars: ");     scanf("%s",&c);     fflush(stdin);     permut(c,strlen(c)-1);     return (EXIT_SUCCESS); }   void swap(char *c, int firstIndex, int secondIndex){     char tmp = c[firstIndex];     c[firstIndex] = c[secondIndex];     c[secondIndex] = tmp; }   void permut(char *c, int endIndex){     if(endIndex == 0){        printf("%s\n",c);     }else{        permut(c,endIndex-1);        int i;        for(i = 0; i<endIndex;i++){            swap(c,i,endIndex);            permut(c,endIndex-1);            swap(c,i,endIndex);        }     } }

Ausgabe:

Code :

1 2 3 4 5 6 7 8

Chars: ABC ABC BAC CBA BCA ACB CAB [Press Enter to close window]

Gruß Tom

Rekursiv ist eigtl. langsamer als Iterativ.

Hallo,

1) Ich habe nur einen anderen Algorithmus vorgestellt der etwas flexibler ist, als das was du da vorgeschlagen hast.
2) Rekursion ist nicht immer langsamer als Iteration! Jeder Funktionsaufruf kostet Zeit und Speicher das ist klar, jedoch besiegt eine clervere rekursive Implementierung oftmals eine umständliche iterative.
Weiterhin lässt sich der Nachteil des erhöhten Speicherplatzbedarfs mit Techniken wie Endrekursion / tailcalls: http://de.wikipedia.org/wiki/Endrekursion relativ einfach aus der Welt schaffen , sofern die Sprache / der Compiler sowas unterstützt.

Gruß Tom

Hallo,

@devDevil

mal abgesehen davon, ist dein Algorithmus auch noch falsch ...
1.) Hast du lauter Endlosschleifen drin
2.) Ist eine Permutation nur auf Mengen definiert, d.h. die Elemente müssen alle verschieden sein. => die Permutationsmenge einer Menge mit n Elementen besitzt n! Elemente. Deine "Menge" hat aber lauter Duplikate und besitzt folglich n^n Elemente, wenn du denn diese Endlosschleifen beseitigen würdest.

Gruß,
RedWing

Ich sag ja nix dagegen das du einen anderen Lösungsvorschlag anbringst Hab die jetzt auch keinem Performancetest unterzogen :-P

@RedWing:
(1) Jop. Passiert wenn man es nur so reintippt.
(2) Wer hat von Permutation gesprochen? Er wollte nur alle möglichen Kombinationen ohne das 121 z.B. doppelt vorkommt. Das ist so der Fall.

Hallo,

Zitat von devDevil

@RedWing:
(2) Wer hat von Permutation gesprochen? Er wollte nur alle möglichen Kombinationen ohne das 121 z.B. doppelt vorkommt. Das ist so der Fall.

naja, seine Aufgabenstellung impliziert das ja (bzw erschlägt einen der Zaunpfeiler fast ):

Die Funktion Permutation soll einmal aufgerufen werden können und dann verändertaust sie genau 2 Zahlen in meinem String. Um also alle Kombinationen von 0-9 zu erhalten, muss Permutation 3628800mal aufgerufen werden.

M = {0,...,9} => |M| = 10 => |P(M)| = 10! = 3628800

(1) Jop. Passiert wenn man es nur so reintippt.

Es sei dir verziehen :P

Gruß,
RedWing

Aua Jetzt is et mir aber peinlich Hab die Aufgabe scheinbar nicht zu ende gelesen denn den Teil mit Permutation hatte ich vorher noch nicht gelesen Sorry ... habt ja recht

und auf welchem rechner soll das laufen?
gibt es online server, die das ergebnis als txt. datei ausgeben? das würde mich dehr interessieren
also
0000000000000
0000000000001
0000000000002
in txt. datei
vielen dank im vorraus

Zitat von gulaschsuppe

und auf welchem rechner soll das laufen?

Auf einem Recher, für den es einen C-Compiler gibt.

Zitat von gulaschsuppe

gibt es online server, die das ergebnis als txt. datei ausgeben? das würde mich dehr interessieren
also
0000000000000
0000000000001
0000000000002
in txt. datei
vielen dank im vorraus

Ist nicht auszuschließen. Allerdings beschreibst du mit deiner Reihe keine Permutationen. Wofür brauchst du eine solche Datei?

Grüße,
Matthias