Proyecto Euler - Problema 24

El problema 24 habla de permutaciones y el orden lexicografico.

Aclaración!!!
1. Una permutación es cada una de las diferentes ordenaciones posibles de un conjunto de objetos, así, por ejemplo de los elementos [a b c] existen seis permutaciones posibles a saber: abc, acb, bac, bca, cab, cba.

2. El orden lexicografico es relación de orden que utiliza la ordenación ascendente de un conjunto de elementos, es el orden utilizado en las lista de nombres de personas como el directorio telefónico por ejemplo, para verlo más fácilmente las permutaciones de los elementos [a b c] ordenadas lexicograficamente son

abc, acb, bac, bca, cab, cba.

Con eso aclarado, el problema 24, pregunta cuál es la millonésima permutación lexicografica de los números dígidos [ 0 1 2 3 4 5 6 7 8 9].

SOLUCIÓN 1: (Fuerza bruta!!!)

La primera idea que apareció ante esta cuestión fue encontrar todas las permutaciones del vector de los dígitos, ordenarlas lexicograficamente y determinar cual quedaba almacenada en la posición un millón.

Matlab tiene la función perms que permite encontrar todas las permutaciones de un vector de elementos, esta función genera una matriz MxN que almacena todas las permutaciones de los N elementos del vector, para el caso, genera una matriz 3628800x10.

Para ordenarlas lexicográficamente puede utilizarse la función sort, sin embargo antes de hacer esto hay que lograr que se leea cada fila de la matriz como un número de 10 dígitos, es decir en lugar de [5 3 6 8 9 0 1 2 4 7] es necesario que pueda leerse como 5368901247, esto se consigue fácilmente con una sola línea de código

syms(num2str(P(i,:)))

esta línea convierte cada fila de la matriz P en una cadena de dígitos. Estas cadenas ya pueden ser ordenadas lexicograficamente, es más añadiendo sort al iniciar la anterior línea se ejecuta todo el proceso en un solo paso.

Finalmente ejecutanto P(1000000,:) se consigue la respuesta al problema.

NOTA: Este procedimiento tardará más de 19 horas en una máquina con 4 núcleos de 3 GHz cada uno y con 2 GB de ram físicos y 1 GB de swap.

SOLUCIÓN 2 (más inteligente)

Pensando en que no podría poner el pc a trabajar 19 horas para conseguir esta respuesta se llega a lo siguiente.

1. Hay 3628800 permutaciones de los número dígitos, eso indica que hay 362880 permutaciones para cada dígito en la posición 1. Si se piensa bien.... 362880 permutaciones que inician con 0, 362880 que inician con 1, 362880 que inician con 2 y ya se está en la permutación 1088640, lo que indica que el primer elemento de la solución es el número 2.

2. Ahora para el segundo elemento quedan 9 dígitos, lo que nos deja con 40320 permutaciones por dígito... haciendo el mismo análisis anterior se llega a que el segundo elemento de la solución es 7.

3. El código que permita hacer eso 

clear all; clc;

V=[0 1 2 3 4 5 6 7 8 9];

L=factorial(length(V))/length(V);

i=1;e=0;j=1;

while i~=1000000

    if i>1000000

        R(j)=V(e);

        j=j+1;

        i=i-L;

        V=[V(1:e-1) V(e+1:length(V))];

        e=0;

        L=factorial(length(V))/length(V);

    else

        i=i+L;

        e=e+1;

    end

end

disp(R);

disp(V);

Ahora podría esperarse que la respuesta de la última instrucción fuera un vector nulo pero... resulta que 2!/2 =1 lo que indica que los dos últimos elementos tienen el mismo número de permutaciones asociado, por lo cual que se llegará a 1000000 antes de haber analizado todos los elementos del vector, esto nos deja con dos soluciones posibles, pero saber cual de las dos es la correcta es aún más fácil.

NOTA: Un hermoso segundo tarda esta solución.

Así termina la solución del problema 24 del proyecto euler.