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 entero$m$$0\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 reemplace$r$$$\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
