Como melhorar a eficiência do algoritmo que gera a próxima permutação lexicográfica?
Deve-se notar aqui que eu realizei a matemática manualmente no papel para derivar as provas anteriores. Não tenho certeza se as provas se tornariam aparentes usando apenas o meio do computador moderno.
A definição de "eficiência", conforme usada abaixo, significa concluir uma parte discreta do algoritmo ou todo o algoritmo no menor período de tempo. Tanto em termos matemáticos quanto programáticos ou computacionais.
Ao examinar procedimentos adicionais para gerar a próxima permutação lexicográfica a partir do conjunto original ou permutação de corrente, após reler a Resposta por @chqrlie emPermutações sem chamada de função recursiva, Iniciei a consulta escrevendo os índices no papel, na tentativa de observar quaisquer relações matemáticas entre os índices que poderiam ser utilizados para executar a tarefa específica.
Eu descobri várias verdades interessantes, as provas demonstradas abaixo.
Quando escrevemos, por exemplo, os valores
a,b,c
ou
abc
ou, em vez disso, escreva os índices que representam os valores
0,1,2
ou
012
Como sabemos, dado um conjunto
abc
que podemos gerar a próxima permutação lexicográfica trocando os dois últimos valores ou índices do conjunto
acb
ou
021
podemos ignorar os valores, que podem ser qualquer tipo de dados, e nos concentrar no uso dos índices para nossos exames, pois números discretos são mais adequados para correlacionar possíveis relacionamentos do que uma quantidade possivelmente infinita de valores diversificados.
Portanto, com o segundo índice lexicográfico do conjunto original
abc
podemos denotar os valores dos índices como números e observar
0,2,1
ou
021
Os primeiros índices sendo
012
o segundo ser
021
Desde que conhecemos o.length
do conjunto original é3
, se lembrarmos do.length
do conjunto original de valores, podemos remover o ponto de partida
0
onde reduzir os índices para o número
12
e
21
respectivamente. Onde o0
pode ser referenciado como o índice do conjunto original para obter o valor no índice0
quando o conjunto resultante da próxima operação for menor que o conjunto original.
Quando tentamos representar graficamente possíveis relacionamentos entre12
e21
, descobrimos que
21 - 12 = 9
Quando continuamos, descobrimos que os próximos índices lexicográficos são
102
subtraindo os índices anteriores
102 - 21 = 81
Onde102
é a próxima permutação lexicográfica, representada como os valores
bac
que nos fornece a relação comum entre os índices, sendo o número nove, representado numericamente como
9
Esse relacionamento é evidente e reproduzível para um conjunto infinito de valores de entrada representados como números. Podemos gráficos dos relacionamentos, que, dependendo da perspectiva do observador, podem ser vistos como duas inclinações, com um deslocamento de ápice invertido ao iniciar o gráfico a partir do primeiro valor do conjunto de permutações 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 aqui que o número no gráfico na inclinação de inclinação é idêntico ao número na inclinação de declinação correspondente, após a inversão do número do número total dividido de possíveis permutações divididas pela metade, onde por exemplo, para um total de seis permutações, subtraímos um, deixando o restante de cinco, lembrando que ainda precisamos do conjunto ímpar de índices, usamos o número no ápice invertido como um pivô, deixando quatro índices, que denotamos como inclinações e declinações, respectivamente .
Observamos aqui que os números no gráfico da inclinação de declinação são idênticos ao ângulo adjacente correspondente da inclinação de inclinação na mesma coordenada y.
Assim, abaixo demonstro a prova de que um conjunto infinito de permutações, dado um conjunto infinito de entradas, pode ser calculado, gerado, filtrado, derivado utilizando adição ou multiplicação do número nove
9
combinando números que incluem apenas o número do índice de um número de entrada, sem duplicado no conjunto.
Além disso, demonstro a prova de que apenas os índices precisam de números na inclinação, ou a quantidade total de permutações possíveis dividida por dois mais um, é necessária para derivar o número total de permutações de uma determinada entrada.
Conforme enfatizado no prefácio deste post, talvez esses cálculos não fossem possíveis sem muitas horas de fazer as contas manualmente no papel. A tela de mídia simples não fornece a mesma mídia que compor os caracteres um por um no papel; com a capacidade de visualizar o papel de várias dimensões físicas.
A expressão do algoritmo usando uma linguagem de codificação é outra tarefa em si.
A seguir, é apresentada uma progressão das descobertas, provas e expressões implementadas usando a linguagem de programação "JavaScript". A primeira versão possui umRegExp
que não é preciso quanto ao resultado esperado, como apontado por@Tushar, com correçãoRegExp
, embora incorretoRegExp
retorna o mesmo 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);
O gráfico da diferença numérica entre os números como índices para a matrizarr
será
// 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)
A eficiência da segunda versão foi bastante aprimorada em relação à primeira versão, substituindo o bitmask porRegExp
por Resposta de @lleaff emMétodo mais eficiente para verificar o intervalo de números dentro do número sem duplicatas.
Os perfis relevantes gerados porDevTools
Entre oRegExp
version e bitmask devem ser reproduzíveis no navegador chromium, no entanto, devido à negligência em comentar os testes exatos realizados, não consigo reproduzir com precisão os números e horários publicados, sem dedicar mais tempo à verificação dos números publicados na pergunta anterior. Não consigo lembrar com precisão, embora a guia do navegador possa ter travado quando.length
do conjunto de entrada era dez. O importante era que a versão de teste do bitmask fosse mais eficiente do queRegExp
versão de teste.
// 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);
As anotações e o processo levaram quase um ano, mais de um ano atrás, para mostrar e provar. Simplesmente pensaram em como obter índices para ambos os lados da inclinação simultaneamente, usando apenas índices de inclinação, em vez de codificar o algoritmo.
A maior parte da matemática estava na tentativa de derivar uma correlação adicional entre os múltiplos adjacentes do número nove, para a capacidade de calcular o próximo múltiplo exato do número nove.
9
para incrementar um número em nove e depois filtrar valores duplicados do número resultante. Ainda não consegui decifrar as inter-relações entre os múltiplos adjacentes de nove na inclinação do declive, na medida em que a multiplicação ou divisão pudesse substituir a adição e a exclusão.
Decidiu finalmente criar uma prova de conceito para a proposição de gerar um número infinito de permutações a partir de um conjunto de entradas infinitas, usando apenas a inclinação da inclinação, ou apenas os índices como números, da primeira metade das permutações possíveis mais uma.
// 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);
Outra etapa eventual no desenvolvimento do algoritmo receberá uma arbitrária.length
entrada, para poder calcular os índices e, portanto, os valores doenésimo permutação do conjunto matematicamente; usando apenas uma única fórmula de multiplicação, divisão, álgebra, trigonotetria ou cálculo.
Inclua referências de referência reproduzíveis no Answer. O motivo é que não consigo lembrar exatamente como deduzo os números paraProfiles
àsDevTools
, embora se lembre de usado corretamenteconsole.time()
, console.timeEnd()
econsole.profile()
no início e no final das respectivas partes, quando usados. Faça backup de seus experimentos; você nunca sabe se ou quando um disco rígido ou sistema operacional falhará. Geralmente, você pode recuperar os dados do disco, embora com custo de tempo e esforço para fazê-lo. Salve seus testes da mesma maneira que você salva versões de algoritmos, para capacidade de se reproduzir e para os outros se reproduzirem. A gama completa dos testes originais é perdida.
Os restos remanescentes do teste de quantas permutações poderiam ser derivadas antes da falha da guia do navegador são apenas comentários recuperados de um SO diferente
// 362880 876543210 876543219
var arr = ["a", "b", "c", "d", "e", "f", "g", "h", "i"];
onde se lembrar com precisão, quando"j"
foi adicionado à matriz, a guia ativa no cromo falhou. O primeiro número é a quantidade total de permutações para o conjunto "a" a "i"; os próximos dois números são provavelmente, embora não certos, os resultados de dois testes para uma das versões anteriores à versão 3, composta hoje.
Essa é outra razão para agora publicar a divulgação acima aqui no stackoverflow.com, para preservar os princípios do algoritmo e trabalhar no código feito até agora, menos uma catástrofe destruir todas as notas e trabalhos originais; por exemplo, ficar acordado por vários dias seguidos tentando interpretar padrões e relacionamentos entre números; deixar de documentar todos os padrões de teste específicos tentou tentar portar o algoritmo para codificar nos comentários dentro do código; ou como @JaromandaX descreveu a circunstância"PEBCAK".
Olhos novos provavelmente podem ver o algoritmo de uma perspectiva diferente quanto à eficiência.
Podemos reproduzir um gráfico dos resultados de algumas das versões de código preservadas acima, por exemplo, usandoconsole.time()
, console.timeEnd()
, performance.now()
ou outros testes apropriados que envolvam tempo para concluir a função, que pode ser reproduzida.
// 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 de rodapé, mencionarei que usei os princípios do algoritmo para derivar os resultados esperados emA maneira mais rápida de gerar todas as seqüências binárias de tamanho n em uma matriz booleana?, onde novamente, o número nove apareceu como um número-chave na inclinação, e o ângulo de declinação correspondente também é observável. Embora não tenha realizado mais testes e automação da forma específica de entrada e resultado descrita nessa pergunta. A resposta foi uma prova de conceito quanto à viabilidade da abordagem de ignorar os valores e usar apenas um padrão de incremento tipo onda aplicado a um número inicial de número único, zero, para derivar infinitas permutações de um conjunto.
Questões:
Como o algoritmo pode ser aprimorado quanto à eficiência; computacionalmente e matematicamente?
Podemos criar os índices para inclinação e inclinação ao mesmo tempo; em vez de determinar a inclinação da declinação após o cálculo da inclinação?
Existem relacionamentos ou padrões matemáticos entre os índices como números, ou seja, por exemplo, o conjunto de números emgráfico 1, gráfico 2 ougráfico 3, derivado da entrada de quaisquer quatro valores, por exemplo
abcd
ou
["a", "b", "c", "d"]
que o autor ainda não reconheceu; qual poderia ser usado para reduzir ainda mais o número de cálculos atualmente implementados para obter resultados?