php - concepto - combinatoria

Encontrar n-ésima permutación sin computar a los demás

Question

Dado un conjunto de N elementos que representan los átomos de permutación, ¿existe un algoritmo como ese?

function getNthPermutation( $atoms, $permutation_index, $size )

donde $atoms es la matriz de elementos, $permutation_index es el índice de la permutación y $size es el tamaño de la permutación.

Por ejemplo:

$atoms = array( ''A'', ''B'', ''C'' );
// getting third permutation of 2 elements
$perm = getNthPermutation( $atoms, 3, 2 );
echo implode( '', '', $perm )."/n";

Imprimiría:

B, A

¿Sin calcular cada permutación hasta $ permutation_index?

Escuché algo acerca de las permutaciones factoradic, pero cada implementación que he encontrado da como resultado una permutación con el mismo tamaño de V, que no es mi caso.

Gracias.

Answer 1

Aquí hay un algoritmo para convertir permutaciones y rangos en tiempo lineal. Sin embargo, el ranking que usa no es lexicográfico. Es extraño, pero consistente. Voy a dar dos funciones, una que se convierte de un rango a una permutación, y otra que hace lo contrario.

Primero, para unrank (ir de rango a permutación)

Initialize:
n = length(permutation)
r = desired rank
p = identity permutation of n elements [0, 1, ..., n]
unrank(n, r, p)
if n > 0 then
swap(p[n-1], p[r mod n])
unrank(n-1, floor(r/n), p)
fi
end

A continuación, para clasificar:

Initialize:
p = input permutation
q = inverse input permutation (in linear time, q[p[i]] = i for 0 <= i < n)
n = length(p)
rank(n, p, q)
if n=1 then return 0 fi
s = p[n-1]
swap(p[n-1], p[q[n-1]])
swap(q[s], q[n-1])
return s + n * rank(n-1, p, q)
end

El tiempo de ejecución de ambos es O (n).

Hay un documento agradable y legible que explica por qué esto funciona: clasificación y cambio de permutaciones en tiempo lineal, por Myrvold & Ruskey, Information Processing Letters Volumen 79, edición 6, 30 de septiembre de 2001, páginas 281-284.

http://webhome.cs.uvic.ca/~ruskey/Publications/RankPerm/MyrvoldRuskey.pdf

Answer 2

Aquí hay una solución corta y muy rápida (lineal en el número de elementos) en python, que funciona para cualquier lista de elementos (las 13 primeras letras en el siguiente ejemplo):

from math import factorial
def nthPerm(n,elems):#with n from 0
if(len(elems) == 1):
return elems[0]
sizeGroup = factorial(len(elems)-1)
q,r = divmod(n,sizeGroup)
v = elems[q]
elems.remove(v)
return v + ", " + ithPerm(r,elems)

Ejemplos:

letters = [''a'',''b'',''c'',''d'',''e'',''f'',''g'',''h'',''i'',''j'',''k'',''l'',''m'']
ithPerm(0,letters[:]) #--> a, b, c, d, e, f, g, h, i, j, k, l, m
ithPerm(4,letters[:]) #--> a, b, c, d, e, f, g, h, i, j, m, k, l
ithPerm(3587542868,letters[:]) #--> h, f, l, i, c, k, a, e, g, m, d, b, j

Nota: doy letters[:] (una copia de letters ) y no letras porque la función modifica su parámetro elems (elimina el elemento elegido)

Answer 3

Aquí hay una solución que permite seleccionar el tamaño de la permutación. Por ejemplo, además de poder generar todas las permutaciones de 10 elementos, puede generar permutaciones de pares entre 10 elementos. También permute listas de objetos arbitrarios, no solo enteros.

Esto es PHP, pero también hay JavaScript y la impedancia de Haskell .

function nth_permutation($atoms, $index, $size) {
for ($i = 0; $i < $size; $i++) {
$item = $index % count($atoms);
$index = floor($index / count($atoms));
$result[] = $atoms[$item];
array_splice($atoms, $item, 1);
}
return $result;
}

Ejemplo de uso:

for ($i = 0; $i < 6; $i++) {
print_r(nth_permutation([''A'', ''B'', ''C''], $i, 2));
}
// => AB, BA, CA, AC, BC, CB

¿Como funciona?

Hay una idea muy interesante detrás de esto. Tomemos la lista A, B, C, D Podemos construir una permutación dibujando elementos como desde una baraja de cartas. Inicialmente podemos dibujar uno de los cuatro elementos. Luego, uno de los tres elementos restantes, y así sucesivamente, hasta que finalmente no nos quede nada.

Aquí hay una posible secuencia de elecciones. Comenzando desde arriba, tomamos el tercer camino, luego el primero, el segundo y finalmente el primero. Y esa es nuestra permutación # 13.

Piensa cómo, dada esta secuencia de elecciones, llegarías al número trece algorítmicamente. A continuación, invierta su algoritmo, y así es como puede reconstruir la secuencia a partir de un número entero.

Tratemos de encontrar un esquema general para empaquetar una secuencia de elecciones en un entero sin redundancia, y desempaquetarlo nuevamente.

Un esquema interesante se llama sistema de números decimales. Se puede pensar que "27" elige la ruta # 2 de 10, y luego elige la ruta # 7 de 10.

Pero cada dígito solo puede codificar elecciones de 10 alternativas. Otros sistemas que tienen una base fija, como binaria y hexadecimal, también solo pueden codificar secuencias de opciones a partir de un número fijo de alternativas. Queremos un sistema con una base variable, tipo de unidades de tiempo, "14:05:29" es la hora 14 de 24, el minuto 5 de 60, el segundo 29 de 60.

¿Qué pasa si tomamos las funciones genéricas de número a cadena y de cadena a número y las engañamos para que usen radix mixtas? En lugar de tomar una sola raíz, como parseInt (''beef'', 16) y (48879).toString(16) , tomarán una base por cada dígito.

function pack(digits, radixes) {
var n = 0;
for (var i = 0; i < digits.length; i++) {
n = n * radixes[i] + digits[i];
}
return n;
}
function unpack(n, radixes) {
var digits = [];
for (var i = radixes.length - 1; i >= 0; i--) {
digits.unshift(n % radixes[i]);
n = Math.floor(n / radixes[i]);
}
return digits;
}

¿Eso incluso funciona?

// Decimal system
pack([4, 2], [10, 10]); // => 42
// Binary system
pack([1, 0, 1, 0, 1, 0], [2, 2, 2, 2, 2, 2]); // => 42
// Factorial system
pack([1, 3, 0, 0, 0], [5, 4, 3, 2, 1]); // => 42

Y ahora al revés:

unpack(42, [10, 10]); // => [4, 2]
unpack(42, [5, 4, 3, 2, 1]); // => [1, 3, 0, 0, 0]

Esto es tan hermoso. Ahora apliquemos este sistema numérico paramétrico al problema de las permutaciones. Consideraremos la longitud 2 permutaciones de A, B, C, D ¿Cuál es el número total de ellos? Veamos: primero dibujamos uno de los 4 elementos, luego uno de los 3 restantes, eso es 4 * 3 = 12 formas de dibujar 2 elementos. Estas 12 formas se pueden empaquetar en enteros [0..11]. Entonces, imaginemos que ya los hemos empaquetado y tratemos de desempacar:

for (var i = 0; i < 12; i++) {
console.log(unpack(i, [4, 3]));
}
// [0, 0], [0, 1], [0, 2],
// [1, 0], [1, 1], [1, 2],
// [2, 0], [2, 1], [2, 2],
// [3, 0], [3, 1], [3, 2]

Estos números representan elecciones, no índices en la matriz original. [0, 0] no significa tomar A, A , significa tomar el ítem # 0 de A, B, C, D (eso es A) y luego el ítem n. ° 0 de la lista restante B, C, D (eso es B) . Y la permutación resultante es A, B

Otro ejemplo: [3, 2] significa tomar el ítem n. ° 3 de A, B, C, D (eso es D) y luego el ítem n. ° 2 de la lista restante A, B, C (eso es C). Y la permutación resultante es D, C

Este mapeo se llama código Lehmer . Vamos a asignar todos estos códigos de Lehmer a las permutaciones:

AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC

Eso es exactamente lo que necesitamos. Pero si nos fijamos en la función de unpack , notará que produce dígitos de derecha a izquierda (para invertir las acciones del pack ). La elección de 3 se desempaqueta antes de la elección de 4. Eso es desafortunado, porque queremos elegir entre 4 elementos antes de elegir 3. Sin poder hacerlo, primero tenemos que calcular el código de Lehmer, acumularlo en una matriz temporal, y luego aplicarlo a la matriz de elementos para calcular la permutación real.

Pero si no nos importa el orden lexicográfico, podemos pretender que queremos elegir entre 3 elementos antes de elegir entre 4. Luego, la opción de 4 saldrá primero de unpack . En otras palabras, utilizaremos unpack(n, [3, 4]) lugar de unpack(n, [4, 3]) . Este truco permite calcular el siguiente dígito del código de Lehmer e inmediatamente aplicarlo a la lista. Y así es exactamente como funciona nth_permutation() .

Una última cosa que quiero mencionar es que unpack(i, [4, 3]) está estrechamente relacionado con el sistema de número factorial. Mire ese primer árbol nuevamente, si queremos permutaciones de longitud 2 sin duplicados, podemos omitir cada segundo índice de permutación. Eso nos dará 12 permutaciones de longitud 4, que se pueden recortar a la longitud 2.

for (var i = 0; i < 12; i++) {
var lehmer = unpack(i * 2, [4, 3, 2, 1]); // Factorial number system
console.log(lehmer.slice(0, 2));
}

Answer 4

Como señala RickyBobby, al considerar el orden lexicográfico de las permutaciones, debe usar la descomposición factorial a su favor.

Desde un punto de vista práctico, así es como lo veo:

• Realice una especie de división euclidiana, ¡excepto que lo hace con números factoriales, comenzando con (n-1)! , (n-2)! , y así.
• Mantenga los cocientes en una matriz. El i -ésimo cociente debe ser un número entre 0 y ni-1 inclusive, donde voy de 0 a n-1 .
• Esta matriz es tu permutación. El problema es que a cada cociente no le importan los valores anteriores, por lo que debe ajustarlos. Más explícitamente, necesita incrementar cada valor tantas veces como valores anteriores que sean menores o iguales.

El siguiente código C debería darle una idea de cómo funciona esto ( n es el número de entradas, y i es el índice de la permutación):

/**
* @param n The number of entries
* @param i The index of the permutation
*/
void ithPermutation(const int n, int i)
{
int j, k = 0;
int *fact = (int *)calloc(n, sizeof(int));
int *perm = (int *)calloc(n, sizeof(int));
// compute factorial numbers
fact[k] = 1;
while (++k < n)
fact[k] = fact[k - 1] * k;
// compute factorial code
for (k = 0; k < n; ++k)
{
perm[k] = i / fact[n - 1 - k];
i = i % fact[n - 1 - k];
}
// readjust values to obtain the permutation
// start from the end and check if preceding values are lower
for (k = n - 1; k > 0; --k)
for (j = k - 1; j >= 0; --j)
if (perm[j] <= perm[k])
perm[k]++;
// print permutation
for (k = 0; k < n; ++k)
printf("%d ", perm[k]);
printf("/n");
free(fact);
free(perm);
}

Por ejemplo, ithPermutation(10, 3628799) imprime, como se esperaba, la última permutación de diez elementos:

9 8 7 6 5 4 3 2 1 0

Answer 5

Depende de la forma en que "ordene" sus permutaciones (orden lexicográfico, por ejemplo).

Una forma de hacerlo es el sistema de número factorial , ¡te da una biyección entre [0, n!] Y todas las permutaciones.

Entonces, para cualquier número i en [0, n!] Puede calcular la i-permutación sin calcular los demás.

Esta escritura factorial se basa en el hecho de que cualquier número entre [0 yn!] Se puede escribir como:

SUM( ai.(i!) for i in range [0,n-1]) where ai <i

(es bastante similar a la descomposición de la base)

para obtener más información sobre esta descomposición, eche un vistazo a este hilo: https://math.stackexchange.com/questions/53262/factorial-decomposition-of-integers

Espero eso ayude

Como se indica en este artículo de la wikipedia, este enfoque equivale a calcular el código lehmer :

Una forma obvia de generar permutaciones de n es generar valores para el código de Lehmer (posiblemente utilizando la representación del sistema de número factorial de enteros hasta n!), Y convertirlos en las permutaciones correspondientes. Sin embargo, el último paso, aunque sencillo, es difícil de implementar de manera eficiente, ya que requiere n operaciones de selección y eliminación de una secuencia en una posición arbitraria; de las representaciones obvias de la secuencia como una matriz o una lista vinculada, ambas requieren (por diferentes razones) operaciones n2 / 4 para realizar la conversión. Con n es probable que sea bastante pequeño (especialmente si se necesita la generación de todas las permutaciones) eso no es demasiado problema, pero resulta que tanto para la generación aleatoria como para la sistemática hay alternativas simples que mejoran considerablemente. Por esta razón, no parece útil, aunque ciertamente posible, emplear una estructura de datos especial que permita realizar la conversión del código de Lehmer a la permutación en el tiempo O (n log n).

Entonces, lo mejor que puede hacer para un conjunto de n elemento es O (n ln (n)) con una estructura de datos adaptada.

Answer 6

Es calculable Este es un código de C # que lo hace por usted.

using System;
using System.Collections.Generic;
namespace WpfPermutations
{
public class PermutationOuelletLexico3<T>
{
// ************************************************************************
private T[] _sortedValues;
private bool[] _valueUsed;
public readonly long MaxIndex; // long to support 20! or less
// ************************************************************************
public PermutationOuelletLexico3(T[] sortedValues)
{
if (sortedValues.Length <= 0)
{
throw new ArgumentException("sortedValues.Lenght should be greater than 0");
}
_sortedValues = sortedValues;
Result = new T[_sortedValues.Length];
_valueUsed = new bool[_sortedValues.Length];
MaxIndex = Factorial.GetFactorial(_sortedValues.Length);
}
// ************************************************************************
public T[] Result { get; private set; }
// ************************************************************************
/// <summary>
/// Return the permutation relative to the index received, according to
/// _sortedValues.
/// Sort Index is 0 based and should be less than MaxIndex. Otherwise you get an exception.
/// </summary>
/// <param name="sortIndex"></param>
/// <param name="result">Value is not used as inpu, only as output. Re-use buffer in order to save memory</param>
/// <returns></returns>
public void GetValuesForIndex(long sortIndex)
{
int size = _sortedValues.Length;
if (sortIndex < 0)
{
throw new ArgumentException("sortIndex should be greater or equal to 0.");
}
if (sortIndex >= MaxIndex)
{
throw new ArgumentException("sortIndex should be less than factorial(the lenght of items)");
}
for (int n = 0; n < _valueUsed.Length; n++)
{
_valueUsed[n] = false;
}
long factorielLower = MaxIndex;
for (int index = 0; index < size; index++)
{
long factorielBigger = factorielLower;
factorielLower = Factorial.GetFactorial(size - index - 1); // factorielBigger / inverseIndex;
int resultItemIndex = (int)(sortIndex % factorielBigger / factorielLower);
int correctedResultItemIndex = 0;
for(;;)
{
if (! _valueUsed[correctedResultItemIndex])
{
resultItemIndex--;
if (resultItemIndex < 0)
{
break;
}
}
correctedResultItemIndex++;
}
Result[index] = _sortedValues[correctedResultItemIndex];
_valueUsed[correctedResultItemIndex] = true;
}
}
// ************************************************************************
/// <summary>
/// Calc the index, relative to _sortedValues, of the permutation received
/// as argument. Returned index is 0 based.
/// </summary>
/// <param name="values"></param>
/// <returns></returns>
public long GetIndexOfValues(T[] values)
{
int size = _sortedValues.Length;
long valuesIndex = 0;
List<T> valuesLeft = new List<T>(_sortedValues);
for (int index = 0; index < size; index++)
{
long indexFactorial = Factorial.GetFactorial(size - 1 - index);
T value = values[index];
int indexCorrected = valuesLeft.IndexOf(value);
valuesIndex = valuesIndex + (indexCorrected * indexFactorial);
valuesLeft.Remove(value);
}
return valuesIndex;
}
// ************************************************************************
}
}

Answer 7

Si almacena todas las permutaciones en la memoria, por ejemplo, en una matriz, podrá volver a sacarlas de a una por vez en O (1) vez.

Esto significa que tiene que almacenar todas las permutaciones, por lo que si el cálculo de todas las permutaciones lleva un tiempo prohibitivamente largo, o almacenarlas ocupa un espacio prohibitivamente grande, puede que esta no sea una solución.

Mi sugerencia sería intentarlo de todos modos, y volver si es demasiado grande / lento: no tiene sentido buscar una solución "inteligente" si alguien ingenuo hace el trabajo.