myCSharp.de - DIE C# und .NET Community
Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 
 | Suche | FAQ

» Hauptmenü
myCSharp.de
» Startseite
» Forum
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Suche
» Regeln
» Wie poste ich richtig?
» Forum-FAQ

Mitglieder
» Liste / Suche
» Wer ist wo online?

Ressourcen
» openbook: Visual C#
» openbook: OO
» Microsoft Docs

Team
» Kontakt
» Übersicht
» Wir über uns

» myCSharp.de Diskussionsforum
Du befindest Dich hier: Community-Index » Diskussionsforum » Entwicklung » Rund um die Programmierung » Anzahl und Berechnung möglicher Kombinationen und Permutationen [inkl. Code-Snippets]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | Thema zu Favoriten hinzufügen

Antwort erstellen
Zum Ende der Seite springen  

Anzahl und Berechnung möglicher Kombinationen und Permutationen [inkl. Code-Snippets]

 
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
KRAFT
myCSharp.de-Mitglied

Dabei seit: 29.01.2005
Beiträge: 14


KRAFT ist offline

Anzahl und Berechnung möglicher Kombinationen und Permutationen [inkl. Code-Snippets]

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Hallo smile

Ich habe ein Schema mit 4 Feldern. Jedes dieser Felder kann einen von 3 Zustanden annehem (1,2,3). Die Anzahl der Möglichen Kombinatioen ist also 3 hoch 4 also 81 wenn ich das richtig sehe.

Um diese (alle) Kombinatioen zu erstellen (darzustellen) möchte ich eine Methode schreiben. Jetzt mal egal, wie ich das Designtechnisch mache.

Meine Überlegung war mehrere for-Schleifen in einander zu schachteln aber ... hat jemand so etwas eventuell schon einmal gemacht? Oder ist den Denkansatz falsch?
Wie hast du die "Zustände" dargestellt??

Danke für nen Tipp fröhlich
02.06.2005 20:44 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
S.H.-Teichhof S.H.-Teichhof ist männlich
myCSharp.de-Mitglied

avatar-2460.jpg


Dabei seit: 03.10.2004
Beiträge: 1.549
Entwicklungsumgebung: #Developer
Herkunft: Sindringen


S.H.-Teichhof ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Warum willst du den alle Kombinationen anzeigen??

Du könntest ja ein Abbild deiner anzeige als int Array speichern dann läst du das mit Hilfe einer schleife durchgehen und fertig.
02.06.2005 20:51 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
bitstream bitstream ist männlich
myCSharp.de-Mitglied

Dabei seit: 28.07.2004
Beiträge: 189
Entwicklungsumgebung: VS.NET 2003
Herkunft: Hannover


bitstream ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Zitat:
Original von KRAFT
Ich habe ein Schema mit 4 Feldern. Jedes dieser Felder kann einen von 3 Zustanden annehem (1,2,3). Die Anzahl der Möglichen Kombinatioen ist also 3 hoch 4 also 81 wenn ich das richtig sehe.

Nein, die Anzahl möglicher Kombinationen ist immer Stellen^Zustände, in deinem Fall also 4^3 = 64.

Den Rest deiner Frage habe ich nicht verstanden... :-/
02.06.2005 21:58 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Quallo
myCSharp.de-Mitglied

Dabei seit: 12.01.2005
Beiträge: 992
Entwicklungsumgebung: VS.NET 2005
Herkunft: Nähe Bremen


Quallo ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

@bitstream: Ich denke, dass Kraft recht hatte: Ich habe bei einer Stelle drei Zustände also drei Möglichkeiten.
Dass macht also Zustände^Stelle = 3^1 = 3.
Wäre es Stelle^Zustände, dann wäre es 1^3 = 1.

Also ist 3^4=81 schon richtig. Ist ja auch logisch. Erst habe ich drei möglichkeiten, dann das dreifache von drei, dann das dreifache davon, usw.
Also 3,9,27,81.


Ich denke, dass das mit den Schleifen am schnellsten ist.

C#-Code:
        int[,] fillpos()
        {
            int[,] returnvalue = new int[81,4];
            int[] looper = new int[4];

            int count = 0;

            for(looper[0] = 1; looper[0] < 4;looper[0]++)
            {
                for(looper[1] = 1; looper[1] < 4;looper[1]++)
                {
                    for(looper[2] = 1; looper[2] < 4;looper[2]++)
                    {
                        for(looper[3] = 1; looper[3] < 4;looper[3]++)
                        {
                            returnvalue[count]=looper; //hier ist ein Problem! ich habe ein zweidimensionales Array und ein eindimensionales Array. Wie kann ich dem Array an der Stelle counter in der 1. ebene jetzt ein ganzes array zuweisen? Wie sieht das mit der Performance aus? Ist es gleich schnell in Arrays zu zählen oder ist es wesentlich schneller, wenn ich ne stinknormale variable nehme?
                            count++;
                        }
                    }
                }
            }

        }
02.06.2005 22:25 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
bitstream bitstream ist männlich
myCSharp.de-Mitglied

Dabei seit: 28.07.2004
Beiträge: 189
Entwicklungsumgebung: VS.NET 2003
Herkunft: Hannover


bitstream ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Zitat:
Original von Quallo
@bitstream: Ich denke, dass Kraft recht hatte: Ich habe bei einer Stelle drei Zustände also drei Möglichkeiten.
Dass macht also Zustände^Stelle = 3^1 = 3.
Wäre es Stelle^Zustände, dann wäre es 1^3 = 1.

Stimmt, ich habe mich geirrt. Ich bin da wohl mit den Begriffen Felder und Zustände durcheinander geraten...

Es verhält sich ja so wie bei den Zahlensystemen! Wenn man eine vierstellige Binärzahl hat, gibt es 2^4=16 Kombinationen. Übertragen auf KRAFTs Frage haben wir also eine vierstellige Ternärzahl, also 3^4=81 Kombinationen.
02.06.2005 22:58 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
herbivore
myCSharp.de-Poweruser/ Experte

avatar-2627.gif


Dabei seit: 11.01.2005
Beiträge: 49.480
Entwicklungsumgebung: csc/nmake (nothing is faster)
Herkunft: Berlin


herbivore ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Hallo zusammen,

81 ist richtig.

Wenn du die möglichen Kombinationen haben willst, geht das auch besser und vor allem allgemeiner als mit vier ineinandergeschachtelten Schleifen:

C#-Code:
const int iDigitBase = 3;  // Anzahl der Zustände
const int iNumDigits = 4; // Anzahl der Felder

int [] iDigit = new int [iNumDigits];

int iNumCombinations = (int)Math.Pow (iDigitBase, iNumDigits);

for (int i = 0; i < iNumCombinations; ++i) {
   int i2 = i;
   Console.Write ((i2 + 1) + " = ");
   for (int i3 = 0; i3 < iNumDigits; ++i3) {
      iDigit [i3] = i2 % iDigitBase;
      i2 /= iDigitBase;
      Console.Write ((iDigit [i3] + 1) + ", ");
   }
   Console.WriteLine ();
}

herbivore

PS: Die Implementierung hat einige Schwächen, z.B. die Verwendung von Pow für int-Zahlen und die Ausgabe der Ziffern in der umgekehrten Reihenfolge inkl. überschüssigem Komma.
02.06.2005 23:09 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Quallo
myCSharp.de-Mitglied

Dabei seit: 12.01.2005
Beiträge: 992
Entwicklungsumgebung: VS.NET 2005
Herkunft: Nähe Bremen


Quallo ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Habt ihr eine Lösung für den Kommentar in meinem Code?
herbivore vielleicht?
Der Name birgt doch sonst für Qualität *g*!

Grüße Christoph
02.06.2005 23:26 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
herbivore
myCSharp.de-Poweruser/ Experte

avatar-2627.gif


Dabei seit: 11.01.2005
Beiträge: 49.480
Entwicklungsumgebung: csc/nmake (nothing is faster)
Herkunft: Berlin


herbivore ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Hallo Quallo,

danke für die Blumen. Leider erwischt du mich an einem schwachen Punkt, da ich kaum mehrdimensionale Arrays verwende. Anyway.

Zitat:
ich habe ein zweidimensionales Array und ein eindimensionales Array. Wie kann ich dem Array an der Stelle counter in der 1. ebene jetzt ein ganzes array zuweisen?

Ich denk, dass geht nur in einer Schleife mit Zuweisung der einzelnen Elemente. Oder du nimmst verzweige Arrays, also 'aai [1] [5]', dann kannst du Array.Copy bzw. Array.CopyTo benutzen. So oder so, muss performacetechnisch jedes Array-Element kopiert werden (was bei Array.Copy vermutlich etwas effizienter geht als von Hand).

Zitat:
Wie sieht das mit der Performance aus? Ist es gleich schnell in Arrays zu zählen oder ist es wesentlich schneller, wenn ich ne stinknormale variable nehme?

++i geht vermutlich ungefähr doppelt so schnell wie ++ai[j], aber da beides "keine" Zeit kostet, ist 2 mal Nullzeit immer noch Nullzeit :-) Will sagen, in den meisten Fällen wirst du keinen Unterschied spüren.

herbivore
03.06.2005 00:06 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Quallo
myCSharp.de-Mitglied

Dabei seit: 12.01.2005
Beiträge: 992
Entwicklungsumgebung: VS.NET 2005
Herkunft: Nähe Bremen


Quallo ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Vielleicht schaffe ich es, da einen kleinen Performance-Test hinzubekommen. Habe aber momentan wenig Zeit.

Danke erstmal für den Tip!

Grüße Christoph
03.06.2005 08:54 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Zwischen diesen beiden Beiträgen liegen mehr als 7 Monate.
Schattenkanzler Schattenkanzler ist männlich
myCSharp.de-Mitglied

Dabei seit: 27.04.2004
Beiträge: 238
Entwicklungsumgebung: Visual Studio 2008
Herkunft: Berlin


Schattenkanzler ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Hmm, der Algorithmus funktioniert ja an sich schon mal ziemlich gut, habe den gerade mal getestet.

Kann man den irgendwie anpassen, damit er alle möglichen Kombinationen innerhalb eines char-Arrays ausgibt? Das versuche ich nämlich und komme nicht auf den richtigen Trichter. Hier soll ebenfalls die Länge der enstehenden Wörter anzugeben sein, während die Möglichkeiten der Zustände durch den Inhalt des Arrays gegeben werden.

Beispielhaft:

C#-Code:
array ist {'a', 'b', 'c'}

Ausgabe soll sein:

a
b
c
aa
ab
ac
aaa
aab
aac
aba
abb
abc
...
usw.

Würde mich sehr freuen, wenn mir dazu jemand einen Tipp geben könnte!

Greets - SK

P.S: Es sieht zwar aus wie ein Bruteforce-Hacker-Tool *welch Wort*, soll aber keins sein. Dient mir eigentlich eher dazu, die möglichen Kombinationen in regulären Sprachen aufzudecken...

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Schattenkanzler am 30.01.2006 00:23.

30.01.2006 00:22 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
herbivore
myCSharp.de-Poweruser/ Experte

avatar-2627.gif


Dabei seit: 11.01.2005
Beiträge: 49.480
Entwicklungsumgebung: csc/nmake (nothing is faster)
Herkunft: Berlin


herbivore ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Hallo Schattenkanzler,

naja, anpassen oder neu implementieren :-)

C#-Code:
private static void ErzeugeAlleWorte (String strBegin, char [] ach, int iLen)
{
   if (iLen <= 0) {
      Console.WriteLine (strBegin);
      return;
   }

   foreach (char ch in ach) {
      ErzeugeAlleWorte (strBegin + ch, ach, iLen - 1);
   }
}

herbivore

Nachtrag: So kann man die Methode komfortabel aufrufen:

C#-Code:
public static void ErzeugeAlleWorte (String strInput)
{
   ErzeugeAlleWorte ("", strInput.ToCharArray (), strInput.Length);
}
30.01.2006 07:20 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Schattenkanzler Schattenkanzler ist männlich
myCSharp.de-Mitglied

Dabei seit: 27.04.2004
Beiträge: 238
Entwicklungsumgebung: Visual Studio 2008
Herkunft: Berlin


Schattenkanzler ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Wow, so kurz? Hab hier rumgeeiert bis zum getno...oh man! Danke dir, herb!

Greets - SK
30.01.2006 09:27 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Zwischen diesen beiden Beiträgen liegen mehr als 3 Jahre.
herbivore
myCSharp.de-Poweruser/ Experte

avatar-2627.gif


Dabei seit: 11.01.2005
Beiträge: 49.480
Entwicklungsumgebung: csc/nmake (nothing is faster)
Herkunft: Berlin


herbivore ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Hallo zusammen,

da ich gerade wieder über den Thread gestolpert bin, hier noch ein kleine Anmerkung.

Wenn man statt alle Kombinationen aus den Buchstaben nur alle Permutationen der Buchstaben haben möchte, dann reicht es vor den rekursiven Aufruf im foreach die Abfrage if (strBegin.IndexOf (ch) < 0) zu setzen(*). Bei der Eingabe "xy" bekommt man dann also statt allen Kombinationen (xx, xy, yx, yy) nur noch die Permutationen (xy, yx).

Das geht aber nur gut, solange jeder Buchstabe in der Eingabe nur genau einmal vorkommt. Hier eine Version von ErzeugeAllePermutationen die auch mit mehrfachen Vorkommen von Buchstaben klar kommt.

C#-Code:
public static void ErzeugeAllePermutationen (String strInput)
{
   Dictionary <char, int> dictNumOccurrences = new Dictionary <char, int> ();
   foreach (char ch in strInput) {
      if (!dictNumOccurrences.ContainsKey (ch)) {
         dictNumOccurrences [ch] = 1;
      } else {
         ++dictNumOccurrences [ch];
      }
   }
   char [] ach = new char [dictNumOccurrences.Count];
   dictNumOccurrences.Keys.CopyTo (ach, 0);
   Array.Sort (ach);

   ErzeugeAllePermutationen ("", ach, dictNumOccurrences, strInput.Length);
}

private static void ErzeugeAllePermutationen (String strBegin,
                                              char [] ach,
                                              Dictionary <char, int> dictNumOccurrences,
                                              int iLen)
{
   if (iLen <= 0) {
      Console.WriteLine (strBegin);
      return;
   }

   foreach (char ch in ach) {
      if (dictNumOccurrences [ch] > 0) {
         --dictNumOccurrences [ch];
         ErzeugeAllePermutationen (strBegin + ch, ach, dictNumOccurrences, iLen - 1);
         ++dictNumOccurrences [ch];
      }
   }
}

ErzeugeAllePermutationen ("xxxyy") ergibt also:

xxxyy
xxyxy
xxyyx
xyxxy
xyxyx
xyyxx
yxxxy
yxxyx
yxyxx
yyxxx

Wie gesagt, wenn jedes Element nur einmal vorkommt, kann man auch das einfachere Snippet von oben plus die zusätzliche Abfrage verwenden.

herbivore

EDIT:

(*) Statt den rekursiven Aufruf in den Then-Teil von if (strBegin.IndexOf (ch) < 0) zu setzen, kann man auch folgende Zeile (1) vor den rekursiven Aufruf schreiben:

C#-Code:
if (strBegin.IndexOf (ch) >= 0) { continue; }

Wenn man nicht die Permutation berechnen will, sondern die Kombinationen, die man - ohne Berücksichtigung der Reihenfolge - erhalten kann, wenn man aus dem Alphabet ach jeweils iLen-viele Buchstaben zieht (also analog der Lottozahlen, die am Ende auch aufsteigend geordnet sortiert gezeigt werden), dann kann man stattdessen folgende Zeile (2) vor den rekursiven Aufruf schreiben:

C#-Code:
if (strBegin.Length > 0 && strBegin [strBegin.Length-1] <= ch) { continue; }

Die Buchstaben tauchen dann innerhalb der berechneten Kombinationen nur noch strikt aufsteigend geordnet auf. Damit erhält man also nur die normierten Kombinationen, die jeweils der Menge der enthaltenen Buchstaben entspricht.

Die Bedingung von Zeile 2 ist schließt die Bedingung von Zeile 1 mit ein. Es gibt also keinen Fall, in denen Bedingung 1 wahr ist, ohne dass Bedingung 2 nicht auch wahr ist. Wenn man Zeile 2 in den Code schreibt, ist folgerichtig Zeile 1 nicht mehr nötig.

Ich bin für die Nachvollziehbarkeit zunächst so nah wie möglich am Ausgangscode geblieben. Das ganze lässt sich jedoch noch etwas effizienter ermitteln.

Wenn man sich als Gedankenexperiment vorstellt, dass die Buchstaben in ach alphabetisch sortiert sind, sieht man, dass Zeile 2 dazu führt, dass immer nur Buchstaben angehängt werden, die von ihrer Indexposition strikt hinter allen Buchstaben stehen, die schon in strBegin enthalten sind.

Mit diesem Wissen lässt sich eine effizientere Implementierung finden, die an den rekursiven Aufruf zusätzlich die Indexposition des aktuellen Buchstabens übergibt. Dann kann man die Schleife nämlich so aufbauen, dass sie nur über die dahinterstehenden Buchstaben läuft.

Selbst wenn wir gedanklich jetzt einen Schritt zurückgehen und die Buchstaben als nicht mehr sortiert ansehen, sieht man, dass trotzdem alle gewünschten Kombinationen berechnet werden (wenn dann auch nicht mehr in alphabetisch aufsteigender Reihenfolge).

Im Ergebnis also bekommt man folgenden Code. Genau genommen wird dabei nicht der Index des aktuellen Buchstabens übergeben, sondern der jeweils nächste zu berücksichtigende Index. Gestartet wird mit Index 0, also ErzeugeAlleWorte3 ("", ach, 0, 5):

C#-Code:
private static void ErzeugeAlleWorte (String strBegin, char [] ach, int iIndex, int iLen)
{
   if (iLen <= 0) {
      Console.WriteLine (strBegin);
      return;
   }
   for (int iCurrIndex = iIndex; iCurrIndex < ach.Length; ++iCurrIndex) {
      ErzeugeAlleWorte (strBegin + ach[iCurrIndex], ach, iCurrIndex + 1, iLen - 1);
   }
}

Diese Variante ist annähernd doppelt so schnell, wie die davor.

Sie ist allerdings etwas weniger robust und liefert die Kombinationen nur dann normiert und sortiert, wenn die Buchstaben in ach sortiert sind und keine doppelten enthalten.

Suchhilfe: 1000 Worte
26.06.2009 14:24 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Zwischen diesen beiden Beiträgen liegen mehr als 2 Jahre.
ProgrammierTroll
myCSharp.de-Mitglied

avatar-3285.jpg


Dabei seit: 12.07.2011
Beiträge: 107


ProgrammierTroll ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Hat jemand eine Idee, wie man die Permutationen iterativ generieren kann? Leider bekommt ja schon bei relativ kurzen Strings einen StackOverFlow. enttäuscht

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von ProgrammierTroll am 24.07.2011 22:09.

24.07.2011 22:09 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
gfoidl gfoidl ist männlich
myCSharp.de-Team

avatar-2894.jpg


Dabei seit: 07.06.2009
Beiträge: 6.673
Entwicklungsumgebung: VS 2019
Herkunft: Waidring


gfoidl ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Hallo ProgrammierTroll,

siehe Fisher-Yates-Shuffle und davon abgeleitete Varianten.
Für alle Permutationen zB Steinhaus–Johnson–Trotter Algorithmus.

mfG Gü
24.07.2011 22:18 Beiträge des Benutzers | zu Buddylist hinzufügen
ProgrammierTroll
myCSharp.de-Mitglied

avatar-3285.jpg


Dabei seit: 12.07.2011
Beiträge: 107


ProgrammierTroll ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Danke, letzterer war, was ich gesucht habe.

Ärgerlich, dass einem sowas nicht selbst einfällt. 8[
24.07.2011 23:12 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
gfoidl gfoidl ist männlich
myCSharp.de-Team

avatar-2894.jpg


Dabei seit: 07.06.2009
Beiträge: 6.673
Entwicklungsumgebung: VS 2019
Herkunft: Waidring


gfoidl ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Hallo ProgrammierTroll,

Zitat:
Ärgerlich, dass einem sowas nicht selbst einfällt.

Stimmt. Aber selbst dann ist es schon publiziert worden und man zieht dennoch den Kürzeren.

Aber das ist das schöne an dieser Art von Algorithmen: genial einfach.*

* nur draufkommen muss man. Das ist der schwierigere Teil davon :-)

mfG Gü
24.07.2011 23:14 Beiträge des Benutzers | zu Buddylist hinzufügen
ProgrammierTroll
myCSharp.de-Mitglied

avatar-3285.jpg


Dabei seit: 12.07.2011
Beiträge: 107


ProgrammierTroll ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Zitat von gfoidl:

Aber das ist das schöne an dieser Art von Algorithmen: genial einfach.*

* nur draufkommen muss man. Das ist der schwierigere Teil davon :-)


Habe diesen Alogrithmus im Studium nie kennengelernt, obwohl der eigentlich wesentlich inuitiver als der rekursive ist. Immerhin was dazu gelernt!
24.07.2011 23:26 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
herbivore
myCSharp.de-Poweruser/ Experte

avatar-2627.gif


Dabei seit: 11.01.2005
Beiträge: 49.480
Entwicklungsumgebung: csc/nmake (nothing is faster)
Herkunft: Berlin


herbivore ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Hallo ProgrammierTroll,

beim meinen Permutations-Snippet ist die maximale Rekursionstiefe gleich der die Länge des Eingabestrings. Da schon relativ kurze Eingabestrings sehr viele Permutationen besitzen, wird die Stackgröße sicher nicht das Problem sein. Bei vernünftigen Eingabelängen wirst du sicher keine StackOverflowException bekommen.

herbivore
25.07.2011 02:34 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
ProgrammierTroll
myCSharp.de-Mitglied

avatar-3285.jpg


Dabei seit: 12.07.2011
Beiträge: 107


ProgrammierTroll ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Ich habe Probleme bei Strings mit einer Länge von ca. 30 Zeichen bekommen.

Iterativ funktionuggelt das einwandfrei. großes Grinsen

ProgrammierTroll hat dieses Bild (verkleinerte Version) angehängt:
progginTroll.png
Volle Bildgröße

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von ProgrammierTroll am 25.07.2011 03:45.

25.07.2011 03:21 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
herbivore
myCSharp.de-Poweruser/ Experte

avatar-2627.gif


Dabei seit: 11.01.2005
Beiträge: 49.480
Entwicklungsumgebung: csc/nmake (nothing is faster)
Herkunft: Berlin


herbivore ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Hallo ProgrammierTroll,

bei einem String der Länge 30 mit 30 verschiedenen Zeichen gibt es 30! (=Fakultät von 30) Permutationen, also ca. 2,7 * 10^32. Wenn wir hypothetisch und etwas überoptimistisch annehmen, dass der Rechner 10^12 Permutationen pro Sekunde berechnen kann, dann wäre er erst nach 8,4 Billionen Jahren fertig.

Wenn in dem String einige Zeichen mehrfach vorkommen, reduziert sich die Anzahl etwas, aber vom Prinzip her ändert sich nichts.

30 ist also sicher keine vernünftige Eingabelänge.

Trotzdem habe mein Snippet eine Weile sogar mal mit einem String der Länge 62
("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") rechnen lassen. Wie erwartet: kein StackOverflow.

Rekursiv funktioniert also natürlich auch einwandfrei (und liefert zudem die Permutationen noch in der systematischen Reihenfolge).

Deshalb komme ich zu dem Schluss, dass du deinem Namen manchmal alle Ehre machst. :-)

herbivore
25.07.2011 04:07 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Baumstruktur | Brettstruktur       | Top 
myCSharp.de | Forum Der Startbeitrag ist älter als 15 Jahre.
Der letzte Beitrag ist älter als 9 Jahre.
Antwort erstellen


© Copyright 2003-2020 myCSharp.de-Team | Impressum | Datenschutz | Alle Rechte vorbehalten. | Dieses Portal verwendet zum korrekten Betrieb Cookies. 27.11.2020 14:53