Como melhorar a eficiência do algoritmo que gera a próxima permutação lexicográfica?

Question

Apr 08, 2017, 07:18 AM

algorithm math javascript permutation language-agnostic

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

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

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

Os primeiros índices sendo

o segundo ser

Desde que conhecemos o.length do conjunto original é3, se lembrarmos do.length do conjunto original de valores, podemos remover o ponto de partida

onde reduzir os índices para o número

e

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

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

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

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.

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