# Permutationen von array



## grec (28. Mai 2004)

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 (28. Mai 2004)

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 (28. Mai 2004)

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 (29. Mai 2004)

> Laut der Dokumentation muss der Inhalt des array's aber vordefiniert werden, oder sehe ich das falsch?
> 
> Ausschnitt aus der Dokumentation:
> 
> ...



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 (29. Mai 2004)

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 (31. Mai 2004)

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

Kachelator, du wirst jetzt gebraucht....


----------



## Kachelator (1. Juni 2004)

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 (1. Juni 2004)

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 (1. Juni 2004)

> 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 (1. Juni 2004)

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


----------



## Thomas Darimont (1. Juni 2004)

Hallo!

Schau mal hier:

http://www.tutorials.de/forum/showthread.php?threadid=75639&highlight=permutation

da hatten wir ein ähnliches Problem.

Gruß Tom


----------



## Kachelator (1. Juni 2004)

> ....wenn du nicht mehr willst dann, muss du ab jetzt nicht mehr antworten!


  Hey, danke!



> Dein Programm ist genial(habs in einem seperaten Projekt getestet)!


  Hey, danke!



> Ich habe allerdings noch immer Probleme mit dem array, meine for-Schleife ist auch nicht unbedingt hilfreich!


  Hey, d... 

Dein Problem ist wahrscheinlich einfach ein verrutschter Index. Schau mal deine do-Schleife an:

```
int p=0;
       //...
        do
        {
                p++;
                cout<<"Person "<<p<<": ";
                cin>>person[p];
        }
        while(person[p]!="x");
```
Der erste Eintrag von person, der zugewiesen wird, ist person[1], und nicht  person[0], was der erste Eintrag des Arrays ist. Dasselbe gilt später auch für z. Du greifst dann jedoch durch z.B. 
	
	
	



```
std::sort( z, z+(p-1));
```
  auf z[0], zu, was aber nicht initialisiert ist. (z ist der Zeiger auf z[0]) Es würde vermutlich funktionieren mit 
	
	
	



```
std::sort( z+1, z+p+1);
```

Überprüf mal die von dir verwendeten Indizes. Bei C und C++ beginnen Arrays mit dem Index 0, nicht 1!

Die sort- und next_permutation-Algorithmen erwarten (wie eigentlich alle Algorithmen, die mit Sequenzen arbeiten) als Parameter zur Kennzeichnung der Sequenz einen Beginn-Iterator und einen End-Iterator. In deinem Fall ist das der Zeiger auf das erste Element bzw. der Zeiger *hinter* das letzte Element. std::string liefert diese "Zeiger" mit begin() und end(). Bei Arrays der Länge n ist es normalerweise a und a+n.


----------



## grec (2. Juni 2004)

> Dein Problem ist wahrscheinlich einfach ein verrutschter Index.


Leider nicht, damit hatte ich zuvor auch ein wenig herum experimentiert, ohne Erfolg! Also Ergebnis bekomme ich immernoch "Datenmüll", und zwar mehrfach!

Gruß
grec


----------



## grec (2. Juni 2004)

Ich erhalte folgende Ausgabe bei der sort() -Funktion, wenn ich sie wie beschrieben in die for-Schleife setze! Die Eingabe ist oben erkenntlich!


```
Person 1: b
Person 2: c
Person 3: a
Person 4: x

// Ausgabe: 
2sortiert (Permutation 0): 0012FDDC   // jeweils die Zahl vor 
3sortiert (Permutation 0): 0012FDDC   // "sortiert" ist die Ausgabe 
1sortiert (Permutation 0): 0012FDDC   // von z[b]
```


----------



## grec (2. Juni 2004)

So, kaum zu glauben, aber ich hab jetzt meine Permutationen gebildet! Ich habe meinen integer-array mit Hilfe von einem StringStream in einen string umgewandelt und dann die ursprüngliche Funktionen benutzt!
Also bis jetzt funktioniert alles, falls es nochmal zu Problemen kommt, melde ich mich natürlich wieder  

1000Dank @Kachelator, wenn du nicht gewesen wärst......ich hoffe ich habe dich nicht zu sehr strapaziert.....

Jetzt ist es gleich 3 Uhr morgens! Ich glaube ich werde hier noch zum Informatiker 

Grüße
grec


----------



## grec (2. Juni 2004)

Hmmm, das ging wohl in die falsche Richtung! Ich habe nur an den nächsten Schritt gedacht und den übernächsten außer Acht gelassen! Das ist fast so, als ob ich mir ein Computer-Spiel kaufe, welches es nur in Japan und in den USA gibt, und ich fliege heute nach Japan, obwohl ich morgen sowieso in die USA muss  

Also wie gesagt, ich habe die *Permutationen gebildet, die jetzt aus string's bestehen!* Am Anfang hatte ich aber folgendes angekündigt:


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


Beispiel, wie ich eine Bedingung in Quelltext umwandeln muss:
"Gebe nur Permutationen aus, wenn die "1" und die "3" nicht nebeneinander stehn"! Dafür muss ich wohl wieder mit arrays arbeiten, oder?  
Irgendwelche Vorschläge?

Gruß
grec


----------



## Kachelator (2. Juni 2004)

Was hindert dich daran, die von next_permutation() generierten Permutationen zu überprüfen und je nachdem entweder zu  verwenden oder zu verwerfen?


----------



## grec (2. Juni 2004)

Ja die Frage ist, wie ich die von next_permutation() generierten string-Permutationen überprüfen kann

Falls es sich bei den Permutationen um array's handeln würde, könne ich ja sowas machen:


```
if( z[b] != z[b+1] && z[b] != z[b-1] )
{
    cout<<"Permutation "<<++permutation<<": "<<z<<endl;
}
```

Aber wenn die Permutationen keine array's sind, weiß ich nicht, wie ich den Inhalt der Permutationen überprüfen soll!

Gruß
grec


----------

