¿Cómo mejorar la eficiencia del algoritmo que genera la próxima permutación lexicográfica?
Debe notarse aquí que realicé las matemáticas a mano en papel para obtener las pruebas anteriores. No estoy seguro de si las pruebas se habrían puesto de manifiesto utilizando únicamente el medio de la computadora moderna.
La definición de "eficiencia" como se usa a continuación significa completar una porción discreta del algoritmo, o el algoritmo completo en la menor cantidad de tiempo. Tanto en términos matemáticos como programáticos o computacionales.
Mientras se examinan los procedimientos para generar la próxima permutación lexicográfica a partir del conjunto original o la permutación actual, después de volver a leer la Respuesta de @chqrlie enPermutaciones sin llamada a función recursivaComencé la investigación escribiendo los índices en papel en un intento de observar cualquier relación matemática entre los índices que pudiera utilizarse para realizar la tarea específica.
Descubrí varias verdades interesantes, las pruebas de ello se demuestran a continuación.
Cuando escribimos, por ejemplo, los valores
a,b,c
o
abc
o, en su lugar, escriba los índices que representan los valores
0,1,2
o
012
Como sabemos, dado un conjunto
abc
que podemos generar la próxima permutación lexicográfica intercambiando los dos últimos valores o índices del conjunto
acb
o
021
podemos ignorar los valores, que podrían ser cualquier tipo de datos, y concentrarnos en usar los índices para nuestros exámenes, ya que los números discretos son más adecuados para correlacionar posibles relaciones que una cantidad posiblemente infinita de valores diversificados.
Por lo tanto, con el segundo índice lexicográfico del conjunto original
abc
podemos denotar los valores de los índices como números y observar
0,2,1
o
021
Los primeros índices son
012
el segundo ser
021
Como sabemos el.length del conjunto original es3, si recordamos el.length del conjunto original de valores, podemos eliminar el inicio
0
donde reducir los índices al número
12
y
21
respectivamente. Donde el0 puede ser referenciado como el índice del conjunto original para obtener el valor en el índice0 cuando el conjunto resultante de la siguiente operación es menor que el conjunto original.
Cuando intentamos graficar relaciones potenciales entre12 y21, encontramos eso
21 - 12 = 9
Cuando continuamos, encontramos que los siguientes índices lexicográficos son
102
restando los índices anteriores
102 - 21 = 81
dónde102 es la próxima permutación lexicográfica, representada como los valores
bac
lo que nos proporciona la relación común entre los índices siendo el número nueve, representado numéricamente como
9
Esta relación es evidente y reproducible para un conjunto infinito de valores de entrada representados como números. Podemos hacer gráficas de las relaciones que, dependiendo de la perspectiva del observador, se pueden ver como dos pendientes, con un desplazamiento del vértice invertido al comenzar la gráfica desde el primer valor del conjunto de permutaciones resultantes
// graph 1
0,9,81
// graph 2
abc 012 0
acb 021 1 9
bac 102 2 81
bca 120 3 18
cab 201 4 81
cba 210 5 9
/\/\
/ \
Podemos observar aquí que el número en el gráfico en la pendiente de inclinación es idéntico al número en la pendiente de declinación correspondiente, siguiendo la inversión del número del número total dividido de permutaciones posibles dividido por la mitad, donde por ejemplo, para un total de seis permutación, restamos uno, dejando el resto de cinco, recordando que todavía necesitamos el conjunto impar de índices, usamos el número en el vértice invertido como un pivote, dejando cuatro índices, que denotamos como pendientes de inclinación y declinación, respectivamente .
Observamos aquí que los números en el gráfico de la pendiente de declinación son idénticos al ángulo adyacente correspondiente de la pendiente de inclinación en la misma coordenada y.
Por lo tanto, a continuación demuestro la prueba de que un conjunto infinito de permutaciones dado un conjunto de entrada infinito puede calcularse, generarse, filtrarse, derivarse mediante la suma o multiplicación del número nueve
9
haciendo coincidir los números que incluyen solo el número del índice de un número de entrada, sin duplicar en el conjunto.
Además, demuestro la prueba de que solo se necesitan los índices como números en la pendiente de inclinación, o la cantidad total de permutaciones posibles dividida entre dos más uno, para obtener el número total de permutaciones de una entrada dada.
Como se destacó en el prefacio de esta publicación, estos cálculos quizás no hubieran sido posibles sin muchas horas de hacer las matemáticas a mano en papel. La pantalla de medios simple no proporciona el mismo medio que componer los caracteres uno por uno en papel; con la capacidad de ver el papel desde varias dimensiones físicas.
La expresión del algoritmo usando un lenguaje de codificación es otra tarea en sí misma.
Lo siguiente es una progresión de los descubrimientos, pruebas y expresiones de los mismos implementados usando el lenguaje de programación "JavaScript". La primera versión tiene unRegExp eso no es exacto en cuanto al resultado esperado, como lo señala@Tushar, con corregidoRegExp, aunque incorrectoRegExp devuelve el mismo resultado.
Entrada dada como matriz
var arr = ["a", "b", "c", "d"];
// version 1
function getNextLexicographicPermutation(arr) {
var len = arr.length;
var idx = arr.map(function(_, index) {
return index
});
var re = new RegExp("[" + len + "-9]|(.)(?!=\\1)");
var n = Math.pow(10, len - 1);
var p = 9;
var last = Number(idx.slice().reverse().join(""));
var res = [idx];
var curr = Number(res[res.length - 1].join(""));
while (curr < last) {
for (var prev = curr, next, k; prev <= last; prev += p) {
if ((re.test(prev))) {
k = String(prev);
if (k.length >= len - 1) { // && Math.max.apply(Math, j) < len
next = [];
for (var i = 0; i < k.length; i++) {
if (next.indexOf(Number(k[i])) == -1
&& idx.indexOf(Number(k[i])) !== -1) {
next.push(Number(k[i]))
}
}
if (prev < n && next.length === len - 1
|| next.length === len && prev > curr) {
res[res.length] = next.length < len
? [0].concat.apply([0], next)
: next;
}
}
}
curr = prev;
}
};
return res.map(function(value) {
return value.map(function(index) {
return arr[index]
})
})
}
getNextLexicographicPermutation(arr);
El gráfico para la diferencia numérica entre los números como índices para la matrizarr estarán
// graph 3
// reflecting input `abcd`
[9,81,18,81,9,702,9,171,27,72,18,693,18,72,27,171,9,702,9,81,18,81,9]
// version 2.0 without using `RegExp`
function getNextLexicographicPermutation(arr) {
var len = arr.length;
var idx = arr.map(function(_, index) {
return index
});
var n = Math.pow(10, len - 1);
var p = 9;
var last = Number(idx.slice().reverse().join(""));
var res = [];
var curr = Number(idx.join(""));
var prev, k, next;
while (curr <= last) {
prev = curr;
k = String(prev).split("").map(Number);
if (k.every(function(v) {
return idx.indexOf(v) !== -1
}) && k.length >= len - 1) {
next = [];
for (var i = 0; i < k.length; i++) {
if (next.indexOf(Number(k[i])) == -1
&& idx.indexOf(Number(k[i])) !== -1) {
next.push(Number(k[i]))
}
}
if (prev < n && next.length === len - 1
|| prev > n && next.length === len)) {
res[res.length] = next.length < len
? [0].concat.apply([0], next)
: next;
}
}
prev += p;
curr = prev;
};
return res.map(function(item) {
return item.map(function(v) {
return arr[v]
})
})
}
getNextLexicographicPermutation(arr)
La eficiencia de la segunda versión se mejoró considerablemente con respecto a la primera al sustituir la máscara de bits porRegExp por Respuesta de @lleaff enEl método más eficiente para verificar el rango de números dentro del número sin duplicados.
Los perfiles relevantes generados porDevTools Entre losRegExp La versión y la versión de la máscara de bits deben ser reproducibles en Chrome Browser, sin embargo, debido a que no se comentan las pruebas exactas realizadas, no puedo reproducir con precisión los números y tiempos publicados sin dedicar más tiempo a verificar los números publicados en la pregunta anterior. No puedo recordar con precisión, aunque la pestaña del navegador puede haberse bloqueado cuando.length del conjunto de entrada fue diez. Lo importante era que la versión de prueba de la máscara de bits era más eficiente queRegExp versión de prueba
// version 2.1, substituting bitmask for `RegExp`
function getNextLexicographicPermutation(arr) {
function checkDigits(min, max, n) {
var digits = 0;
while (n) {
d = (n % 10);
n = n / 10 >> 0;
if (d < min || d > max || (digits & (1 << d)))
return false;
else
digits |= 1 << d;
}
return true;
}
var len = arr.length,
idx = arr.map(function(_, index) {
return index
}),
p = 9,
min = 0,
max = len - 1,
last = Number(idx.slice().reverse().join("")),
res = [],
curr = Number(idx.join("")),
next;
while (curr < last) {
next = (curr += p);
if (checkDigits(min, max, next)) res[res.length] = next;
curr = next;
};
return res.map(function(item) {
var item = String(item).split("").map(Number);
item = item.length < arr.length ? [0].concat(item) : item;
return item.map(function(index) {
return arr[index]
}).filter(Boolean)
})
}
getNextLexicographicPermutation(arr);
Las notas y el proceso tomaron la mayor parte de un año, hace más de un año, para mostrar y probar. Principalmente, simplemente pensé en cómo obtener índices para cada lado de la pendiente simultáneamente, utilizando solo índices de inclinación, en lugar de codificar el algoritmo.
La mayor parte de las matemáticas estaba en tratar de derivar una correlación adicional entre los múltiplos adyacentes del número nueve, para la capacidad de calcular el siguiente múltiplo exacto del número nueve
9
para incrementar un número en nueve y luego filtrar valores duplicados del número resultante. Todavía no he podido descifrar las interrelaciones entre los múltiplos adyacentes de nueve en la pendiente de inclinación en el grado en que la multiplicación o división podría ser sustituida por la suma y la exclusión.
Decidió finalmente crear una prueba de concepto para la proposición de generar un número infinito de permutaciones a partir de un conjunto de entrada infinito, utilizando solo la pendiente de inclinación, o solo los índices como números, de la primera mitad de las permutaciones posibles más uno.
// version 3, generate second half of permutations using indexes of first
// half of permutations
function getNextLexicographicPermutation(arr) {
for (var l = 1, i = k = arr.length; l < i ; k *= l++);
function checkDigits(min, max, n) {
var digits = 0;
while (n) {
d = (n % 10);
n = n / 10 >> 0;
if (d < min || d > max || (digits & (1 << d)))
return false;
else
digits |= 1 << d;
}
return true;
}
var len = arr.length
, idx = arr.map(function(_, index) {
return index
})
, p = 9
, min = 0
, max = len - 1
, last = Number(idx.slice().reverse().join(""))
, curr = Number(idx.join(""))
, res = []
, diff = []
, result = []
, next;
while (res.length < (k / 2) + 1) {
next = (curr += p);
if (checkDigits(min, max, next)) res[res.length] = next;
curr = next;
};
for (var i = 0; i < res.length; i++) {
var item = res[i];
item = String(item).split("").map(Number);
item = (item.length < arr.length ? [0].concat(item) : item)
.map(function(index) {
return arr[index]
}).filter(Boolean);
result.push(item)
}
res.reduce(function(a, b) {
diff.push(b - a);
return b
});
for (var i = 0, curr = res[res.length - 1], n = diff.length - 2
; result.length < k; i++, n--) {
curr = curr + diff[n];
result.push(
String(curr).split("")
.map(function(index) {
return arr[index]
})
);
}
return result;
}
getNextLexicographicPermutation(arr);
Otro paso eventual en el desarrollo del algoritmo recibirá un arbitrario.length input, para poder calcular los índices y, por lo tanto, los valores deenésimo permutación del conjunto matemáticamente; mediante el uso de una sola fórmula de multiplicación, división, álgebra, trigonotetría o cálculo.
Incluya puntos de referencia reproducibles en Answer. La razón es que no puedo recordar exactamente cómo obtengo los números paraProfiles aDevTools, aunque si recuerda correctamente utilizadoconsole.time(), console.timeEnd() yconsole.profile() al principio y al final de las porciones respectivas donde se usan. Respalda tus experimentos; nunca se sabe si un disco duro o sistema operativo se bloqueará o cuándo lo hará. En general, puede recuperar los datos del disco, aunque a costa de tiempo y esfuerzo para hacerlo. Guarde sus pruebas de la misma manera que también guarda versiones de algoritmos, para poder reproducirse usted mismo y para que otros lo hagan. Se pierde toda la gama de las pruebas originales.
Los restos sobrevivientes de la prueba de cuántas permutaciones podrían derivarse antes de que la pestaña del navegador se bloqueara son solo comentarios recuperados de un sistema operativo diferente
// 362880 876543210 876543219
var arr = ["a", "b", "c", "d", "e", "f", "g", "h", "i"];
donde si recuerda con precisión, cuando"j" se agregó a la matriz, la pestaña activa en Chrome se bloqueó. El primer número es la cantidad total de permutaciones para el conjunto "a" hasta "i"; Los dos números siguientes son probablemente, aunque no seguros, los resultados de dos pruebas para una de las versiones anteriores a la versión 3, que compuso hoy.
Esa es otra razón para publicar ahora la divulgación anterior aquí en stackoverflow.com, para preservar los principios del algoritmo y trabajar en el código realizado hasta ahora, menos alguna catástrofe destruya todas las notas y trabajos originales; por ejemplo, estar despierto durante varios días seguidos tratando de interpretar patrones y relaciones entre números; descuidando documentar todos los patrones de prueba específicos, trató de portar el algoritmo para codificar en los comentarios dentro del código; o como @JaromandaX describió la circunstancia"PEBCAK".
Los ojos nuevos probablemente puedan ver el algoritmo desde una perspectiva diferente en cuanto a la eficiencia.
Podemos reproducir un gráfico de los resultados de algunas de las versiones de código conservadas anteriores, por ejemplo, utilizandoconsole.time(), console.timeEnd(), performance.now() u otras pruebas apropiadas que implican tiempo para completar la función, que pueden reproducirse.
// console.time("version N");
// getNextLexicographicPermutation(arr);
// console.timeEnd("version N");
var tests = [];
for (var i = 0; i < 10000; i++) {
var from = window.performance.now();
getNextLexicographicPermutation(arr);
tests.push(window.performance.now() - from);
}
for (var i = 0, k = 0; i < tests.length; i++) {
k += tests[i];
}
var avg = k/tests.length;
// version 1 `avg`: 0.2989265000001993
// version 2.0 `avg`: 0.8271295000007376
// version 2.1 `avg`: 0.17173000000003666
// version 3 `avg`: 0.12989749999987543
Como nota al pie, mencionaré que utilicé los principios del algoritmo para obtener los resultados esperados en¿La forma más rápida de generar todas las cadenas binarias de tamaño n en una matriz booleana?, donde nuevamente, el número nueve apareció como un número clave dentro de la pendiente de inclinación, y el ángulo de declinación correspondiente también es observable. Sin embargo, no realizó pruebas adicionales ni la automatización de la forma específica de entrada y resultado que se describe en esa pregunta. La respuesta fue una prueba de concepto en cuanto a la viabilidad del enfoque de ignorar los valores y usar solo un patrón de incremento en forma de onda aplicado a un número inicial de un solo número, cero, para derivar permutaciones infinitas de un conjunto.
Preguntas:
¿Cómo se puede mejorar el algoritmo en cuanto a eficiencia? tanto computacional como matemáticamente?
¿Podemos crear los índices para la inclinación y la inclinación de declinación al mismo tiempo; en lugar de determinar la pendiente de declinación después de calcular la pendiente de inclinación?
¿Existen relaciones o patrones matemáticos entre los índices como números, es decir, por ejemplo, el conjunto de números engráfico 1, gráfico 2 ográfico 3, derivado de la entrada de cuatro valores, por ejemplo
a B C D
o
["a", "b", "c", "d"]
que el autor aún no ha reconocido; ¿Cuál podría usarse para reducir aún más el número de cálculos implementados actualmente para obtener resultados?