Come calcolare le permutazioni in tempo lineare, con una svolta

Question

Ho un problema di pianificazione delle risorse in Java in cui le cose devono essere sequenziate, ma ci sono restrizioni su quali risorse possono essere una accanto all'altra. Una buona analogia è una stringa di & Quot; cifre & Quot ;, in cui solo determinate cifre possono essere una accanto all'altra. La mia soluzione era ricorsiva e funziona bene per stringhe di piccole dimensioni, ma il tempo di esecuzione è O (X ^ N), dove X è il numero di cifre possibili (la base) e N è la lunghezza della stringa. Diventa rapidamente ingestibile.

Utilizzando la matrice di compatibilità di seguito, ecco alcuni esempi di stringhe consentite
Lunghezza di 1: 0, 1, 2, 3, 4
Lunghezza di 2: 02, 03, 14, 20, 30, 41
Lunghezza di 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

La mia soluzione per contare tutte le stringhe di lunghezza N era iniziare con una stringa vuota, permutare la prima cifra ed effettuare una chiamata ricorsiva per tutte le stringhe di lunghezza N-1. Le chiamate ricorsive controllano l'ultima cifra che è stata aggiunta e provano tutte le permutazioni che possono essere accanto a quella cifra. Sono state apportate alcune ottimizzazioni in modo che non provi e permuti ogni volta 00, 01, 04, ad esempio - solo 02, 03, ma le prestazioni sono ancora scarse in quanto scalano dalla base 5 (l'esempio) alla base 4000.

Qualche idea su un modo migliore per contare le permutazioni oltre a provare a elencarle tutte?

Answer 1

Se vuoi solo il numero di stringhe di una certa lunghezza, potresti semplicemente moltiplicare la matrice di compatibilità con se stessa alcune volte e sommare i suoi valori.

  

n = lunghezza della stringa
   A = matrice di compatibilità
   numero di stringhe possibili = somma di A^n-1

Alcuni esempi:

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

La matrice originale (riga i , colonna j ) potrebbe essere considerata come il numero di stringhe che iniziano con il simbolo i e il cui simbolo successivo è il simbolo j . In alternativa, potresti vederlo come numero di stringhe di lunghezza 2 , che iniziano con il simbolo i e terminano con il simbolo j .

La moltiplicazione di matrici preserva questo invariante, quindi dopo l'espiazione, A ^{n -1} conterrebbe il numero di stringhe che iniziano con il simbolo i , ha lunghezza n e termina con il simbolo j .

Vedi Wikipedia: esponenziazione mediante quadratura per un algoritmo per un calcolo più veloce dei poteri della matrice.

/ p>

(Grazie stefan.ciobaca)

Questo caso specifico si riduce alla formula:

  

numero di stringhe possibili = f ( n ) = 4 + Σ _{k =1..n} 2 ^{& # 8970; k -1 & # 8260; ₂ & # 8971;} = f ( n -1) + 2 ^{& # 8970; n -1 # 8260 &; ₂ # 8971 &;}

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

Vuoi solo sapere quante stringhe di una determinata lunghezza puoi costruire con le regole nella matrice data? In tal caso, un approccio come questo dovrebbe funzionare:

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

Il tuo algoritmo sembra essere ottimale.

Come stai usando queste permutazioni? Li stai accumulando in un elenco o lo usi uno per uno? Dal momento che esiste un numero enorme di tali permutazioni, quindi le scarse prestazioni potrebbero essere dovute all'utilizzo della memoria di grandi dimensioni (se si stanno raccogliendo tutte) o richiede solo così tanto tempo. Non puoi fare miliardi di loop in tempi banali.

Rispondi al commento:

Se vuoi solo contarli, puoi usare la programmazione dinamica:

Sia count [n] [m] un array, dove count [l] [j] è il numero di tali permutazioni la cui lunghezza è l e termina con j,

quindi count [l] [i] = count [l-1] [i1] + count [l-1] [i2] + ..., dove i1, i2, ... sono le cifre che possono precedere i (questo può essere salvato in un array precalcolato).

Ogni cella di conteggio può essere riempita sommando i numeri K (K dipende dalla matrice compatibile), quindi la complessità è O (KMN), M è la lunghezza della permutazione e N è il numero totale di cifre.

/ p>

Answer 4

Forse non lo capisco, ma questo non sarebbe servito da una tabella di elenchi che per ogni cifra ha un elenco di cifre valide che potrebbero seguirlo.

Quindi la tua routine da generare prenderà un risultato accumulato, il numero della cifra e la cifra corrente. Qualcosa del tipo:

// 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);
    }
}

La complessità aumenta in funzione del numero di cifre da generare, ma tale funzione dipende dal numero totale di follow validi per ogni cifra. Se il numero totale di follow è lo stesso per ogni cifra, diciamo, k, allora il tempo per generare tutte le possibili permutazioni sarà O (k ^ n) dove n è il numero di cifre. Scusa, non posso cambiare la matematica. Il tempo per generare n cifre nella base 10 è 10 ^ n.

Answer 5

Non sono esattamente sicuro di quello che stai chiedendo, ma dal momento che potenzialmente ci sono n! permutazioni di una stringa di n cifre, non sarai in grado di elencarle più velocemente di n !. Non sono esattamente sicuro di come pensi di avere un runtime di O (n ^ 2).