Permutationen von array

[grec]

Hallo,

ich brauche alle möglichen Permutationen aus einem array!
Der array enhält eine nicht vordefinierte Anzahl von ungeordneten int-Zahlenwerten! Beispiel: "93718" oder "462"!

Hier ein Beitrag mit char-Werten für PHP: http://www.tutorials.de/tutorials158553.html

Hat jemand einen Algorithmus speziell für meinen Fall?

WICHTIG: Ich muss danach einzelne Permutationen mittels if-Anweisung ansprechen können!

Danke im Voraus!

Gruß
grec

 

[Kachelator]

Hast du ein Glück! Der Algorithmus ist schon in der C++-Standard-Library drin und heisst next_permutation() (im <algorithm>-Header). Das liefert dir immer die nächste Permutation einer Sequenz von Werten, sofern vorhanden. Dazu solltest du eventuell einmal sortieren ( sort() drüberlaufen lassen), damit die ersten Permutationen nicht ausgelassen werden. Hier Dokumentation.

Wenn du nicht damit klar kommst, frag nochmal nach. Die MSDN enthält allerdings auch ein Beispielprogramm.

 

[grec]

Laut der Dokumentation muss der Inhalt des array's aber vordefiniert werden, oder sehe ich das falsch?

Ausschnitt aus der Dokumentation:

Pattern[0] = "A" ;
Pattern[1] = "B" ;
Pattern[2] = "C" ;

Diese Definition ist in meinem Fall nicht möglich! Die Werte in meinem Programm werden in einem vorherigen Schritt in dem array indirekt eingegeben und gespeichert! Es können also alle Zahlenkombinationen und eine unbestimmte Menge von Zahlen vorkommen, die nicht im Programm selbst definiert werden können!

(eine MSDN hab ich leider nicht)

Gruß
grec

 

[Kachelator]

Laut der Dokumentation muss der Inhalt des array's aber vordefiniert werden, oder sehe ich das falsch?

Ausschnitt aus der Dokumentation:

Pattern[0] = "A" ;
Pattern[1] = "B" ;
Pattern[2] = "C" ;

Diese Definition ist in meinem Fall nicht möglich! Die Werte in meinem Programm werden in einem vorherigen Schritt in dem array indirekt eingegeben und gespeichert! Es können also alle Zahlenkombinationen und eine unbestimmte Menge von Zahlen vorkommen, die nicht im Programm selbst definiert werden können!

Ich verstehe das Problem nicht. Du hast ein Array, das mit Werten gefüllt ist, oder? Wie sie da reingekommen sind, ist doch vollkommen egal. next_permutation() permutiert dieses Array, sofern es geht. Die einzigen Bedingungen sind, dass die Werte per "<" vergleichbar sind und dass das Array vor Beginn der Permutationen günstigerweise sortiert wird, um keine Permutationen auszulassen.

(eine MSDN hab ich leider nicht)

Die MSDN gibt es auch online, nicht wahr? Der Link in meinem letzten Post führt dich direkt dort hin. Und wie ich an deinem Codeschnipsel sehe, hast du auch das Beispielprogramm gefunden.

Wenn du etwas Code postest, kann ich dir vielleicht zeigen, wie du es einsetzen kannst.

 

[grec]

Ok, hier ist der Teil, auf den es ankommt!

#include <iostream>
#include <string>

using namespace std;

int main()
{
        int p=0;
        string person;

        do
        {
                p++;
                cout<<"Person "<<p<<": ";
                cin>>person[p];
        }
        while(person[p]!="x");

        for(int b=1;b<p;b++)
        {
                if(person[b]=="a")z[b]=1;
                if(person[b]=="b")z[b]=2;
                if(person[b]=="c")z[b]=3;
                //
                //
                //
                if(person[b]=="n")z[b]=14;
				
                cout<<z[b];
        }
        return 0;
}

Von z[b] brauche ich jetzt alle Permutationen!

Das Programm dient zur Berechnung einer Sitzordnung! Dabei werden zu Beginn Namen eingegeben(im obigen Ausschnitt durch "a", "b", "c", etc. ersetzt)! Diese Namen werden in Zahlen umgewandelt! Am Ende müssen bestimmte Bedingungen erfüllt werden, wie z.B.: Die 2 darf nicht neben der 3 sitzen! Zu diesem Zweck brauche ich alle Permutationen, die dann mittels if-Anweisung angsprochen werden müssen.

Ich würde mich über einen Algorithmus-Vorschlag sehr freuen!

Gruß
grec

 

[grec]

string person; muss natürlich string person[20]; heißen!

Kachelator, du wirst jetzt gebraucht....

 

[Kachelator]

Oh, gut dass du mich nochmal erinnert hast. Also, unten kommmt ein Permutationsbeispiel.

Ich lasse mal aus, dass du die Buchstaben in Zahlen umwandelst und beziehe mich hier auf die Permutationen im String. Die Vorgehensweise ist aber für andere Sequenzarten die selbe.

Eingabe und Ausgabe habe ich anders gelöst.

#include <iostream>
#include <string>
#include <algorithm>

int main(int argc, char* argv[])
{
  using namespace std;

  string eingabe;
  cout << "Bitte eine Zeichenkette eingeben: ";
  cin >> eingabe;
  cout << endl;

  cout << "Eingabe: " << eingabe << endl;

  // sortieren, damit nicht die ersten Permutationen ausgelassen werden,
  // falls Eingabe nicht sortiert (lass es testweise mal weg)
  std::sort( eingabe.begin(), eingabe.end() );
  cout << "sortiert (Permutation 0): " << eingabe << endl;

  int permutation = 0;
  while ( std::next_permutation( eingabe.begin(), eingabe.end() ) )
  {
    // hier werden alle Permutationen nacheinander ausgegeben
    cout << "Permutation " << ++permutation << ": " << eingabe << endl; 
  }
  cout << permutation << " Permutationen gefunden" << endl;

  char eingabedummy = '\0';
  cin >> eingabedummy;

  return 0;
}

Ich hoffe, das hilft dir weiter.

 

[grec]

Problem:

Die Funktionen std::sort( eingabe.begin(), eingabe.end() ); und std::next_permutation( eingabe.begin(), eingabe.end() ) scheinen nur zu funktionieren, wenn eingabe ein string oder ein char ist!
Mein array z[b] ist aber ein integer und das sollte aus programmtechnischen Gründen auch so bleiben! Gibt es eine Möglichkeit, dass die Funktionen mit einem integer funktionieren oder kann ich den integer irgendwie in einen string umwandeln?

Gruß
grec

 

[Kachelator]

Mein array z[ b ] ist aber ein integer

Dein Array kann kein Integer sein, sondern höchstens ein Integer-Array. Jedenfalls gut, dass das jetzt geklärt ist.

Übergib einfach die Startadresse und die Endadresse+1 der Einträge, die für dich relevant sind:

std::sort( z, z + 10 ); // die ersten 10 werden berücksichtigt beim Sortieren
...
while ( std::next_permutation(  z, z + 10 ) ) // die ersten 10 werden berücksichtigt beim Permutieren
  {
...

 

[grec]

Hallo nochmal,

@Kachelator: Ich hoffe ich gehe dir hier nicht auf die Nerven....wenn du nicht mehr willst dann, muss du ab jetzt nicht mehr antworten!
Dein Programm ist genial(habs in einem seperaten Projekt getestet)! Ich habe allerdings noch immer Probleme mit dem array, meine for-Schleife ist auch nicht unbedingt hilfreich!
Hier nochmal der komplette relevante Code:

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main()
{
        int p=0;
        string person[20];

        do
        {
                p++;
                cout<<"Person "<<p<<": ";
                cin>>person[p];
        }
        while(person[p]!="x");

        for(int b=1;b<p;b++)
        {
                int z[20]={0};

                if(person[b]=="a")z[b]=1;
                if(person[b]=="b")z[b]=2;
                if(person[b]=="c")z[b]=3;
                //
                //
                //
                if(person[b]=="n")z[b]=14;
				
                cout<<z[b];
        }
        return 0;
}

Laut deinem Vorschlag füge ich folgende Zeilen hinzu:

std::sort( z, z+(p-1));
cout << "sortiert (Permutation 0): " << z << endl;

// und

int permutation = 0;
while ( std::next_permutation( z, z+(p-1)) )
{
        cout << "Permutation " << ++permutation << ": " << z << endl; 
}
cout << permutation << " Permutationen gefunden" << endl;

Wenn ich das aber in die for-Schleife platziere, dann kommt nur "Datenmüll" raus! Da die Schleife mehrere Durchläufe hat, ist der Datenmüll gleich doppelt, dreifach, vierfach, etc.! Die Funktionen dürfen also dementsprechend nicht in die Schleife gesetzt werden!
Wenn ich sie aber außerhalb platziere, dann wird nur mit dem letzten Wert des array's gerechnet, z.B. "4" anstatt "924" was ja irgendwie auch logisch ist! Aber wie ist das Problem zu lösen?
Der obige Quelltext ist komplett und fehlerfrei, du könntest ihn also mal in einem Projekt testen! Aber wie gesagt, du musst nicht! Du wirst auch wichtigere Sachen zu tun haben! Ich bin dir jetzt schon sehr dankbar!

Gruß
grec