para describir una permutación de n elementos, se ve que para la posición de que el primer elemento termina en, usted tiene n posibilidades, para que pueda describir esto con un número entre 0 y n-1. Para la posición en la que termina el próximo elemento, tiene n-1 posibilidades restantes, por lo que puede describir esto con un número entre 0 y n-2.
Etcétera hasta que tenga n números.
Como un ejemplo para n = 5, considere la permutación que trae abcde a caebd.
a, el primer elemento, termina en la segunda posición, por lo que lo asignamos índice .b termina en la cuarta posición, que sería el índice 3, pero es el tercero restante, por lo que le asignamos .c termina en la primera posición restante, que siempre es .d termina en la última posición restante, que (de las dos únicas posiciones restantes) es .e termina en la única posición restante, indexada en .
Así que tienen la secuencia índice {1, 2, 0, 1, 0}.
Ahora sabe que, por ejemplo, en un número binario, 'xyz' significa z + 2y + 4x. Para un número decimal,
es z + 10y + 100x. Cada dígito se multiplica por un poco de peso, y los resultados se suman. El patrón obvio en el peso es, por supuesto, que el peso es w = b^k, con b la base del número yk el índice del dígito. (Siempre voy a contar dígitos de la derecha y empezando en el índice 0 para el dígito más a la derecha. De la misma manera, cuando hablo de la 'primera' dígitos me refiero a la derecha.)
El razón por qué los pesos para los dígitos siguen este el patrón es que el número más alto que se puede representar con los dígitos de 0 a k debe ser exactamente 1 más bajo que el número más bajo que se puede representar usando solo el dígito k + 1. En binario, 0111 debe ser uno más bajo que 1000. En decimal, 099999 debe ser uno más bajo que 100000.
de codificación a la variable-base
El espaciamiento entre los números subsiguientes siendo exactamente 1 es la regla importante. Al darnos cuenta de esto, podemos representar nuestra secuencia de índice mediante un número de base variable . La base para cada dígito es la cantidad de diferentes posibilidades para ese dígito. Para el decimal cada dígito tiene 10 posibilidades, para nuestro sistema el dígito más a la derecha tendría 1 posibilidad y el más a la izquierda tendrá n posibilidades. Pero como el dígito más a la derecha (el último número en nuestra secuencia) siempre es 0, lo dejamos afuera. Eso significa que nos quedan las bases 2 a n. En general, el dígito k'th tendrá la base b [k] = k + 2. El valor más alto permitido para el dígito k es h [k] = b [k] - 1 = k + 1.
Nuestra regla sobre los pesos w [k] de dígitos requiere que la suma de h [i] * w [i], donde i va de i = 0 a i = k, sea igual a 1 * w [k + 1]. Dicho de forma recurrente, w [k + 1] = w [k] + h [k] * w [k] = w [k] * (h [k] + 1). El primer peso w [0] debe ser siempre 1. A partir de ahí, tenemos los siguientes valores:
k h[k] w[k]
0 1 1
1 2 2
2 3 6
3 4 24
... ... ...
n-1 n n!
(la relación general w [k-1] = k se prueba fácilmente por inducción!.)
El número que obtengamos de la conversión de nuestra secuencia será entonces la suma de s [k] * w [k], con k funcionando de 0 a n-1. Aquí s [k] es el elemento k'th (más a la derecha, comenzando en 0) de la secuencia. Como ejemplo, tome nuestro {1, 2, 0, 1, 0}, con el elemento más a la derecha eliminado como se mencionó anteriormente: {1, 2, 0, 1}. Nuestra suma es 1 * 1 + 0 * 2 + 2 * 6 + 1 * 24 = .
Tenga en cuenta que si tomamos la posición máxima para cada índice, tendríamos {4, 3, 2, 1, 0}, y eso se convierte en 119. Como los pesos en nuestra codificación numérica fueron elegidos para que podamos no omita ningún número, todos los números del 0 al 119 son válidos. ¡Son precisamente 120 de estos, que es n! para n = 5 en nuestro ejemplo, precisamente el número de permutaciones diferentes.Para que pueda ver nuestros números codificados, especifique por completo todas las permutaciones posibles.
Decodificación de la variable-base
de decodificación es similar a la conversión a binario o decimal. El algoritmo común es la siguiente:
int number = 42;
int base = 2;
int[] bits = new int[n];
for (int k = 0; k < bits.Length; k++)
{
bits[k] = number % base;
number = number/base;
}
Para nuestro número variable de bases:
int n = 5;
int number = 37;
int[] sequence = new int[n - 1];
int base = 2;
for (int k = 0; k < sequence.Length; k++)
{
sequence[k] = number % base;
number = number/base;
base++; // b[k+1] = b[k] + 1
}
Este decodifica correctamente nuestro 37 de vuelta a {1, 2, 0, 1} (sequence habría {1, 0, 2, 1} en este ejemplo de código, pero lo que sea ... siempre que indexe adecuadamente). Solo necesitamos agregar 0 en el extremo derecho (recuerde que el último elemento siempre tiene una sola posibilidad para su nueva posición) para recuperar nuestra secuencia original {1, 2, 0, 1, 0}.
permutando una lista utilizando una secuencia de índice de
Se puede utilizar el siguiente algoritmo para permutar una lista de acuerdo con una secuencia de índice específico. Es un algoritmo O (n²), desafortunadamente.
int n = 5;
int[] sequence = new int[] { 1, 2, 0, 1, 0 };
char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];
bool[] set = new bool[n];
for (int i = 0; i < n; i++)
{
int s = sequence[i];
int remainingPosition = 0;
int index;
// Find the s'th position in the permuted list that has not been set yet.
for (index = 0; index < n; index++)
{
if (!set[index])
{
if (remainingPosition == s)
break;
remainingPosition++;
}
}
permuted[index] = list[i];
set[index] = true;
}
representación común de permutaciones
Normalmente no representaría una permutación como unintuitively como lo hemos hecho, sino simplemente por la posición absoluta de cada elemento después de aplicar la permutación. Nuestro ejemplo {1, 2, 0, 1, 0} para abcde a caebd se representa normalmente por {1, 3, 0, 4, 2}. Cada índice de 0 a 4 (o en general, de 0 a n-1) ocurre exactamente una vez en esta representación.
La aplicación de una permutación en esta forma es fácil:
int[] permutation = new int[] { 1, 3, 0, 4, 2 };
char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];
for (int i = 0; i < n; i++)
{
permuted[permutation[i]] = list[i];
}
Invertir es muy similar:
for (int i = 0; i < n; i++)
{
list[i] = permuted[permutation[i]];
}
La conversión de nuestra representación a la representación común
Tenga en cuenta que si tomamos nuestro algoritmo para permutar una lista usando nuestra secuencia de índice, y aplicarla a la permutación de identidad {0, 1, 2, ..., n-1}, obtenemos el inverso permutación, representada en la forma común. ({2, 0, 4, 1, 3} en nuestro ejemplo).
Para obtener la pre-mutación no invertida, aplicamos el algoritmo de permutación que acaba de aparecer:
int[] identity = new int[] { 0, 1, 2, 3, 4 };
int[] inverted = { 2, 0, 4, 1, 3 };
int[] normal = new int[n];
for (int i = 0; i < n; i++)
{
normal[identity[i]] = list[i];
}
O puede simplemente aplicar la permutación directamente, utilizando el algoritmo de permutación inversa:
char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];
int[] inverted = { 2, 0, 4, 1, 3 };
for (int i = 0; i < n; i++)
{
permuted[i] = list[inverted[i]];
}
Tenga en cuenta que todos los algoritmos para tratar las permutaciones en la forma común son O (n), mientras que la aplicación de una permutación en nuestra forma es O (n²). Si necesita aplicar una permutación varias veces, primero conviértala a la representación común.
Aunque el algoritmo que se muestra a continuación es muy completo, señala correctamente que el algoritmo más rápido es una tabla de búsqueda. Realmente no estás hablando de "mucha" memoria, aunque, por supuesto, depende de tu sistema y plataforma. Pero si una tabla de búsqueda será suficiente, y si esta es una aplicación real, úsala. Rápido y simple! –
Usted dice eso, pero n no tiene que ser muy grande para que sea tonto. Para 12 elementos, 12! es 479,001,600 permutaciones. ¡Esa es una gran tabla de búsqueda! – ijw