Berechnung des N-ten Permutationsschritts?

Question

Ich habe ein char[26] der Buchstaben a-z und über verschachtelte for-Anweisungen, die ich eine Liste von Sequenzen wie produzieren:

aaa, aaz... aba, abb, abz, ... zzy, zzz.

Gegenwärtig wird die Software so geschrieben, dass sie eine Liste aller möglichen Werte von aaa-zzz erstellt, dann einen Index verwaltet und jeden dieser Werte durchläuft, indem sie eine Operation an ihnen durchführt.

Die Liste ist offensichtlich groß, nicht lächerlich groß, aber sie ist an einem Punkt angelangt, an dem der Speicherbedarf zu groß ist (es gibt auch andere Bereiche, die untersucht werden, aber das ist einer, den ich habe).

Ich versuche, eine Formel zu erstellen, bei der ich den Index beibehalten, aber die Liste der Sequenzen abschaffen und die aktuelle Sequenz auf der Grundlage des aktuellen Index berechnen kann (da die Zeit zwischen den Operationen zwischen den Sequenzen lang ist).

Beispiel:

char[] characters = {a, b, c... z};
int currentIndex = 29; // abd

public string CurrentSequence(int currentIndex)
{
    int ndx1 = getIndex1(currentIndex); // = 0
    int ndx2 = getIndex2(currentIndex); // = 1
    int ndx3 = getIndex3(currentIndex); // = 3

    return string.Format(
        "{0}{1}{2}", 
        characters[ndx1], 
        characters[ndx2], 
        characters[ndx3]); // abd
}

Ich habe versucht, ein kleines Beispiel mit einer Teilmenge (abc) auszuarbeiten und zu versuchen, mit Hilfe der Modulo-Division einen Index zu erstellen, aber ich habe heute Schwierigkeiten beim Denken und bin ratlos.

Ich erwarte keine Antwort, nur irgendeine Art von Hilfe. Vielleicht einen Tritt in die richtige Richtung?

Answer 1

Hinweis: Stellen Sie sich vor, Sie würden eine Zahl zur Basis 26 statt zur Basis 10 und mit Buchstaben anstelle von Ziffern drucken. Wie lautet der allgemeine Algorithmus für die Anzeige einer Zahl in einer beliebigen Basis?

Spoiler (zum Anzeigen nach rechts scrollen)

                                                                                      int ndx1 = currentIndex / 26 / 26 % 26;
                                                                                      int ndx2 = currentIndex / 26 % 26;
                                                                                      int ndx3 = currentIndex % 26;

Answer 2

So etwas sollte funktionieren, wenn man von 26 Zeichen ausgeht:

public string CurrentSequence(int currentIndex) {
    return characters[currentIndex / (26 * 26)] 
        + characters[(currentIndex / 26) % 26]
        + characters[currentIndex % 26];
}

Answer 3

Wow, zwei Fragen an einem Tag die über kartesische Produkte gelöst werden können. Erstaunlich.

Sie können verwenden LINQ-Schnipsel von Eric Lippert um alle Kombinationen der Indexwerte zu erzeugen. Dieser Ansatz führt zu einem Streaming-Set von Werten, so dass sie nicht im Speicher gespeichert werden müssen. Mit diesem Ansatz wird die Logik der Codeerzeugung von der Verwaltung des Zustands oder der Durchführung von Berechnungen mit dem Code getrennt.

Erics Code für alle Kombinationen:

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)  
{  
  IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };  
  return sequences.Aggregate(  
    emptyProduct,  
    (accumulator, sequence) =>   
      from accseq in accumulator   
      from item in sequence   
      select accseq.Concat(new[] {item}));                 
} 

Sie können jetzt schreiben:

public static IEnumerable<string> AllCodes()
{
  char[] characters = {a, b, c... z}; 
  IEnumerable<char[]> codeSets = new[] { characters, characters, characters };

  foreach( var codeValues in codeSets.CartesianProduct() )
  {
    yield return 
       string.Format( "{0}{1}{2}", codeValues[0], codeValues[1], codeValues[2]);
  }
}

Der obige Code erzeugt eine Streaming-Sequenz aller Code-Strings aus aaa a zzz . Sie können diese nun an anderer Stelle verwenden, wo Sie Ihre Verarbeitung durchführen:

foreach( var code in AllCodes() )
{
    // use the code value somehow...
}

Answer 4

Es gibt mehrere Möglichkeiten, Ihr Problem zu lösen, aber eine Option besteht darin, die Sequenz im laufenden Betrieb zu erzeugen, anstatt sie in einer Liste zu speichern:

IEnumerable<String> Sequence() {
  for (var c1 = 'a'; c1 <= 'z'; ++c1)
    for (var c2 = 'a'; c2 <= 'z'; ++c2)
      for (var c3 = 'a'; c3 <= 'z'; ++c3)
        yield return String.Format("{0}{1}{2}", c1, c2, c3);
}

Sie können dann alle Zeichenketten aufzählen:

foreach (var s in Sequence())
  Console.WriteLine(s);

Dieser Code verwendet überhaupt keine Indizes, aber er ermöglicht es Ihnen, mit einfachem Code und ohne Speicherung der Zeichenketten eine Schleife um die Folge von Zeichenketten zu erstellen.