Sequenza costretti a indice delle mappe

Question

Sono scervellarsi su come mappare un insieme di sequenze di numeri interi consecutivi.

Tutte le sequenze seguono questa regola:

A_0 = 1
A_n >= 1
A_n <= max(A_0 .. A_n-1) + 1

Sto cercando una soluzione che sarà in grado di, data una tale sequenza, calcolare un intero per fare una ricerca in una tabella e dato un indice nella tabella, generare la sequenza.

Esempio: per lunghezza 3, 5 sono le sequenze valide. Una funzione veloce per fare la seguente mappa (preferibilmente in entrambe le direzioni) sarebbe una buona soluzione

1,1,1   0
1,1,2   1
1,2,1   2
1,2,2   3
1,2,3   4

---

• Il punto dell'esercizio è quello di ottenere un tavolo compresso con un 1-1 corrispondenza tra le sequenze e le cellule validi.
• La dimensione dell'insieme in limitato solo dal numero di sequenze uniche possibili.
• Non so ora quale sarà la lunghezza della sequenza, ma sarà una piccola, <12, costanti e noti in anticipo.
• sarò arrivare a questo, prima o poi, ma anche se mi piacerebbe buttare fuori per la comunità di avere "divertimento" con nel frattempo.

---

queste sono diverse sequenze validi

1,1,2,3,2,1,4
1,1,2,3,1,2,4
1,2,3,4,5,6,7
1,1,1,1,2,3,2

questi non sono

1,2,2,4
2,
1,1,2,3,5

---

In relazione al questo

Answer 1

C'è un'indicizzazione sequenza naturale, ma non così facile da calcolare.

Let cercare a_n per n> 0, poiché A_0 = 1.

L'indicizzazione avviene in 2 fasi.

Parte 1:

sequenze Gruppo di luoghi in cui a_n = max (A_0 .. a_n-1) + 1. chiamare questi luoghi gradini .

• Nella passi sono numeri consecutivi (2,3,4,5, ...).
• non-luoghi step possiamo mettere numeri da 1 al numero di passaggi con indice minore di k.

Ciascun gruppo può essere rappresentare come stringa binaria dove 1 è passo e 0 non passo. Per esempio. 001001010 significa gruppo con 112aa3b4c, un <= 2, b <= 3, c <= 4. Perché, gruppi sono indicizzate con numero binario c'è indicizzazione naturale dei gruppi. Da 0 a 2 ^ lunghezza - 1. Consente valore richiamo del gruppo rappresentazione binaria ordine di gruppo

.

Parte 2:

Indice sequenze all'interno di un gruppo. Poiché i gruppi definiscono posizioni fasi, soltanto numeri su posizioni non-step sono variabili, e sono variabili a intervalli definiti. Con questo è facile sequenza indice del dato gruppo all'interno di quel gruppo, con ordine lessicografico di posti variabile.

E 'facile calcolare il numero di sequenze in un gruppo. E 'il numero della forma 1 ^ I_1 * 2 ^ I_2 * 3 ^ I_3 * ....

La combinazione di:

Questo dà una chiave di 2 parte: <Steps, Group> questo allora deve essere mappato ai numeri interi. Per fare questo dobbiamo trovare il numero di sequenze sono in gruppi che hanno ordine di meno che un certo valore. Per questo, lascia prima trovare il numero di sequenze sono in gruppi di data lunghezza. Che possono essere calcolati passa attraverso tutti i gruppi e numero di sequenze sommando o simile con recidiva. Sia T (l, n) numero di sequenze di lunghezza l (A_0 viene omesso) dove il valore massimo primo elemento può essere n + 1. Che tiene:

T(l,n) = n*T(l-1,n) + T(l-1,n+1)
T(1,n) = n

Poiché l + n <= sequence length + 1 esistono ~ sequence_length^2/2 (L, N) valori di T, che possono essere facilmente calcolati.

Si calcolano numero di sequenze in gruppi di ordine inferiore o uguale al valore determinato. Questo può essere fatto con sommatore del T (l, n) valori. Per esempio. numero di sequenze in gruppi con ordine <= 1001010 binaria, è uguale a

T(7,1) +         # for 1000000
2^2 * T(4,2) +   # for 001000
2^2 * 3 * T(2,3) # for 010

Ottimizzazioni:

Questo vi darà una mappatura ma l'implementazione diretta per combinare le parti fondamentali è >O(1) al meglio. D'altra parte, la Steps porzione della chiave è piccola e calcolando l'intervallo di Groups per ogni O(1) valore, una tabella di ricerca può ridurre questo a <=>.

Non sono sicuro al 100% sulla formula superiore, ma dovrebbe essere qualcosa di simile.

Con queste osservazioni e ricorrenza è possibile effettuare funzioni sequenza -> e indice -> sequenza. Ma non è così banale: -)

Answer 2

Credo hash con fuori l'ordinamento dovrebbe essere la cosa.

Come A0 inizia sempre con 0, può essere Penso che possiamo pensare alla sequenza come un numero con base 12 e utilizzare la sua base 10 come la chiave per guardare in alto. (Ancora non è sicuro di questo).

Answer 3

Questa è una funzione Python che può fare il lavoro per voi assumendo che tu abbia questi valori memorizzati in un file e si passa le linee per la funzione

def valid_lines(lines):
    for line in lines:
        line = line.split(",")
        if line[0] == 1 and line[-1] and line[-1] <= max(line)+1:
            yield line

lines = (line for line in open('/tmp/numbers.txt'))
for valid_line in valid_lines(lines):
    print valid_line

Answer 4

Data la sequenza, che avrebbe risolto, quindi utilizzare l'hash della sequenza ordinata come l'indice della tabella.