Wie Permutationen in linearer Zeit, mit einem Twist berechnen

Question

Ich habe eine Ressourcenplanung Problem in Java, wo die Dinge zu sequenzierenden müssen, aber es gibt Einschränkungen auf, welche Ressourcen nebeneinander sein können. Eine gute Analogie ist eine Reihe von „Ziffern“, wo nur bestimmte Ziffern nebeneinander sein können. Meine Lösung war rekursiv, und arbeitet für kleine Saiten in Ordnung, aber die Laufzeit ist O (X ^ N), wobei X die Anzahl der möglichen Stellen (die Basis), und N ist die Länge der Saite. Es wird schnell unhandlich.

, um die Kompatibilitätsmatrix unter Verwendung, hier sind ein paar Beispiele von erlaubtem Strings
Länge von 1: 0, 1, 2, 3, 4
Länge von 2: 02, 03, 14, 20, 30, 41
Länge von 3: 020, 030, 141, 202, 203, 302, 303, 414

     0  1  2  3  4
   ---------------------
0|  0  0  1  1  0
1|  0  0  0  0  1
2|  1  0  0  0  0
3|  1  0  0  0  0
4|  0  1  0  0  0

Meine Lösung alle Strings der Länge N zum Zählen war mit einem leeren String beginnen, permutiert die erste Ziffer und einen rekursiven Anruf für alle Strings der Länge N-1. Die rekursive Aufrufe überprüfen Sie die letzte Ziffer, die hinzugefügt wurde und versuchen, alle Permutationen, die zu dieser Ziffer nächsten sein kann. Es gibt einige Optimierungen vorgenommen, so dass ich nicht versuchen, und permutiere 00, 01, 04 jedes Mal, zum Beispiel - nur 02, 03, aber die Leistung ist immer noch schlecht, wie es von der Basis 5 (das Beispiel) skaliert auf Basis 4000.

Alle Gedanken auf einem besseren Weg, um die Permutationen zu zählen andere als zu versuchen, sie alle aufzuzählen?

Answer 1

Wenn Sie nur die Anzahl der Saiten einer bestimmten Länge möchten, können Sie einfach die Kompatibilitätsmatrix multiplizieren mit sich selbst ein paar Mal, und fassen es Werte.

  

n = Länge der Zeichenfolge
   A = Kompatibilitätsmatrix
   Anzahl der möglichen Zeichenketten = Summe von A ^{n -1}

Ein paar Beispiele:

n = 1
| 1 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 0 0 |
| 0 0 0 1 0 |
| 0 0 0 0 1 |
sum: 5

n = 3
| 2 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 1 0 |
| 0 0 1 1 0 |
| 0 0 0 0 1 |
sum: 8

n = 8
| 0 0 8 8 0 |
| 0 0 0 0 1 |
| 8 0 0 0 0 |
| 8 0 0 0 0 |
| 0 1 0 0 0 |
sum: 34

Die ursprüngliche Matrix (Zeile i , Spalte j ) gedacht als die Anzahl der Saiten werden könnte, die mit dem Symbol beginnen i und dessen nächste Symbol ist das Symbol j . Alternativ können Sie es als Anzahl von Strings der Länge sehen konnten, 2 , die mit dem Symbol beginnen i und endet mit dem Symbol j .

Die Matrixmultiplikation bewahrt diese Invarianten, also nach Potenzierung, A ^{n -1} würde die Anzahl der Zeichenfolgen enthalten, die mit dem Symbol beginnen i / em <>, Länge n und endet in Symbol j .

Siehe Wikipedia: Binäre Exponentiation für einen Algorithmus für eine schnellere Berechnung der Matrix Kräfte <. / p>

(Danke stefan.ciobaca)

Dieser Sonderfall reduziert sich auf die Formel:

  

Anzahl möglicher Zeichenfolge = f ( n ) = 4 + Σ _{K = 1 .. n} 2 ^{⌊ k -1 / ₂ ⌋} = f ( n 1) + 2 ^{⌊ n -1 / ₂ ⌋}

n       f(n)
----    ----
   1       5
   2       6
   3       8
   4      10
   5      14
   6      18
   7      26
   8      34
   9      50
  10      66

Answer 2

Wollen Sie nur wissen, wie viele Strings einer bestimmten Länge, die Sie mit den Regeln in der angegebenen Matrix aufbauen können? Wenn ja, dass ein Ansatz wie diese funktionieren soll:

n = 5
maxlen = 100

combine = [
      [0, 0, 1, 1, 0],
      [0, 0, 0, 0, 1],
      [1, 0, 0, 0, 0],
      [1, 0, 0, 0, 0],
      [0, 1, 0, 0, 0]
   ]

# counts of strings starting with 0,1,...,4, initially for strings of length one:
counts = [1, 1, 1, 1, 1]

for size in range(2, maxlen+1):
   # calculate counts for size from count for (size-1)
   newcount = []
   for next in range(n):
      total = 0
      for head in range(n):
         if combine[next][head]:
            # |next| can be before |head|, so add the counts for |head|
            total += counts[head]
      # append, so that newcount[next] == total
      newcount.append(total)
   counts = newcount
   print "length %i: %i items" % (size, sum(counts))

Answer 3

Ihr Algorithmus scheint optimal zu sein.

Wie verwenden Sie diese Permutationen? Werden Sie sie in einer Liste Akkumulieren oder mit ihm eins nach dem anderen? Da gibt es eine große Anzahl solcher Permutationen, so vielleicht die schlechte Leistung durch große Speichernutzung (wenn Sie alle von ihnen sammeln) oder es dauert nur so viel Zeit. Sie können nicht nur Milliarden von Schleifen in trivialer Zeit tun.

Auf Kommentar antworten:

Wenn Sie nur wollen, dass sie zählen, dann können Sie die dynamische Programmierung mit:

count Sei [n] [m] ein Array, in dem count [l] [j] ist die Anzahl solcher Permutationen, deren Länge L und enden mit j

dann count [l] [i] = count [l-1] [i1] + count [l-1] [i2] + ..., wobei i1, i2, ... die Ziffern sind, die können voraus i (dies kann in einem vorher berechneten Array gespeichert werden).

Jede Zelle Zahl kann durch Summieren K Zahlen gefüllt werden (K ist abhängig von der kompatibelen Matrix), so dass die Komplexität O (KMN), M ist die Länge der Permutation, und N die Gesamtzahl der Stellen.

Answer 4

Vielleicht verstehe ich das nicht, aber wäre dies nicht, indem eine Tabelle von Listen bedient werden, dass für jede Stelle eine Liste der gültigen Ziffern hat, die ihm folgen konnte.

Dann ist Ihre Routine zu generieren ein akkumuliertes Ergebnis, die stellige Zahl, und die aktuelle Ziffer nehmen. So etwas wie:

// not really Java - and you probably don't want chars, but you'll fix it
void GenerateDigits(char[] result, int currIndex, char currDigit)
{
    if (currIndex == kMaxIndex) {
        NotifyComplete(result);
        return;
    }
    char[] validFollows = GetValidFollows(currDigit); // table lookup
    foreach (char c in validFollows) {
        result[currIndex] = c;
        GenerateDigits(result, currIndex+1, c);
    }
}

Die Komplexität steigt in Abhängigkeit von der Anzahl der Ziffern zu erzeugen, aber diese Funktion ist abhängig von der Gesamtzahl der gültigen für jede eine Ziffer folgt. Wenn die Gesamtzahl der folgt der gleiche für jede Ziffer ist, sagen wir mal, k, dann ist die Zeit, um alle möglichen Permutationen zu erzeugen, wird O (k ^ n) sein, wobei n die Anzahl der Ziffern ist. Sorry, ich kann nicht Mathe ändern. Die Zeit, 10 n Stellen in der Basis zu erzeugen, ist 10 ^ n.

Answer 5

Ich bin mir nicht ganz sicher, was Sie fragen, aber da gibt es potentiell n! Permutationen einer Zeichenkette von n Ziffern, Sie gehen zu können, schreiben Sie sie nicht schneller als n !. Ich bin mir nicht ganz sicher, wie Sie glauben, eine Laufzeit von O bekam (n ^ 2).