следует отметить, что я выполнил математику вручную на бумаге, чтобы получить приведенные выше доказательства. Я не уверен, что доказательства стали бы очевидными, если бы мы использовали исключительно современный компьютер.

Используемое ниже определение «эффективность» означает завершение дискретной части алгоритма или всего алгоритма за наименьшее количество времени. И математически, и программно, или вычислительно.

При дальнейшем изучении процедур для генерации следующей лексикографической перестановки из исходного набора или текущей перестановки, после повторного чтения ответа от @chqrlie вПерестановки без рекурсивного вызова функцииЯ начал исследование с написания индексов на бумаге, пытаясь наблюдать какие-либо математические зависимости между индексами, которые можно было бы использовать для выполнения конкретной задачи.

Я обнаружил несколько интересных истин, доказательства которых приведены ниже.

Когда мы пишем, например, значения

a,b,c

или же

abc

или вместо этого напишите индексы, представляющие значения

0,1,2

или же

012

Поскольку мы знаем, учитывая набор

abc

что мы можем создать следующую лексикографическую перестановку, поменяв местами последние два значения или индексы набора

acb

или же

021

мы можем игнорировать значения, которыми могут быть данные любого типа, и сосредоточиться на использовании индексов для наших исследований, поскольку дискретные числа больше подходят для корреляции возможных отношений, чем, возможно, бесконечное количество разнообразных значений.

Следовательно, со вторым лексикографическим указателем исходного набора

abc

мы можем обозначить значения индексов числами и наблюдать

0,2,1

или же

021

Первые индексы

012

второе существо

021

Так как мы знаем.length оригинального набора3, если мы помним.length из исходного набора значений, мы можем удалить начальный

0

где свести индексы к числу

12

а также

21

соответственно. Где0 можно ссылаться как индекс из исходного набора, чтобы получить значение по индексу0 когда результирующий набор следующей операции меньше исходного набора.

Когда мы пытаемся наметить потенциальные отношения между12 а также21мы находим, что

21 - 12 = 9

Когда мы продолжим, мы обнаружим, что следующие лексикографические индексы

102

вычитая предыдущие индексы

102 - 21 = 81

где102 следующая лексикографическая перестановка, представленная в виде значений

bac

что дает нам общую связь между индексами, являющимися номером девять, численно представлены как

9

Эта связь очевидна и воспроизводима для бесконечного набора входных значений, представленных в виде чисел. Мы можем построить графики отношений, которые, в зависимости от перспективы наблюдателя, можно рассматривать как два уклона с инвертированным смещением вершины при начале графика с первого значения набора результирующих перестановок.

// 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

 /\/\
/    \

Здесь мы можем наблюдать, что число на графике на наклоне наклона совпадает с числом на соответствующем наклоне наклона, после инверсии числа разделенного общего числа возможных перестановок, деленного на половину, где, например, для общего из шести перестановок мы вычитаем один, оставляя остаток из пяти, помня, что нам все еще нужен нечетный набор индексов, мы используем число в перевернутой вершине в качестве точки разворота, оставляя четыре индекса, которые мы обозначаем как наклоны наклона и склонения соответственно ,

Здесь мы наблюдаем, что числа на графике наклона склонения совпадают с соответствующим смежным углом наклона наклона при той же координате y.

Таким образом, ниже я демонстрирую доказательство того, что бесконечный набор перестановок с заданным бесконечным входным набором может быть рассчитан, сгенерирован, отфильтрован, получен с использованием сложения или умножения числа девять

9

сопоставляя числа, которые включают только номер индекса входного числа, без дублирования в наборе.

Кроме того, я демонстрирую доказательство того, что нужны только индексы в виде чисел на склоне наклона или общее количество возможных перестановок, деленное на два плюс один, которые необходимы для получения общего числа перестановок данного ввода.

Как подчеркивалось в предисловии к этому посту, эти расчеты, возможно, были бы невозможны без многих часов выполнения математических работ на бумаге. Простой экран мультимедиа не обеспечивает того же носителя, что и написание символов один за другим на бумаге; с возможностью просмотра бумаги из разных физических измерений.

Выражение алгоритма с использованием языка кодирования является еще одной задачей.

Ниже приведена последовательность открытий, доказательств и выражений, реализованных с использованием языка программирования «JavaScript». Первая версия имеетRegExp это не является точным в отношении ожидаемого результата, как указано@Tusharс исправленнымиRegExpхотя и неверноRegExp возвращает тот же результат.

Заданный вход как массив

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);

График для числовой разницы между числами в виде индексов для массиваarr будет

// 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)

Эффективность второй версии была значительно улучшена по сравнению с первой версией, заменив битовую маску дляRegExp Ответом @lleaff наНаиболее эффективный метод проверки диапазона номеров в номере без дубликатов.

Соответствующие профили, созданныеDevTools междуRegExp Версия и версия битовой маски должны воспроизводиться в браузере Chromium, однако из-за пренебрежения комментированием точных выполненных тестов я не могу точно воспроизвести числа и время, отправленные без выделения дополнительного времени для проверки чисел, опубликованных в предыдущем Вопросе. Не могу вспомнить точно, хотя вкладка браузера могла зависнуть, когда.length входного набора было десять. Важно было то, что тестовая версия с битовой маской была более эффективной, чемRegExp тестовая версия.

// 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);

Записки и процесс заняли лучшую часть года, больше года назад, чтобы показать и доказать. В основном просто подумал, как получить индексы для обеих сторон наклона одновременно, используя только индексы наклона наклона, а не кодируя алгоритм.

Основная часть математики была в попытках получить дальнейшую корреляцию между соседними кратными числа девять, для способности вычислить точное следующее кратное число девять

9 

для увеличения числа на девять, а затем отфильтровывать повторяющиеся значения из полученного числа. Я еще не смог расшифровать взаимосвязи между соседними кратными девяти на склоне наклона до такой степени, чтобы умножение или деление можно было заменить на сложение и исключение.

Решено, наконец, создать доказательство концепции для предложения генерирования бесконечного числа перестановок из бесконечного входного набора, используя только наклон наклона или только индексы в качестве чисел, первой половины возможных перестановок плюс один.

// 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);

Еще один возможный шаг в развитии алгоритма будет дан произвольный.length вход, чтобы иметь возможность рассчитать индексы, и, следовательно, значенияэнный перестановка множества математически; используя только одну формулу умножения, деления, алгебры, тригонометрии или исчисления.

Пожалуйста, включите воспроизводимые тесты в ответ. Причина в том, что не могу вспомнить, как именно я получаю числа дляProfiles вDevToolsправда, если помните правильно использовалconsole.time(), console.timeEnd() а такжеconsole.profile() в начале и в конце соответствующих частей, где они используются. Сделайте резервную копию ваших экспериментов; Вы никогда не знаете, произойдет ли сбой жесткого диска или ОС. Как правило, вы можете извлечь данные с диска, хотя затрачивая на это время и силы. Сохраняйте свои тесты таким же образом, вы также сохраняете версии алгоритмов, чтобы иметь возможность воспроизводить себя и других. Полная гамма оригинальных тестов потеряна.

Сохранившиеся остатки теста на то, сколько перестановок может быть получено до сбоя вкладки браузера, представляют собой только комментарии, полученные из другой ОС

// 362880 876543210 876543219 
var arr = ["a", "b", "c", "d", "e", "f", "g", "h", "i"];

где, если вспомнить точно, когда"j" был добавлен в массив, активная вкладка в Chromium потерпела крах. Первое число - это общее количество перестановок для набора от «а» до «i»; следующие два числа, вероятно, хотя и не уверены, являются результатами двух тестов для одной из версий до версии 3, которые были составлены сегодня.

Это еще одна причина для того, чтобы опубликовать вышеупомянутое раскрытие здесь, на stackoverflow.com, чтобы сохранить принципы алгоритма и работать над кодом, выполненным до сих пор, за исключением некоторой катастрофы, уничтожающей все исходные заметки и работу; например, бодрствовать в течение нескольких дней подряд, пытаясь интерпретировать закономерности и отношения между числами; пренебрегая документированием всех специфических тестовых шаблонов, пытался портировать алгоритм для кодирования комментариев в коде; или как @JaromandaX описал обстоятельства"PEBCAK".

Свежие глаза, вероятно, могут увидеть алгоритм с другой точки зрения в отношении эффективности.

Мы можем воспроизвести график результатов из некоторых сохраненных версий кода выше, например, используяconsole.time(), console.timeEnd(), performance.now() или другие соответствующие тесты, требующие времени для завершения функции, которые могут быть воспроизведены.

// 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

В качестве сноски я упомяну, что я использовал принципы алгоритма для получения ожидаемых результатов приСамый быстрый способ генерировать все двоичные строки размером n в логический массив?где снова число девять появилось в качестве ключевого числа в пределах наклона наклона, и совпадающий угол склонения также можно наблюдать. Хотя я не проводил дальнейшие тесты и автоматизацию конкретной формы ввода и результата, описанной в этом Вопросе. Ответ был подтверждением концепции жизнеспособности подхода игнорирования значений и использования только волнообразного возрастающего шаблона, применяемого к начальному числу, равному нулю, для получения бесконечных перестановок множества.

Вопросы:

Как можно улучшить алгоритм с точки зрения эффективности; как в вычислительном отношении, так и математически?

Можем ли мы создать индексы для наклона и наклона склонения одновременно; вместо определения наклона склонения после того, как был рассчитан наклон наклона?

Существуют ли математические отношения или закономерности между индексами в виде чисел, например, набор чисел вграфик 1, график 2 или жеграфик 3, полученных из ввода любых четырех значений, например

ABCD

или же

["a", "b", "c", "d"]

что автор еще не признал; что может быть использовано для дальнейшего сокращения числа вычислений, которые в настоящее время применяются для получения результатов?