Su tupla de pedidos es lexicográfica y su a-ser-calcula la posición
está basada en uno, como son el símbolo de los códigos de a,b,\ldots utilizado en @joriki la respuesta;
pero por el bien de la simplicidad voy a utilizar inversa orden lexicográfico
y a partir de cero posiciones y códigos de letra.
La conversión se realiza mediante la sustitución de @joriki (i_1,\ldots,i_k)
con (n-i_k,\ldots,n-i_1)
y la sustitución de la posición resultante de la fórmula con su distancia a
\binom{n}{k}.
El resultado es, pues, coherente con @joriki de la fórmula.
He utilizado tales cálculos para la compresión de multi-índices
en (inclinada)simétrica tensores; por lo tanto, voy a tomar un poco de vocabulario a partir de que
dominio.
Vamos a definir un k-índice de estar
un k-tupla de estrictamente creciente de números enteros no negativos.
Usted puede tener que ordenar en consecuencia y a no permitir entradas duplicadas.
k-índices puede ser totalmente ordenado en sentido inverso-lexicográfica manera:
La ordenación se realiza por el último elemento,
en caso de igualdad, por el siguiente al último elemento, y así sucesivamente.
Para un k-índice de I, vamos a definir su posición (o índice comprimido)
\operatorname{ordx}(I) como el número de k-índices
inversa-lexicográficamente menor que I.
Tenga en cuenta que \operatorname{ordx}(I) = 0
para los más pequeños k-índice de I=(0,\ldots,k-1).
Necesitamos una notación para trunca tuplas.
Denotando I = (i_0,\ldots,i_{k-1}),
deje I_m = (i_0,\ldots,i_{k-m-1}) por enterom0\leq m<k.
Que es I con la última m elementos cortados.
Ahora un k-índice de J=(j_0,\ldots,j_{k-1}) es
inversa-lexicográficamente menor que I si y sólo si
- j_{k-1} < i_{k-1};
hay \binom{i_{k-1}}{k} tales k-índices; o
- k>1, e j_{k-1} = i_{k-1},
y J_1 es inversa lexicográficamente menor que I_1.
Esta condición implica una comparación de (k-1)-índices.
Procediendo por inducción, llegamos a la fórmula
\operatorname{ordx}(I) = \sum_{r=1}^k\binom{i_{r-1}}{r}
It is worth noting that this formula does not depend on the upper bound n
para el índice de los elementos.
El coeficiente binomial valores pueden calcularse sobre la marcha
mediante la inicialización y actualización de un segmento del triángulo de Pascal.
Definir
b_{j}^{(r)} = \binom{j+r}{r} = \begin{cases}
1 & \text{if %#%#% or %#%#%} \\
b_{j}^{(r-1)} + b_{j-1}^{(r)} & \text{if %#%#% and %#%#%}
\end{casos}
Tan sólo tenemos que inicializar y actualización de una matriz
r=0
En la práctica, se antepone un j=0 a la matriz en orden a la cuenta
para el caso de r>0$ que requiere un cero coeficiente binomial.
En Python (que utiliza índices con base cero y semi-abierta rangos):
def ordx(idx):
"""
Turns a multi-index of strictly increasing nonnegative integers
into a 1-dimensional zero-based index.
"""
s = 0
b = [0] + [1] * (idx[-1] + 1 - len(idx)) # [0, 1, 1, ...]
for r,i in enumerate(idx): # (0,idx[0]), (1,idx[1]), ...
for j in xrange(2, len(b)): # 2, ..., len(b)-1
b[j] += b[j-1] # binomial(j+r, r+1)
s += b[i - r]
return s
Además:
Si desea permitir duplicar tupla de elementos, se puede transformar en que
problema al añadir a cada elemento de a j>0 el sub-índice de $$B^{(r)} = \left(b_0^{(r)},\ldots,b_{i_{k-1}-k}^{(r)}\right)$ y
computación ordx para la modificación de la tupla que ahora tiene estrictas incrementos.
Para ese caso de uso, el código anterior se obtiene simplificado un poco:
def ords(idx):
"""
Turns a multi-index of nondecreasing nonnegative integers
into a 1-dimensional zero-based index.
"""
s = 0
b = [0] + [1] * idx[-1] # [0, 1, 1, ..., 1]
for i in idx:
for j in xrange(2, len(b)): # 2, ..., len(b)-1 = idx[-1]
b[j] += b[j-1]
s += b[i]
return s
Este calcula
0$
Una función de este tipo ords podría ser utilizado para la compresión de un criterio de multi-índice
totalmente simétrica tensores a un plano índice que elimina la redundancia.
Actualización:
Los algoritmos anteriores son simples, pero la necesidad de actualizar una matriz de binomio
los coeficientes para cada elemento de índice.
En consecuencia, la ejecución de la anterior ords necesidades i_{r-1} = r-1 adiciones
y una matriz b de duración i_r.
Para ordx reemplacer$$\operatorname{ords}(I) = \sum_{r=0}^{k-1}\binom{i_r + r}{r+1}$.
Se puede reducir el recuento de operación y uso de memoria de computación
cada uno necesita coeficiente binomial directamente de la anterior.
Esto requiere de una secuencia de multiplicaciones y divisiones en lugar
de sólo agregados, pero se reduce el binomio de la contabilidad a una variable escalar
y mantiene total ords de recuento de operación en k\,i_{k-1}.
En consecuencia, ordx operación recuento i_{k-1}+1.
Aquí es una muestra de Python implementación de la optimización de la i_{k-1}
(con // que denota la división entera):
def ordx_opt(idx):
"""
Turns a multi-index of strictly increasing nonnegative integers
into a 1-dimensional zero-based index.
"""
s = 0
j = 1
b = 1
for r,i in enumerate(idx): # (0,idx[0]), (1,idx[1]), ...
if i == r: continue # skipping terms with zero binomial coeff
# b == binomial(j+r-1, r), update to j == i - r
while j < i - r:
b *= j + r
b //= j
j += 1
# b == binomial(i-1, r), update to binomial(i, r+1)
b *= i
b //= r + 1
s += b
return s
Y la correspondiente optimizado i_{k-1}-k+1:
def ords_opt(idx):
"""
Turns a multi-index of nondecreasing nonnegative integers
into a 1-dimensional zero-based index.
"""
s = 0
j = 1
b = 1
for r,i in enumerate(idx):
if i == 0: continue # skipping terms with zero binomial coeff
# b == binomial(j+r-1, r), update to j == i
while j < i:
b *= j + r
b //= j
j += 1
# b == binomial(i+r-1, r), update to binomial(i+r, r+1)
b *= i + r
b //= r + 1
s += b
return s
