[C] Buchstabensalatalgorithmus

[romansvillage]

Gibt es einen Algorithmus oder einen Lösungsansatz mit dem ich eine Buchstabenkette die in einem String gespeichert ist zu Wörtern machen kann?
Wenn z.B. die eingabe abc ist dass dann abc, acb, bac, bca, cab, cba herauskommt?

 

[Tobias K.]

moin


Geben tut es sowas in C standartmäßig nicht.
Aber selber machen ist doch kein Ding. Dürfen Zahlen/Zeichen doppelt vorkommen?


mfg
umbrasaxum

 

[romansvillage]

Die Zeichen dürfen nur einmal vorkommen. Ausser das Zeichen ist schon doppelt im String vorhanden.

Leider hab ich im Moment echt keinen Plan wie ich das selbst lösen soll, könnt ihr mir vielleicht ein bisschen auf die Sprünge helfen?

 

[Endurion]

Würde ich rekursiv lösen. Stur von vorne bis hinten, einen möglichen Buchstaben einsetzen, und die restliche Buchstaben liste an die Einsetzroutine übergeben. Lässt sich aber auch recht einfach nicht rekursiv machen.
Im Grunde baust du dir erstmal eine Liste aller vorkommenden Buchstaben.
Dann eine Kopie der Liste erzeugen. Ersten Buchstaben rausnehmen, an Routine weitergeben. Danach zweiten Buchstaben, usw.

 

[romansvillage]

Ich habs jetzt mal so gelöst:

for(z = 0; z < i; z++) // i steht für die Länge der Zeichenkette
{
  for(j = 0; j < i - z; j++)
  {
    temp = zeichenfolge[z+j];
    zeichenfolge[z+j] = zeichenfolge[z];
    zeichenfolge[z] = temp;
    for(x = 0; x < i; x++)
    {
      printf("%c",zeichenfolge[x]);
    }
    printf("\n");
  }
}

Dabei kommt aber nur folgendes heraus:
ABC
BAC
CAB
CAB
CBA
CBA

Ich komme wiedermal nicht mehr weiter. Wäre froh wenn mir jemand weiterhelfen könnte.

 

[MFC openGL]

Such mal nach PIVOT Algorithmus, das ist ein Tauschverfahren welches dir alle möglichen Kombinationen einer Anordnung liefert.

Wenn du das auch dann nicht hinbekommst, meld dich nochmal, irgendwo hab ich den Algo noch fertig rumfliegen. Aber selbst versuchen ist immer besser.

Gruss

MFC OpenGL

 

[romansvillage]

Ich hab beim googlen nichts gescheites über den PIVOT-Algorithmus gefunden.

 

[Kachelator]

Geben tut es sowas standartmäßig nicht.

Doch, tut es.

In der Headerdatei <algorithm> findest du Algorithmen wie std::next_permutation und std:: prev_permutation , die im Prinzip nichts anderers tun, als Sequenzen wiederholt durcheinanderzuwürfeln.
Nützlich ist auch std::random_shuffle. Damit wird eine Sequenz einfach beliebig verwürfelt.

Informationen dazu (wie immer) in der MSDN-Lib (auch online). Es lohnt sich auf jeden Fall, sich die Funktionen einmal anzusehen. Das gilt natürlich auch für die anderen Algorithmen in der STL. Sich da einzuarbeiten ist wesentlich klüger, als immer wieder das Rad neu zu erfinden.

Falls noch Fragen auftauchen zur Benutzung: Bitte melden!

----

Edit: Sorry, mir ist erst gerade aufgefallen, dass im Titel ein C steht. Die STL steht bei reinem C natürlich nicht zur Verfügung. Dazu muss man C++ verwenden.

 

[MFC openGL]

Ich hab beim googlen nichts gescheites über den PIVOT-Algorithmus gefunden.

Na dann, hier haste nen Permutationsalgo, ist jetzt nicht der Pivot, den find ich gerade nicht, aber der hier tuts auch.

char bk[11];  //zeichenkettenspeicher
 
 
int eingabeb()  //NICHT C KONFORM, kannste aber durch printf und scanf ersetzen....
{
 cout<<endl<<"Bitte Zeichenkette zur Permutation eingeben(max. 10 Zeichen) : "; 
 cin>>bk;
 for(int i = 0; bk[i] != '\0'; i++); //zählt die zeichenanzahl
 
 cout<<endl<<"eingelesen : "<<bk[9]<<bk[8]<<bk[7]<<bk[6]<<bk[5]<<bk[4]<<bk[3]<<bk[2]<<bk[1]<<bk[0]<<endl;
 return i; 
}
 
 
int maxcheck(int anzahl)
{
 return faku(anzahl);
}
 
 
int faku(int anzahl)
{
 if(anzahl == 0)  
  return(1); 
 else   
  return(anzahl*faku(anzahl-1)); 
}
 

void swap(int anzahl, int max)  //PERMUTATION
{
 int puffer, k = 0;
 while(k != max)
 {
  for(int i = 0; i < anzahl-1; i++)
  {
   ausgabe(anzahl);	//<------ HIER kannst du die aktuelle PERMUTATION entnehmen, einfach abspeichern oder sonstwas mit machen
   puffer = zk[i];
   zk[i] = zk[i+1];
   zk[i+1] = puffer;
   k++;
  }
 }
}
 
 
void ausgabe(int anzahl)
{
 for(int i = 0; i < anzahl; i++)
  printf("%c   ",zk[i]);
}
 
void main()
{
 int max, anzahl;
 char buf;
	  anzahl = eingabeb();  //anzahl ist die anzahl der zu permutierenden zeichen
	  max = maxcheck(anzahl);  //berechnet anzahl der swaps
	  swapb(anzahl, max);  
}

Wenn du das nimmst bekommste immer alle möglichen Permutationen von einem char den du reingibst...

Gruss

MFC OpenGL


PS : Normalerweise geb ich keine fertigen Programme raus, aber da ich das hier gerade hatte....