Mir fällt da pauschal kein geeigneter Titel ein ;)

[Tribal]

Manchmal hilft ja auch schon das drüber sprechen, um aufs Ergebnis zu kommen...

Folgendes...
Ich möchte gerne ein Programm erstellen, welches mir sämtliche Kombinationen zu einem definiertem Zeichensatz ausgibt...

Ich habe ins Programm die Möglichkeit eingebaut den Zeichensatz zu definieren, sodass man sagen kann das Wort besteht nur aus den Buchstaben "a, b, c und d". Nun soll der gute Junge ja wie folgt die Wörter ausgeben:

aaaa
aaab
aaac
aaad

aaba
aabb
aabc
aabd

usw.

Nunja... mit meinem Code macht er das Ergebnis immer nur zweistellig

aa
ab
ac
ad

ba
bb
bc
bd

usw.

Auszug des Codes:

For i = 0 To LST_Zeichensatz.ListCount - 1
For k = 0 To LST_Zeichensatz.ListCount - 1
TXT_Kombination.Text = TXT_Kombination.Text + LST_Zeichensatz.List(i) + LST_Zeichensatz.List(k) + vbNewLine
Next k
Next i


TXT_Kombination ist eine Textbox in der die Kombinationen drin stehen.
LST_Zeichensatz ist eine Liste, in der die Zeichen stehen, pro Zeichen eine Zeile.


Frage also, wie mach ich das, das er nicht nur zweistellig ausgibt, sondern sovielstellig, wieviel Zeichen ich im Zeichensatz definiert habe?


Liebe Grüße,
Tribal

[Jan Krüger]

Geht natürlich mit der aktuellen Struktur nicht. Ansatz:

1) Ergebnis = (Anzahl Zeichen) x '(erstes Zeichen in der Liste)', z.B. "aaaa"
2) Arbeitsposition: letztes Zeichen
3) Zeichen an Arbeitsposition durchiterieren (am Anfang "aaaa", "aaab", "aaac", "aaad"; jede Iteration ausgeben)
4) Arbeitsposition um eins verringern, alle Zeichen danach auf erstes Zeichen in der Liste setzen
5) Zurück zu 2), wenn nicht Arbeitsposition = Anfang des String
6) Ende

Der Algorithmus ist wahrscheinlich nicht optimal zeitkomplex, aber mehr fällt mir so früh am Morgen nicht ein.

Zum Threadtitel: vielleicht "alle Permutationen ausgeben"?

[Tribal]

muchos gracias jast :)

Joah eben, ich hab das alles schonmal durch, allerdings is das schon ne weile her und ich hab vergessen wies geht...

Danke nochmals :)

[Scavi]

Habt ihr euch schon mal mit Grammatiken beschäftigt? So'n Spass kannste auch leicht mit einer Turingmaschine lösen.

[Tribal]

Habt ihr euch schon mal mit Grammatiken beschäftigt? So'n Spass kannste auch leicht mit einer Turingmaschine lösen.


Wenn du so nett wärst und mir sagst was eine Turingmaschine sein soll, dann wäre ich dir sehr verbunden :)

[Jan Krüger]

Macht das die Sache leichter? Nein.

Eine Turingmaschine ist ein nicht nachbaubares theoretisches Modell für eine Maschine, mit der man alles berechnen kann, entwickelt von (daher der Name) Alain Turing.

[Scavi]

Macht das die Sache leichter? Nein. Hab ich das behauptet? Mir ist nur aufgefallen, dass das eine Grammatik repräsentiert und mit einer Turingmaschine lösbar wäre. Also geht es auch primitiv rekursiv zu lösen. Nur mal so als Denkansatz. Eine Turingmaschine ist ein nicht nachbaubares theoretisches Modell für eine Maschine ...wenn du nicht annimmst, dass die Bänder unendlich sind, kannst du sie nachbauen!

[Tribal]

Hab ich das behauptet? Mir ist nur aufgefallen, dass das eine Grammatik repräsentiert und mit einer Turingmaschine lösbar wäre. Also geht es auch primitiv rekursiv zu lösen. Nur mal so als Denkansatz. ...wenn du nicht annimmst, dass die Bänder unendlich sind, kannst du sie nachbauen!


Und wie du recht hast, Danke Scavi... Ich habs Rekursiv gebaut und holla die Waldfee es klappt perfekt. Wer interesse am Code hat (C#) dem klatsch ich das hier mal so einfach hin :)


using System;
using System.IO;

namespace WordListGenerator
{
class Class1
{
static private decimal Counter = 0;
static private char[] Zeichensatz;
static private string Ausgabe = "";
static private bool Anzeige = true;
static StreamWriter sw = new StreamWriter(AppDomain.CurrentDomain.BaseDirectory + "List.txt");
[STAThread]
static void Main(string[] args)
{
Console.WriteLine("Bitte geben Sie an, wieviele Zeichen es sind und drücken Sie dann Enter.");
int AnzahlZeichen = Convert.ToInt32(Console.ReadLine());

Console.WriteLine("Bitte spezifizieren Sie nun die Zeichen, die benutzt werden duerfen.\r\n(Beispiel: abcdefg123) würde nur die Buchstaben a-g und die Zahlen 1-3 benutzen.");
string Zeichen = Console.ReadLine();
Zeichensatz = Zeichen.ToCharArray();

Console.WriteLine("Bei einer größeren Anzahl von Zeichen kann das Darstellen auf die Konsole\r\ndie Geschwindigkeit stark beeinflussen.\r\n\r\nSollen die Kombinationen in der Konsole dargestellt werden ? (ja/nein)");
Again:
string Antwort = Console.ReadLine();
if(Antwort.ToLower() == "ja")
Anzeige = true;
if(Antwort.ToLower() == "nein")
Anzeige = false;

if(Antwort.ToLower() != "ja" && Antwort.ToLower() != "nein")
{
Console.WriteLine("Falsche Eingabe. Bitte Wiederholen.");
goto Again;
}


char[] CharArray = new char[AnzahlZeichen];
for(int i = 0; i < CharArray.Length; i++)
{
CharArray[i] = Zeichensatz[0];
}
Recursion(CharArray,CharArray.Length-1,0,CharArray.Length-1);

Console.WriteLine("Es gab " + Counter.ToString() + " Möglichkeiten. Drücken Sie Enter um das Programm zu beenden.");
sw.Close();
System.Diagnostics.Process p = new System.Diagnostics.Process();
p.StartInfo = new System.Diagnostics.ProcessStartInfo(AppDomain.CurrentDomain.BaseDirectory + "List.txt");
p.Start();

Console.ReadLine();
}
private static void Recursion(char[] CharArray, int Dimension, int Current, int Max)
{
for(int z = 0; z < Zeichensatz.Length; z++)
{
CharArray[Dimension] = Zeichensatz[z];
if(Current <= Max && Dimension > 0)
Recursion(CharArray,Dimension-1,Current+1,Max);

Ausgabe = "";
for(int k = 0; k < CharArray.Length; k++)
{
Ausgabe+=CharArray[k];
}
if(Anzeige)
Console.WriteLine(Ausgabe);
sw.WriteLine(Ausgabe);
Counter++;
}
}
}
}

[Jan Krüger]

Wenn die Bänder nicht unendlich sind, ist es keine Turingmaschine, denn dann kannst du z.B. nicht das Traveling-Salesman-Problem für beliebig große Graphen lösen.

[Scavi]

Wenn die Bänder nicht unendlich sind, ist es keine Turingmaschine, denn dann kannst du z.B. nicht das Traveling-Salesman-Problem für beliebig große Graphen lösen. Ach ja?! Wieso kann mein Rechner dann das TSP lösen? Heutige Rechner können durchaus als TM angesehen werden. Denn sobald ein Problem auf der TM lösbar ist, ist es im PF lösbar, was impliziert, dass es auf einen Standardrechner lösbar ist.

[Jan Krüger]

Turing-Vollstaendigkeit hat jeder heutige Rechner, aber er kann eine Turingmaschine nicht ersetzen. Versuch mal, auf deinem Rechner das TSP fuer 10^1000 Staedte zu loesen... die Turingmaschine kann das, also wird dein Rechner das laut deiner Aussage auch koennen muessen. ;)

[Scavi]

Bei der TM geht es ja nicht um das Lösen aller Möglichkeiten eines Problem, es geht darum zu zeigen, dass das Problem überhaupt lösbar ist und zwar primitiv rekursiv. Und dafür muss man nicht alle Möglichkeiten durchgehen. Wenn also das TSP für wenige Städte lösbar ist, ist es auch lösbar für viele Städte! ...und das kann ich dir mit meinem PC zeigen ;)

[Quantumseeker]

Bei der TM geht es ja nicht um das Lösen aller Möglichkeiten eines Problem, es geht darum zu zeigen, dass das Problem überhaupt lösbar ist und zwar primitiv rekursiv. Und dafür muss man nicht alle Möglichkeiten durchgehen. Wenn also das TSP für wenige Städte lösbar ist, ist es auch lösbar für viele Städte! ...und das kann ich dir mit meinem PC zeigen ;)

Es ist nicht nur die Frage, ob ein Problem lösbar ist, sondern auch in welcher Zeit und mit welchem Aufwand. (Probleme, die in (nicht-)polynomieller Zeit lösbar sind). Aber ein PC ist von den möglichen Operationen her genauso mächtig wie eine TM, und umgekehrt. Beide können, bei "beliebiger Speichererweiterung" bis um einen konstanten Faktor alle Probleme der gleichen Äquivalenzklasse in der selben Klasse lösen.
Afair.

[Scavi]

Yup. Und wie gesagt ... TM -> primitiv rekursiv.

[Quantumseeker]

Yup. Und wie gesagt ... TM -> primitiv rekursiv.
Die TM hat nicht nur die Mächtigkeit der primitiven Rekursion, sondern auch noch die der mü-Rekursion ^^ *nitpicking*

[Scavi]

Ähh, aber impliziert PR nicht MÜ?

[Quantumseeker]

Ähh, aber impliziert PR nicht MÜ?
Wenn etwas primitiv rekursiv ist, muss es nicht unbedingt auch mü rekursiv sein. Aber alles was mü-rekursiv ist, ist auch primitiv rekursiv.
Beispiel: Die Ackermann funktion ist total, mü-rekursiv, aber nicht primitiv rekursiv :)

[Scavi]

Stümmt, du hast Recht. Naja, ist schon ne Weile her bei mir ;)