Algoritmo per creare permutazioni per un dato alfabeto basato su un numero di sequenza

Question

Algoritmo per creare permutazioni per un dato alfabeto basato su un numero di sequenza

#1 da (1 voti)

1

Mi piacerebbe avere una funzione che creerà una parola (sempre la stessa parola) per un dato numero di sequenza basato su un dato alfabeto.

word(0, [a,b,c]) = a
word(1, [a,b,c]) = b
word(2, [a,b,c]) = c
word(3, [a,b,c]) = aa
word(4, [a,b,c]) = ab
word(5, [a,b,c]) = ac
word(6, [a,b,c]) = ba
word(7, [a,b,c]) = bb
word(8, [a,b,c]) = bc
word(9, [a,b,c]) = ca
...

Sono riuscito a creare ricorsivamente tutte le permutazioni di una determinata lunghezza, ma a partire dalla lunghezza 5 la memoria diventa già abbastanza grande.

runtime algorithms strings

posta OliverS 02.05.2014 - 14:38

fonte

1 risposta

Leggi altre domande sui tag runtime algorithms strings

Utilizzo di JDBC per leggere in modo asincrono una tabella Oracle di grandi dimensioni Iniezione delle dipendenze per le variabili di richiesta in un'applicazione web

score 1 · Accepted Answer

Sia n la dimensione dell'alfabeto (qui 3).

Ora il numero di ath nello schema sopra si trova tra

0 < = a < n o 0 + n < = a < 0 + n + n * n o ...

0 + n + n ^ 2 + ... + n ^ m < = a < 0 + n + n ^ 2 + ... + n ^ (m + 1)

Risoluzione per m,

m = int (log (a (n-1) / n + 1) / log (n))

Eccolo,

m = int (log (2 * a / 3 + 1) / log (3))

Ora sottraiamo n * (n ^ m-1) / (n-1) da un ottenere b. b sarà un numero di (m + 1) posti in un sistema numerico con radix n.

Ho messo un piccolo codice Python per questo in questo modo:

from math import*

f = lambda a : int(log(2*a/3.0 + 1.0)/ log(3))

alpha = ['a','b','c']


def get_repr(a):
    m = f(a)
    if m == 0:
        b = a
    else:
        trunc = 3*((3**m)-1)/(2)
        b = a - trunc
    s = ''
    for q in range(0, m+1):
        s =   alpha[(b%3)] + s
        b /= 3
    return s


print get_repr(8)

EDIT: possiamo evitare il gergo del logaritmo e tutto il resto, e possiamo usare quanto segue:

def word(a, alphabet):
    k = 1
    N = len(alphabet)
    n = N
    while True:
        if a < n:
            break
        else:
            a = a - n
            n = n*N
            k = k + 1
    s = ''
    for q in range(0, k):
        s =   alphabet[(a%N)] + s
        a /= N
    return s


print word(1, ['a','b','c'])