Alle Kombinationen finden

[freakbodo]

Hallo habe folgendes Problem, möchte ein Programm in Java schreiben das mir Buchstaben einliest und sämtliche Kombinationsmöglichkeiten der eingelesenen Buchstaben ausgibt! Das einlesen ist schon erledigt, nur finde ich keinen Ansatz für den Kombinationsalgorithmus, weder rekursiv noch iterativ! :confused: :confused:
Wäre für Vorschläge/Ideen oder ähnlichem dankbar. Muss auch nicht als Quellcode sein will ja schließlich auch noch ein wenig Spass selber dran haben! ;D

[freakbodo]

ok habe jetz ein möglichkeit gefunden jedoch taucht ab 8 Zeichen folgender fehler auf:
java.lang.OutOfMemoryError: Java heap space
Was heißt das und was kann ich dagegen tun?

[Sephiroth]

ok habe jetz ein möglichkeit gefunden jedoch taucht ab 8 Zeichen folgender fehler auf:
java.lang.OutOfMemoryError: Java heap space
Was heißt das und was kann ich dagegen tun?
Du hast nicht mehr genug Speicher, um ein neue Objekt zu erstellen.

Bei 8 verschiedenen Zeichen würde man ja auch auf 16777216 mögliche Kombinationen kommen, in sofern nicht allzu verwunderlich.

Was du probieren könntest, wäre z.B. mehr Speicher zur Verfügung zu stellen -> http://java.sun.com/j2se/1.5.0/docs/tooldocs/windows/java.html#nonstandard Xms und Xmx

Wie sieht denn dein Code aus?

[freakbodo]

noch etwas konfus werde morgen oder übermorgen ein wenig Ordnung/Lesbar machen und dann hier reinstellen

[Chris Lux]

[...]
Bei 8 verschiedenen Zeichen würde man ja auch auf 16777216 mögliche Kombinationen kommen, in sofern nicht allzu verwunderlich.

soweit ich weiss sind es weitaus weniger. es sollten genau 8! (sprich 8fakultät) sein, was genau 40320 sind. (8 unterscheidbare kugeln, wieviele möglichkeiten beim ziehen ohne rücklegen).

[Crushinator]

(...) Wäre für Vorschläge/Ideen oder ähnlichem dankbar. Muss auch nicht als Quellcode sein will ja schließlich auch noch ein wenig Spass selber dran haben! ;D
http://www.mainzelahr.de/smile/schilder/guckstduhier.gif und zwar dahin (http://forum.java.sun.com/thread.jspa?threadID=618441&tstart=120). :)

[freakbodo]

Hier der Quellcode hoffe der ist gut lesbar

import java.util.Scanner;

public class neunlive {

boolean wiederholung;
int merk, zeile, laenge, zahl[], max, fak;
Scanner sc;
String input;
char buchstaben[];
byte erg[][];
int enderg[][];
char ausgabe[][];
int zaehler;
public static void main(String[] args) {
new neunlive();
}


public neunlive(){
zeile=0;
zaehler=0;
sc=new Scanner(System.in);

/*
* Eingabe
*/
System.out.println("Buchstabenreihe eingeben: ");
input=sc.next();

/*
* Buchstaben-Arrays erstellen
*/
laenge=input.length();
buchstaben=new char[laenge];
zahl=new int[laenge];
for(int i=0;i<laenge;i++){
buchstaben[i]=input.charAt(i);
zahl[i]=i;
}

max=(int)Math.pow(laenge,laenge);
fak=fakultaet(laenge);

/*
* restliche benötigte Arrays
*/
System.out.println("Bitte warten");
//Array das sämtliche "Kombinationen mit Wiederholung" enthält
erg=new byte[max][laenge];//Hier Fehler
System.out.println("...");
//Array das nur die gesuchten Kombinationen enthält
enderg=new int[fak][laenge];
System.out.println("...");
//Array das die Buchstaben enthält
ausgabe=new char[fak][laenge];
System.out.println("...");


kombinieren();
ausgabe();


}
public void kombinieren(){
/*
* Hier werden alle Kombinationen erschaffen
* [kann nicht erklären warum es funktioniert ;-)]
*
*/

for(int i=0;i<laenge;i++){
for (int j=0;j<(int)Math.pow(laenge,i);j++){
for(int zahlen=0;zahlen<laenge;zahlen++){
for(int k=0;k<(max/((int)Math.pow(laenge,i+1)));k++){
erg[zaehler][i]=(byte)zahlen;
zaehler++;
}
}
}
zaehler=0;
}

/*
* Hier werden die falschen Kombinationen aussortiert
*/
for(int i=0;i<max;i++){
wiederholung=false;
for(int j=0;j<laenge;j++){
merk=erg[i][j];
if(!wiederholung){
for(int k=j+1;k<laenge;k++){
if(merk==erg[i][k]){
wiederholung=true;
}
}
}
}
if(!wiederholung){
for(int j=0;j<laenge;j++){
enderg[zeile][j]=erg[i][j];
}
zeile++;
}
}

/*
* Hier werden die Zahlen durch die entsprechenden
* Buchstaben ersetzt
*/
for(int i=0;i<fak;i++){
for(int j=0;j<laenge;j++){
ausgabe[i][j]=buchstaben[enderg[i][j]];
}
}
}
public void ausgabe(){
System.out.println("Anzahl der möglichen Kombinationen: "+fak);
for(int i=0;i<fak;i++){
for(int j=0;j<laenge;j++){
System.out.print(""+ausgabe[i][j]);
}
System.out.println("");
}


}

public int fakultaet(int f){
int erg=1;
for(int i=0;i<f;i++){
erg=erg*(i+1);
}
return erg;
}
}

Funktionsweise: erschaffe alle Möglichkeiten auch die die das selbe Element enthalten, dann sortiere ich die falschen Elemente (also die die gleiche Elemente mehrfach enthalten) aus

[Pinoccio]

for(int i=0;i<laenge;i++){
for (int j=0;j<(int)Math.pow(laenge,i);j++){
for(int zahlen=0;zahlen<laenge;zahlen++){
for(int k=0;k<(max/((int)Math.pow(laenge,i+1)));k++){
erg[zaehler][i]=(byte)zahlen;
zaehler++;
}
}
}
zaehler=0;
}Ich weiß nicht, ob der Compiler das wegoptimiert, aber ich halte es dessen ungeachtet für schlechten Stil, konstante Ausdrücke so in einer for-Schleife zu verwenden.
for(int i=0;i<max;i++){
wiederholung=false;
for(int j=0;j<laenge;j++){
merk=erg[i][j];
if(!wiederholung){
for(int k=j+1;k<laenge;k++){
if(merk==erg[i][k]){
wiederholung=true;
}
}
}
}
if(!wiederholung){
for(int j=0;j<laenge;j++){
enderg[zeile][j]=erg[i][j];
}
zeile++;
}
}Du setzt wiederholung auf false und machst nix dran und testest dann den Wert von wiederholung, scheint mir etwas unklar warum bzw ob das sinnvoll ist.
public int fakultaet(int f){
int erg=1;
for(int i=0;i<f;i++){
erg=erg*(i+1);
}
return erg;
}
}
Ich würde hier nicht int nehmen, das steigt bei 13! aus, long kommt immerhin bis 20!.

Deinen Code zum Zusammenbauen der mörglichen Kombination ist imho extrem ineffektiv, da die Anzahl der Kombination enorm größer ist als die der möglichen Kombination. Du rechnest also viel Mist aus den du dann verwirfst, das führt, so wie Sephiroth schon bemerkte, zu Problemem mit dem zur Verfügung stehenden Speicher. Den Speicher zu erweitern ist eine Variante ...
Hab ne Idee, werd mal eclipse (http://eclipse.org/) anschmeißen.

mfg Sebastian

[freakbodo]

for(int i=0;i<max;i++){
wiederholung=false;
for(int j=0;j<laenge;j++){
merk=erg[i][j];
if(!wiederholung){
for(int k=j+1;k<laenge;k++){
if(merk==erg[i][k]){
wiederholung=true;
}
}
}
}
if(!wiederholung){
for(int j=0;j<laenge;j++){
enderg[zeile][j]=erg[i][j];
}
zeile++;
}
}

Damit überprüfe ich ob die zu überprüfende Kombination,ein Element enthält das doppelt auftritt, und wenn dies der Fall ist brauch ich ja nicht weiter überpüfen ob es doppeltes Element enthalten ist, das erspart meiner Meinung nach Rechenzeit. Wenn kein doppeltes Element enthalten ist dann ist es eine gesuchte Kombination

[Pinoccio]

So, hier eine rekursive Variante, welche allerdings nicht berücksichtigt, daß Buchstaben mehrmals vorkommen können. Für zB "einsam" liefiert sie alle richtigen Kombinationen, für "alleine" gibt sie zum Beispiel "ainllee", "ainllee", "ainllee" und "ainllee", als verschiedene Kombinationen zurück. Daran knobel ich noch.
public class Kombiner {

// Unsere Datenstruktur, ein Array ginge auch,
// aber beim Vector muss nicht ICH aufpassen, an welcher Stelle wir sind.

static java.util.Vector arr = null;

public static void main(String[] args) {

arr = new java.util.Vector();
String ausgang = "einsam";
kombi(ausgang);
output();

}

public static void kombi(String s) {

// Rekursionsbeginn mit leerem Anfang
kombine("", s);

}

public static void kombine(String anfang, String rest) {

// Ist nur noch ein Buchstabe am Ende da, muss das eine neue Kombination
// sein
if (rest.length() == 1) {
String kombination = anfang + rest;
arr.add(kombination);
} else {
// bei mehreren wähle immer einen und setze ihn mit an den Anfang
for (int i = 0; i < rest.length(); i++) {

String rest_neu = rest.substring(0, 0 + i)
+ rest.substring(i + 1);
String anfang_neu = anfang + rest.substring(i, i + 1);
kombine(anfang_neu, rest_neu);
}
}

}

public static void output() {

System.out.println("" + arr.size() + " Kombinationen gefunden. Liste:");

// der Wert gibt an, bis wohin alle Kombinationen ausgegeben werden.
if (arr.size() > 22) {
for (int i = 0; i < 11; i++) {
System.out.println(arr.elementAt(i));
}
System.out.println("... " + (arr.size() - 20)
+ " Kombination werden nicht angezeigt.");
for (int i = arr.size() - 10; i < arr.size(); i++) {
System.out.println(arr.elementAt(i));
}
} else {
for (int i = 0; i < arr.size(); i++) {
System.out.println(arr.elementAt(i));
}

}
}

}

mfg Sebastian

Disclaimer: Der hier gepostet Quelltext ist zu 100% ohne Vorlage entstanden. Leider kann ich nicht ausschließen, daß er tatsächlich frei von Anprüchen durch Trivial-Patente ist.

[freakbodo]

sieht schon ganz gut aus und vorallem schneller jedoch kommen wir hier auch bei 10 buchstaben sind aber schonmal 3 Zeichen mehr

[Pinoccio]

sieht schon ganz gut aus und vorallem schneller jedoch kommen wir hier auch bei 10 buchstaben sind aber schonmal 3 Zeichen mehrVerstehe leider nicht, was du mir sagen willst. :-(

/edit: Hab's verstanden: Wir komen auch bei 10 Buchstaben an die Speichergrenze. Stimmt. :-(

/edit2: Also Sephirots Tip half, mit -Xmx500m gehen zehn Buchstaben in (bei mir) rund 14 Sekunden.
Werde mal drüber nachdenken. Problem ist aber vermutlich die Rekursion, die ja meist recht Speicher-intensiv ist.

mfg Sebastian

[Sephiroth]

soweit ich weiss sind es weitaus weniger. es sollten genau 8! (sprich 8fakultät) sein, was genau 40320 sind. (8 unterscheidbare kugeln, wieviele möglichkeiten beim ziehen ohne rücklegen).
Tja, n! wären eben Permutationen, d.h. keine Wiederholung. Und dafür könnte ich etwas anbieten (+ das von Crushi bereits verlinkte).
Ich habe das Problem jedoch als Variationen, in seinem Fall n^k, aufgefasst. Im worst case sind das 8^8.

1.) http://forum.java.sun.com/thread.jspa?threadID=555748
2.) http://www.tutorials.de/tutorials75639.html&highlight=permutation

Es stellt sich (mir) die Frage, ob bei abc auch aaa mit gezählt werden darf, oder nicht. Wenn ja, dann Variation -> n^k und sonst denke ich sind die Permutationen n! gemeint.


/edit:
//Array das sämtliche "Kombinationen mit Wiederholung" enthält
Also Variationen, sprich n^k.

[freakbodo]

aaa bei abc soll nicht gewertet werden, also schon permutation, habe das variations array nur zu hilfszwecken benutzt

[Neomi]

So, hier eine rekursive Variante, welche allerdings nicht berücksichtigt, daß Buchstaben mehrmals vorkommen können. Für zB "einsam" liefiert sie alle richtigen Kombinationen, für "alleine" gibt sie zum Beispiel "ainllee", "ainllee", "ainllee" und "ainllee", als verschiedene Kombinationen zurück. Daran knobel ich noch.

Das ist recht simpel. Wenn du in der Funktion "kombine" in der Schleife die einzelnen Zeichen des Reststrings durchgehst, dann mußt du nur jedes Zeichen überspringen, das es vorher schonmal im Reststring gab.

Konkretes Beispiel:
Der String "holla" würde z.B. auch "holla" und "holla" ergeben, nach den ersten zwei Zeichen ist der Reststring "lla". Das erste "l" (Position 0) nimmt er und machet mit dem Reststring "la" weiter. Das zweite "l" (Position 1) kannst du ignorieren, da an Position 0 schon eins vorkommt.

[Sephiroth]

So, hier eine rekursive Variante, welche allerdings nicht berücksichtigt, daß Buchstaben mehrmals vorkommen können. Für zB "einsam" liefiert sie alle richtigen Kombinationen, für "alleine" gibt sie zum Beispiel "ainllee", "ainllee", "ainllee" und "ainllee", als verschiedene Kombinationen zurück. Daran knobel ich noch.

Aber an für sich ist das doch korrekt - du hast quasi zwei verschiedene L's.

Wenn das eben die gleichen L's (oder welcher Buchstabe auch immer) sein sollen, müsstest du ja auf 7!/(2!*2!) kommen, da das l doppelt vorkommt und das e auch - mal jetzt auf dein Beispiel "alleine" bezogen.

[Pinoccio]

Aber an für sich ist das doch korrekt - du hast quasi zwei verschiedene L's.Naja, das ist aber mit Sicherheit nicht im Sinne der eigentlichen Aufgabenstellung!Das ist recht simpel. Wenn du in der Funktion "kombine" in der Schleife die einzelnen Zeichen des Reststrings durchgehst, dann mußt du nur jedes Zeichen überspringen, das es vorher schonmal im Reststring gab.Implementier's doch. ;-)

mfg Sebastian

[freakbodo]

Habe das Java heap space problem habe ich durch speichern nach jeweils 500000 Kombinationen und leeren des Vectors ,gelöst :biggrin:, allerdings mache ich mir durch das speichern jetzt die Platte voll (ca. 6MB pro 500000 Kombinationen :eek: ) kann mann das verringern. Eine "Optimierung" habe ich auch vorgenommen, sortiere jetzt alle Kombinationen die mit zwei gleichen Buchstaben beginnen aus (ich weiß es gibt einige Wörter die doppelten Anfangsbuchstaben zu lassen aber z.b Aachen aber darum kümmer ich mich später), hat jemand vielleicht noch andere optimierungs Möglichkeiten?

[ethrandil]

Für interessanter halte ich die Version, Worte mit zwei aufrinanderfolgenden Konsonanten auszuschließen! Allerdings muss man die Ausnahmen beachten: "ch", "ck", "mm", "nn" weiß nicht wieviele noch ;)

- Eth

P.S.: Ich werd mich gleich mal an dem Problem versuchen ;-)

[freakbodo]

hat ich mir auch schon überlegt allerdings weiß ich nicht ob es da nicht zu viele ausnahmen gibt und der aufwand sich dann noch lohnt. Besondern wenn man ans Ende des Wortes kommt, denn je weiter ich vorne abbrechen kann um so eher spare ich rechen-/rekursionsschritte

[ethrandil]

Also... ich hab das mal gamacht um zu gucken wie gut ich c++ noch/schon kann, und nun... verdammt ich liebe Java xD und das wäre in Java alles zig mal schneller geproggt gewesen. aber nungut.

Ich habe einfach mal doppelkonsonanten ausgeschlossen. Gleiche Buchstaben führen aber immernoch zu mehreren gleichen kombinationen. Nichtsdestotrotz habe ich bei unserem schönen Wörtchen 'alleine' dadurch nur 2832 statt 5040 ergebnisse.


*g*
Ich schaff also schon relativ große Kombinationen... nur... wozu brauchst du das? O_O

- Eth

EDIT: Das ist irgendwie noch verbuggt -.-
EDIT2: Vor dem Bug hatte ich nur 336 Möglichkeiten. menno *g*

[zeckensack]

#include <set>
#include <string>
#include <iostream>

static const char* const input="penixxx";

int
main()
{
int i;
std::set<char> base_set;
base_set.clear();
for (i=0;i<strlen(input);++i)
{
base_set.insert(input[i]); //Duplikate gehen futsch
}

//ausrechnen wieviele Permutationen es gibt
int pm_count=0;

if (base_set.size()>0)
{
//Fakultät ...
pm_count=1;
for (int mult=1;mult<=base_set.size();++mult)
{
pm_count*=mult;
}
}

//Huzzah!
//alle Kombinationen ausgeben
for (int pmi=0;pmi<pm_count;++pmi)
{
//wir bauen uns die Kombination direkt anhand der Nummer.
//Die Nummer wird schwer leiden, also erstmal kopieren.
int pm=pmi;
//Menge der zu verwurschtelnden Zeichen auch kopieren.
std::set<char> pm_set=base_set;
//und einen string für die Ausgabe
std::string pm_out="";

while (pm_set.size()>0)
{
int toothpick=pm%pm_set.size();
pm/=pm_set.size();

//kein operator [] beim set ist blöd ...
std::set<char>::iterator it=pm_set.begin();
for (int skip=0;skip<toothpick;++skip) ++it;
//Zeichen anhängen
pm_out+=*it;
//dieses Zeichen soll nicht wieder drankommen, also entfernen
pm_set.erase(it);
}

std::cout << "#" << pmi << ": ";
std::cout << pm_out << std::endl;
}

return(0);
}

[ethrandil]

zecki, du vergisst doch alle Wörter, in denen ein Buchstabe doppelt vorkommt. Bei penixxx muss ja auch "pinexxx" möglich sein. Bei dir kommt nir "pinex".

Hier ist mein bescheidener Vorschlag - bestimmt viel zu kompliziert. Mein erster c++-Versuch seit Ewigkeiten. Aber ich studier ja bald ;(
Korrigiert mal. Ich möchte guten Stil schreiben...


#include <iostream>
#include <iterator>
#include <list>
#include <string>

using namespace std;

struct Permutation {
string wort;
list < char >verbleibend;
};

// Damit aus der Liste immer nur ein Buchstsbe zur Zeit gelöscht wird
class EqualsOnce:public std::unary_function < char, bool > {
private:
bool foundOnce;
char subject;
public:
EqualsOnce(char sub) {
subject = sub;
foundOnce = false;
} bool operator () (char &val) {
bool right = (subject == val);
if(right) {
if(foundOnce) {
return false;
}
else {
foundOnce = true;
return true;
}
}
return false;
}
};

// Damit sortieren wir die Doppelgänger raus
class IsUniquePermutation:public std::binary_function < Permutation, Permutation, bool > {
public:
bool operator () (Permutation & val, Permutation & val2) {
return val.wort == val2.wort;
}};

// false bei unmöglichen Wörtern
bool gutesWort(string * wort)
{
if(wort->length() <= 2)
return true;

char vl = (*wort)[wort->length() - 2];
char l = (*wort)[wort->length() - 1];
// Ausnahmen:
if(vl == l)
return true;
if(vl == 'c' && (l == 'h' || l == 'k'))
return true;
if(vl == 't' && l == 'z')
return true;
// Die Regel:
char *vokale = "aeiuo";
while(*vokale != 0) {
if(vl == *vokale || l == *vokale)
return true;
vokale++;
}

return false;
}

// return: true falls weitere gefunden, sonst false
bool findePermutationen(list < Permutation > *perm)
{
if(perm->size() == 0)
return false;

Permutation p = perm->front();

if(p.verbleibend.size() == 0)
return false;
// Erste Permutation löschen, die Nachfolger werden später
// hinten wieder dran gehängt.
perm->pop_front();

list < char >::iterator iter_rest = p.verbleibend.begin();
list < char >::iterator iter_end = p.verbleibend.end();
// Alle Nachfolger ermitteln, uuund......
while(iter_rest != iter_end) {
char zeichen = *iter_rest;
Permutation neu = p;
neu.wort += zeichen;
neu.verbleibend.remove_if(EqualsOnce(zeichen));
// .. wieder dranhängen wenn sie gut genug sind
if(gutesWort(&neu.wort))
perm->push_back(neu);

iter_rest++;
}

return true;
}

long fak(int i)
{
int f = 1;
while(i > 0) {
f *= i;
i--;
}
return f;
}

int main(int argc, char *argv[])
{
if(argc < 1)
return -1;

// Initialobjekt
Permutation start;
// Anfangs ist noch jeder Buchstabe möglich
char *c = argv[1];
while(*c != 0) {
start.verbleibend.push_front(*c);
c += sizeof(char);
}

// Planschbecken für unsere Permutationen
list < Permutation > pool;
pool.push_front(start);

// Alle finden
while(findePermutationen(&pool));

int mitdublikaten = pool.size();
pool.unique(IsUniquePermutation());

// Ausgeben
list < Permutation >::const_iterator iter = pool.begin();
list < Permutation >::const_iterator ende = pool.end();

while(iter != ende) {
cout << ((Permutation) (*iter)).wort << endl;
iter++;
}

cout << "found: " << pool.size()
<< "/" << mitdublikaten << "/" << fak(start.verbleibend.size()) << endl;

return 0;
}
(die Formatierung ist nicht von mir, die ist automatisch und ich find sie doof...)

- Eth

[ScottManDeath]

Da' (http://www.codeproject.com/csharp/combinatorial_in_csharp.asp) , in C#, das hab ich mal genutzt. Hat die üblichen Verdächtigen wie Kombinationen, Permutationen und Variationen.

[freakbodo]

danke für die C-Programme, habe leider keine Ahnung von C, sondern nur von Java.

@ethrandil: hatte mal neunlive gesehen und da gibt es so lustige wortspiele wo sie dir eine Buchstabenkombination vorgeben, meist 9-12 Buchstaben und du ein Wort finden musst das genau aus den Buchstaben besteht, da habe ich mir geadcht das müsste man doch proggen können, um es dann zu verkaufen und neunlive in die pleite zu treiben ;D ;D ;D
PS das mit dem verkaufen war nur ein Scherz

[zeckensack]

zecki, du vergisst doch alle Wörter, in denen ein Buchstabe doppelt vorkommt.Sry, ich dachte das soll so :hammer:Bei penixxx muss ja auch "pinexxx" möglich sein.Ja hey, wenn das so ist, dann ist mir das zu kompliziert ;)

[ethrandil]

@ethrandil: hatte mal neunlive gesehen und da gibt es so lustige wortspiele wo sie dir eine Buchstabenkombination vorgeben, meist 9-12 Buchstaben und du ein Wort finden musst das genau aus den Buchstaben besteht, da habe ich mir geadcht das müsste man doch proggen können, um es dann zu verkaufen und neunlive in die pleite zu treiben ;D ;D ;D
PS das mit dem verkaufen war nur ein Scherz
Naja, das wirst du dir ja inzwischen abgeschminkt haben *g*
Das wort Zeckensack dauerte bei mir >10 minuten und hatte 7000 Ergebnisse. So oft solltest du da wirklich nicht anrufen ;-)

- Eth

[ethrandil]

hat ich mir auch schon überlegt allerdings weiß ich nicht ob es da nicht zu viele ausnahmen gibt und der aufwand sich dann noch lohnt. Besondern wenn man ans Ende des Wortes kommt, denn je weiter ich vorne abbrechen kann um so eher spare ich rechen-/rekursionsschritte
Hab grad das hier gefunden: http://www.steineule.de/schularb/Lesen_und_Schreiben/Buchstaben_und_Silben/Silbentabelle/silbentabelle.html
:ugly2:

- Eth

[freakbodo]

sieht interessant aus

[Gast]

http://www.mainzelahr.de/smile/schilder/guckstduhier.gif und zwar dahin (http://forum.java.sun.com/thread.jspa?threadID=618441&tstart=120). :)

[P2oldi]

evtl. findest Du auch hier (http://www.forum-3dcenter.org/vbulletin/showthread.php?t=251111&highlight=permutation) noch ein paar Anregungen um die Zeit zu optimieren

[Gast]

Dank sei Gott, und da behaupte nochmal einer Java hat ne umfassendere Standardbibliothek als C++

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

int main()
{
using namespace std;
string word;
getline(cin, word);
sort(word.begin(), word.end());
do {
cout << word << endl;
} while(next_permutation(word.begin(), word.end()));
}

[Pinoccio]

Dank sei Gott, und da behaupte nochmal einer Java hat ne umfassendere Standardbibliothek als C++

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

int main()
{
using namespace std;
string word;
getline(cin, word);
sort(word.begin(), word.end());
do {
cout << word << endl;
} while(next_permutation(word.begin(), word.end()));
} Eine Frage dazu: wie lang darf die Eingabe maximal sein, damit das Programm durchläuft?

mfg Sebastian

[Gast]

Das Programm ist sehr sehr schnell! Wenn du das Programm wie oben angegeben mit einem langen Wort fütterst wird es eventuell sehr lange für die Ausgabe benötigen. Das liegt aber nicht am Algorithmus für die Permutation, sondern an den Implementierungen der I/O-Streams. Zum Testen kann man das Programm ja mal ohne iostreams kompillieren und wird sehen dass es schneller wird.