# C - Permutation mit 10 Zahlen



## sheester (12. Mai 2008)

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


----------



## devDevil (13. Mai 2008)

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

```
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 ...

```
std::putchar(i + '0');
```
 ...


----------



## Thomas Darimont (17. Mai 2008)

Hallo,

schau mal hier:

```
/* 
 * 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:

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

Gruß Tom


----------



## devDevil (17. Mai 2008)

Rekursiv ist eigtl. langsamer als Iterativ.


----------



## Thomas Darimont (17. Mai 2008)

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


----------



## RedWing (17. Mai 2008)

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


----------



## devDevil (17. Mai 2008)

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

@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.


----------



## RedWing (17. Mai 2008)

Hallo,


devDevil hat gesagt.:


> @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 

Gruß,
RedWing


----------



## devDevil (19. Mai 2008)

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


----------



## gulaschsuppe (27. Dezember 2009)

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


----------



## Matthias Reitinger (27. Dezember 2009)

gulaschsuppe hat gesagt.:


> und auf welchem rechner soll das laufen?


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




gulaschsuppe hat gesagt.:


> gibt es online server, die das ergebnis als txt. datei ausgeben? das würde mich dehr interessieren
> also
> 0000000000000
> 0000000000001
> ...


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

Grüße,
Matthias


----------

