Sortier-(Probier) funktion für Buchstaben

Mr.Blond

Hallo,

eines Vorweg...die Suchfunktion geht im Augenblick nicht. (Deshalb konnte ich nicht suchen)
Hier meine Frage:

Wie bekomme ich es hin, das wenn ich ein beliebig langes (vermischtes) Wort eingebe der Computer mir ALLE möglichen Konstellationen, die sich aus den Buchstaben ergeben lassen anzeigt?

Vielleicht hat ja jemand nen Link zu dem passenden Thema? Gab es doch bestimmt schonmal.

Danke schon mal für alle Tipps und Hilfen!

otze

ich glaub, du sprichst von permutationen?
http://www.sgi.com/tech/stl/next_permutation.html
http://www.sgi.com/tech/stl/prev_permutation.html

Mr.Blond

Bezieht sich dieser Code den nicht nur auf Zahlen?

Wenn nicht, wie binde ich den in mein Programm ein?

Hier der zu verwendende Code:

template <class BidirectionalIterator> 
void snail_sort(BidirectionalIterator first, BidirectionalIterator last)
{
  while (next_permutation(first, last)) {}
}

int main()
{
  int A[] = {8, 3, 6, 1, 2, 5, 7, 4};
  const int N = sizeof(A) / sizeof(int);

  snail_sort(A, A+N);
  copy(A, A+N, ostream_iterator<int>(cout, "\n"));
}

Falls mir jemand dabei helfen kann oder eine bessere Idee hat ...würde mich sehr freuen.

Vielleicht nochmal zum Verständniss: Nehmen wir an ich habe diese 3 Buchstaben: SUA
Dann will ich alle möglichen Kombinationsmöglichkeiten sehen:
SUA
SAU
USA
UAS
ASU
AUS

Und das natürlich für beliebig lange Reihen (Bis 12 Buchstebn sollten erstmal reichen)

MFG

Mr.Blond

Ich glaube ich hab noch einen Lösungsansatz. Weiss nur nicht so genau wie ich das realisieren soll.

Nehmen wir an ich gebe 6 Buchstaben ein. Dann könnte ich die einzelnen Buchstaben doch bestimmt in Zahlen mit ihrem AsciWert umwandeln. Könnte ich dann nicht mit diesen Zahlen über eine RandomFunktion alle möglichkeiten durchlaufen lassen, diese vor der Ausgabe wieder in Buchstaben umwandeln und überprüfen ob dieser Wert schon per Zufall erstellt wurde?

Caipi

Mr.Blond schrieb:

Ich glaube ich hab noch einen Lösungsansatz. Weiss nur nicht so genau wie ich das realisieren soll.

Nehmen wir an ich gebe 6 Buchstaben ein. Dann könnte ich die einzelnen Buchstaben doch bestimmt in Zahlen mit ihrem AsciWert umwandeln. Könnte ich dann nicht mit diesen Zahlen über eine RandomFunktion alle möglichkeiten durchlaufen lassen, diese vor der Ausgabe wieder in Buchstaben umwandeln und überprüfen ob dieser Wert schon per Zufall erstellt wurde?

Das versteh ich nicht so ganz. Wenn du per Zufall versuchst die Werte zu "berechnen", verschwendest du doch nur Rechenpower. (Kann natürlich auch sein, dass ich dich falsch verstanden habe).

Hier vielleicht ein Lösungsansatz. (Kann durchaus Fehler erhalten, da ich ihn mir gerade am Beispiel Sua ausgedacht habe).
Also:

SUA  | S mit U vertauschen
 |
USA  | S mit A    "
 |
UAS  | U mit A    "
 |
AUS  | U mit S    "
 |
ASU  | A mit S    "
 |
SAU  | Fertig. Da jetzt wieder SUA ensteht.

Das sollte sich doch jetzt relativ einfach programmieren lassen. (Sofern der Algorithmus stimmt)

Caipi

Mr.Blond

bei 3 bUchstaben ist das kein Problem. Das Programm sollte aber mit bis zu 12 Buchstaben arbeiten. Da mus es doch irgendwas geben.

Caipi

Habe gerade anhand dieses Algorithmus ein Test-Programm geschrieben. Bei USA bekomme ich 6 verschiedene Kombinationen. Bei HELLOWORLD 82. (Wie gesagt, keine Garantie auf Korrektheit des Algos).
Hier die Kombinationen die ich bekomme wenn ich den Algo mit HELLO laufen lasse: (18 Kombinationen).

hello
ehllo
elhlo
ellho
elloh
leloh
lleoh
lloeh
llohe
lolhe
lohle
lohel
olhel
ohlel
ohell
hoell
heoll
helol

Caipi

evilissimo

So könnte man das mit *_permutate machen

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
using namespace std;
std::string sort( std::string const & str )
{
   std::string ret(str);
   while(prev_permutation(ret.rbegin(),ret.rend()));
   return ret;
}
std::vector<string> permutate(string::iterator first, string::iterator last)
{
  std::string str(first,last);
  vector<string> ret;
  str = sort(str);
  ret.push_back(str);

  while (next_permutation(str.begin(),str.end()))
    ret.push_back(string(str.begin(),str.end()));

  return ret;
}

int main()
{
  std::string a("SUAUZJHDJKLH");
  vector<string> tmp = permutate(a.begin(), a.end());
  copy(tmp.begin(), tmp.end(), ostream_iterator<string>(cout, "\n"));
}

Ich rate aber niemandem das mit nem längeren string zu testen. Mir ist grade das system eingefroren :p

otze

is ja auch kein wunder, dein permutate müsste O(2*N!) sein...

Mr.Blond

eViLiSSiMo schrieb:

So könnte man das mit *_permutate machen

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
using namespace std;
std::string sort( std::string const & str )
{
   std::string ret(str);
   while(prev_permutation(ret.rbegin(),ret.rend()));
   return ret;
}
std::vector<string> permutate(string::iterator first, string::iterator last)
{
  std::string str(first,last);
  vector<string> ret;
  str = sort(str);
  ret.push_back(str);
  
  while (next_permutation(str.begin(),str.end()))
    ret.push_back(string(str.begin(),str.end()));
  
  return ret;
}

int main()
{
  std::string a("SUAUZJHDJKLH");
  vector<string> tmp = permutate(a.begin(), a.end());
  copy(tmp.begin(), tmp.end(), ostream_iterator<string>(cout, "\n"));
}

Ich rate aber niemandem das mit nem längeren string zu testen. Mir ist grade das system eingefroren :p

Dein Pogramm funzt wunderbar. Wenn du mir jetzt noch sagen könntest wie ich eine Abfrage für die Eingabe der Buchstaben mit einbau?
Für mich ist das so kein Problem ..nur fuer andere User. Ich habs mit char probiert....da meckert er aber rum.

Habe mal Wirtschaft eingegeben jetzt rödelt mein computer schon seid 10 Minuten und ist immer noch nicht viel weiter.

Wo soweit schon mal alles klappt habe ich direkt noch eine Frage. Gibt es eine art elektronisches Lexika, mit dem ich die ermittelten Lösungen auf richtigkeit überprüfen kann?