Voll einfach?

[zeku]

Hallo,

ich habe da ein Problem, bei dem ich nicht weiterkomme, aber vielleicht kann mir ja jemand von Euch weiterhelfen.

Ich brauche einen Algorithmus, der die Zahlen 1 bis 15 in einem Array mit 15 Feldern so verteilt, daß jede Zahl genau einmal vorkommt. Das ist ja noch nicht das Problem. Der Algorithmus soll aber jede mögliche (un)Sortierung der Zahlen durchspielen.

Ich habe versucht, das in C mit einer rekursiven Funktion zu lösen, was mir aber nur einen schwirrenden Kopf bereitet hat. Wahrscheinlich habe ich nur ein Brett vorm Kopf und es ist gar nicht so schwer, aber ich komm einfach nicht weiter.

Weiß irgendjemand eine Antwort oder gibt es vielleicht schon einen solchen Algorithmus?

Ich komm mir echt blöde vor, weil sich das so einfach anhört.

[Tailgunner]

Hallo!

Ich habe zwar keine konkrete Lösung, aber mir ein paar Gedanken gemacht, bin mir aber nicht sicher, ob das alles seine Richtigkeit hat. Anstatt 15 nehme ich einfach mal die 3, erspart eine Menge Schreibarbeit.

Array a[3]={1,2,3} beinhaltet einfach die zu verwendeten Zahlen.

Array x[3] soll später das Ergebnis beinhalten.

Array y[2] soll mit den schon verwendeten Zahlen gefüllt werden.

Dann werden noch 2 weitere Zwischenspeicherarrays benötigt: b[2] und c[1]

Nun geht's los:

x[0] wird mit einer beliebigen Zahl aus Array a gefüllt. Daraufhin wird Array b mit allen Zahlen aus Array a ohne y[0] gefüllt.

x[1] wird mit einer beliebigen Zahl aus Array b gefüllt. Daraufhin wird Array c mit allen Zahlen aus Array b ohne y[1] gefüllt.

x[2] wird mit der letzten verbleibenden Zahl aus Array c gefüllt.

Wenn dann jeweils in den einzelnen Schritten noch mit einem entsprechenden Zähler gearbeitet wird, sollte man damit alle Möglichkeiten hinbekommen.

Alternativ für die Arrays a, b und c kann man auch ein zweidimensionales Array verwenden.

[edit]

y braucht kein Array sein, es braucht nur die zuletzt genutzte Zahl gespeichert werden.

[/edit]

[Nalimov]

Original geschrieben von zeku

Der Algorithmus soll aber jede mögliche (un)Sortierung der Zahlen durchspielen.

Hm, wie soll man das verstehen? Wie sollen die Zahlen eingegeben werden? Sollen erst die Zahlen in ein Array eingegeben und dann sortiert werden? Oder wie darf ich die Aufgabe jetzt genau verstehen. (Hab da im Moment ein Brett vorm Kopf...)

[Tailgunner]

Original geschrieben von Nalimov

Hm, wie soll man das verstehen? Wie sollen die Zahlen eingegeben werden? Sollen erst die Zahlen in ein Array eingegeben und dann sortiert werden? Oder wie darf ich die Aufgabe jetzt genau verstehen. (Hab da im Moment ein Brett vorm Kopf...)

Es sollen einfach alle möglichen Sortierungen der Zahlen vorkommen. Das sind dann Fakultät von 15 (=1307674368000) verschiedene Möglichkeiten. Spielen wir das mal mit den Zahlen 1, 2 und 3 durch, das sind dann Fakultät von 3, also 6 Möglichkeiten:

1.: 1,2,3

2.: 1,3,2

3.: 2,1,3

4.: 2,3,1

5.: 3,1,2

6.: 3,2,1

[Aquano]

Habe mir darüber nur 2 Minuten Gedanken gemacht. Keine Ahnung ob Du so wirklich alle Möglichkeiten bekommst. Ist ein Denkanstoß!

zahlen so sortieren auf 15 zahlen bitte selber erweitern, gebraucht werden ein Array, zwei Indexzähler und ein int feld:

<-

6 5 4 3 2 1

6 5 4 3 1 2

6 5 4 1 3 2

6 5 1 4 3 2

6 1 5 4 3 2

1 6 5 4 3 2

<-

1 6 5 4 2 3

=>

1 2 3 4 5 6

dann

[0] mit [5] tauschen

=>

<-

6 2 3 4 5 1

6 2 3 4 1 5

=>

1 5 4 3 2 6

dann [0] mit [4] tauschen

<-

2 5 4 3 1 6

2 5 4 3 6 1

=>

6 1 3 4 5 2

usw.

dann [1] mit [5] tauschen

[1] mit [4] tauschen usw.

auf Gleichheit der Werte achten, Grenze ist die Größe des Arrays!

Aber warum willst du so was denn machen?

[nic_power]

Hallo,

ist ein Standard-C Algorithmus:

/* generating permutations lexicographic order */

/* Algorithm due to Dijkstra.

   C Implementation by Glenn C. Rhoads */

#include <stdio.h>

#include <stdlib.h>

void main(void)

{

    int i, j, r, s, temp, n;

    int *pi;

    printf( "Enter n: ");

    scanf( "%d", &n);

    pi = malloc( (n+1) * sizeof(int));

    for (i=0; i <= n; i++) pi[i] = i;

    i = 1;

    while (i)

        {

        for (i=1; i <= n; i++) printf( " %2d", pi[i]);

        printf("\n");

        i = n-1;

        while (pi[i] > pi[i+1]) i--;

        j = n;

        while (pi[i] > pi[j]) j--;

        temp = pi[i];

        pi[i] = pi[j];

        pi[j] = temp;

        r = n;

        s = i+1;

        while (r > s)

            {

            temp = pi[r];

            pi[r] = pi[s];

            pi[s] = temp;

            r--; s++;

            }

        }

}

Nic

[cLara]

Original geschrieben von Aquano

Habe mir darüber nur 2 Minuten Gedanken gemacht. Keine Ahnung ob Du so wirklich alle Möglichkeiten bekommst. Ist ein Denkanstoß!

..., gebraucht werden ein Array, zwei Indexzähler und ein int feld:

6 5 4 3 2 1

...

dann

[0] mit [5] tauschen

dann [0] mit [4] tauschen

usw.

dann [1] mit [5] tauschen

[1] mit [4] tauschen usw.

Hi,

wenn ich dich richtig verstehe,

- deckst du damit nur einen Bruchteil der Moeglichkeiten ab! Schau dir mal allein schon oben das Beispiel mit den drei Zahlen an... Also koennen schon bei deinen sechs Zahlen im Vergleich zum Ausgangsarray nicht nur zwei, sondern auch drei ... sechs Zahlen vertauscht werden. Daher kam der Gedanke an ein rekursives Tauschen.

- Andererseits / noch ein Hinweis: Bei deinen beiden Zaehlern passe auf, dass nicht dieselbe Moeglichkeit mehrfach heraus kommt, also in obigem Beispiel: Du hast [0] mit [5] getauscht, [0] mit [4] ... [0] mit [1], dann [1] mit [5] ... [1] mit [2] und natuerlich nicht [1] mit [0]

cLara

[Aquano]

Original geschrieben von Aquano

Habe mir darüber nur 2 Minuten Gedanken gemacht. Keine Ahnung ob Du so wirklich alle Möglichkeiten bekommst. Ist ein Denkanstoß!

auf Gleichheit der Werte achten, Grenze ist die Größe des Arrays!

nT