C - Permutation mit 10 Zahlen

[sheester]

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]

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]

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]

Rekursiv ist eigtl. langsamer als Iterativ.

 

[Thomas Darimont]

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]

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]

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]

Hallo,

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

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]

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