Trovare l'indice di una data permutazione

Question

Sto leggendo i numeri 0, 1, ..., (N - 1) uno per uno in un certo ordine. Il mio obiettivo è trovare l'indice di lessicografia di questa data permutazione, usando solo lo spazio O(1).

Questa domanda è stata posta prima, ma tutti gli algoritmi che ho trovato utilizzavano lo spazio O(N). Sto iniziando a pensare che non è possibile. Ma mi aiuterebbe molto a ridurre il numero di allocazioni.

Answer 1

Considerando i seguenti dati:

chars = [a, b, c, d] 
perm = [c, d, a, b] 
ids = get_indexes(perm, chars) = [2, 3, 0, 1] 

Una possibile soluzione per permutazione con ripetizioni va come segue:

len = length(perm)   (len = 4) 
num_chars = length(chars) (len = 4) 

base = num_chars^len  (base = 4^4 = 256) 
base = base/len   (base = 256/4 = 64) 

id = base * ids[0]   (id = 64 * 2 = 128) 
base = base/len   (base = 64/4 = 16) 

id = id + (base * ids[1]) (id = 128 + (16 * 3) = 176) 
base = base/len   (base = 16/4 = 4) 

id = id + (base * ids[2]) (id = 176 + (4 * 0) = 176) 
base = base/len   (base = 4/4 = 1) 

id = id + (base * ids[3]) (id = 176 + (1 * 1) = 177) 

processo inverso:

id = 177 
(id/(4^3)) % 4 = (177/64) % 4 = 2 % 4 = 2 -> chars[2] -> c 
(id/(4^2)) % 4 = (177/16) % 4 = 11 % 4 = 3 -> chars[3] -> d 
(id/(4^1)) % 4 = (177/4) % 4 = 44 % 4 = 0 -> chars[0] -> a 
(id/(4^0)) % 4 = (177/1) % 4 = 177 % 4 = 1 -> chars[1] -> b 

Il numero di possibili le permutazioni sono date da num_chars^num_perm_digits, con num_chars come numero di possibili caratteri e num_perm_digits come numero di cifre in una permutazione.

Ciò richiede O(1) nello spazio, considerando l'elenco iniziale come un costo costante; e richiede O(N) in tempo, considerando N come il numero di cifre della tua permutazione.

Sulla base dei punti di cui sopra, si può fare:

function identify_permutation(perm, chars) { 

    for (i = 0; i < length(perm); i++) { 
     ids[i] = get_index(perm[i], chars); 
    } 

    len = length(perm); 
    num_chars = length(chars); 

    index = 0; 
    base = num_chars^len - 1; 
    for (i = 0; i < length(perm); i++) { 
     index += base * ids[i]; 
     base = base/len; 
    } 

} 

E 'una pseudocodice, ma è anche abbastanza facile da convertire in qualsiasi lingua (:!.

Answer 2

ci sono N permutazioni Per rappresentare indice è necessario almeno N bit

Answer 3

Ecco un modo per farlo se si vuole assumere che le operazioni aritmetiche sono tempo costante:.

def permutationIndex(numbers): 
    n=len(numbers) 
    result=0 
    j=0 
    while j<n: 
    # Determine factor, which is the number of possible permutations of 
    # the remaining digits. 
    i=1 
    factor=1 
    while i<n-j: 
     factor*=i 
     i+=1 
    i=0 
    # Determine index, which is how many previous digits there were at 
    # the current position. 
    index=numbers[j] 
    while i<j: 
     # Only the digits that weren't used so far are valid choices, so 
     # the index gets reduced if the number at the current position 
     # is greater than one of the previous digits. 
     if numbers[i]<numbers[j]: 
     index-=1 
     i+=1 
    # Update the result. 
    result+=index*factor 
    j+=1 
    return result 

Ho scritto appositamente alcuni calcoli che potrebbero essere fatti più semplicemente usando alcune operazioni built-in Python, ma volevo rendere più ovvio che non si usasse spazio extra non costante.

Come osservato maxim1000, il numero di bit necessari per rappresentare il risultato crescerà rapidamente al crescere di n, quindi saranno necessari infine grandi numeri interi, che non hanno più tempo costante l'aritmetica, ma credo che questo codice si rivolge lo spirito di la tua domanda.

Answer 4

Se stai cercando un modo per ottenere l'indice lessicografico o il rango di una combinazione unica invece di una permutazione, allora il tuo problema rientra nel coefficiente binomiale. Il coefficiente binomiale gestisce i problemi di scelta di combinazioni uniche in gruppi di K con un totale di N elementi.

Ho scritto una classe in C# per gestire le funzioni comuni per lavorare con il coefficiente binomiale. Esso svolge i seguenti compiti:

1. Uscite tutti i K-indici in un bel formato per qualsiasi N scegliere K in un file. Gli indici K possono essere sostituiti con stringhe o lettere più descrittive.

2. Converte gli indici K nell'indice lessicografico corretto o nella classificazione di una voce nella tabella del coefficiente binomiale ordinato. Questa tecnica è molto più veloce delle vecchie tecniche pubblicate che fanno affidamento sull'iterazione. Lo fa usando una proprietà matematica inerente al triangolo di Pascal ed è molto efficiente rispetto all'iterazione sul set.

3. Converte l'indice in una tabella di coefficiente binomiale ordinata negli indici K corrispondenti. Credo che sia anche più veloce delle vecchie soluzioni iterative.

4. Utilizza il metodo Mark Dominus per calcolare il coefficiente binomiale, che è molto meno probabile che si verifichi un overflow e funzioni con numeri più grandi.

5. La classe è scritta in .NET C# e offre un modo per gestire gli oggetti correlati al problema (se presenti) utilizzando un elenco generico. Il costruttore di questa classe prende un valore bool chiamato InitTable che quando true creerà un elenco generico per contenere gli oggetti da gestire. Se questo valore è falso, non creerà la tabella. Non è necessario creare la tabella per utilizzare i 4 metodi precedenti. I metodi di accesso sono forniti per accedere alla tabella.

6. Esiste una classe di test associata che mostra come utilizzare la classe e i suoi metodi. È stato ampiamente testato con 2 casi e non ci sono bug noti.

Per leggere su questa classe e scaricare il codice, vedere Tablizing The Binomial Coeffieicent.

Il codice testato seguente sarà Sperimenta ogni combinazioni uniche:

public void Test10Choose5() 
{ 
    String S; 
    int Loop; 
    int N = 10; // Total number of elements in the set. 
    int K = 5; // Total number of elements in each group. 
    // Create the bin coeff object required to get all 
    // the combos for this N choose K combination. 
    BinCoeff<int> BC = new BinCoeff<int>(N, K, false); 
    int NumCombos = BinCoeff<int>.GetBinCoeff(N, K); 
    // The Kindexes array specifies the indexes for a lexigraphic element. 
    int[] KIndexes = new int[K]; 
    StringBuilder SB = new StringBuilder(); 
    // Loop thru all the combinations for this N choose K case. 
    for (int Combo = 0; Combo < NumCombos; Combo++) 
    { 
     // Get the k-indexes for this combination. 
     BC.GetKIndexes(Combo, KIndexes); 
     // Verify that the Kindexes returned can be used to retrive the 
     // rank or lexigraphic order of the KIndexes in the table. 
     int Val = BC.GetIndex(true, KIndexes); 
     if (Val != Combo) 
     { 
     S = "Val of " + Val.ToString() + " != Combo Value of " + Combo.ToString(); 
     Console.WriteLine(S); 
     } 
     SB.Remove(0, SB.Length); 
     for (Loop = 0; Loop < K; Loop++) 
     { 
     SB.Append(KIndexes[Loop].ToString()); 
     if (Loop < K - 1) 
      SB.Append(" "); 
     } 
     S = "KIndexes = " + SB.ToString(); 
     Console.WriteLine(S); 
    } 
} 

si dovrebbe essere in grado di porto questa classe nel corso abbastanza facilmente alla lingua di vostra scelta. Probabilmente non dovrai eseguire il porting sulla parte generica della classe per raggiungere i tuoi obiettivi. A seconda del numero di combinazioni con cui stai lavorando, potresti dover usare una parola più grande di 4 byte.

Answer 5

C'è una soluzione java a questo problema su geekviewpoint. Ha una buona spiegazione del perché è vero e il codice è facile da seguire. http://www.geekviewpoint.com/java/numbers/permutation_index. Ha anche un test unitario che esegue il codice con diversi input.

Answer 6

nulla di realmente nuovo nell'idea, ma un metodo completamente matriciale, senza ciclo esplicito o ricorsione (usando Numpy ma facile da adattare):

import numpy as np 
import math 
vfact = np.vectorize(math.factorial, otypes='O') 

def perm_index(p): 
    return np.dot(vfact(range(len(p)-1, -1, -1)), 
        p-np.sum(np.triu(p>np.vstack(p)), axis=0)) 

Answer 7

ho appena scritto un codice utilizzando Visual Basic e il mio programma può direttamente calcola ogni indice o ogni permutazione corrispondente a un dato indice fino a 17 elementi (questo limite è dovuto all'approssimazione della notazione scientifica dei numeri superiori a 17! del mio compilatore).

Se sei interessato posso inviare il programma o pubblicarlo da qualche parte per il download. Funziona bene e può essere utile per testare e confrontare l'output dei tuoi codici.

Ho usato il metodo di James D. McCaffrey chiamato factoradic e potete leggere a riguardo lo here e qualcosa anche here (nella discussione alla fine della pagina).