Перестановки без вызова рекурсивной функции

Ответ 1

Вот простое решение для вычисления n-й перестановки строки:

function string_nth_permutation(str, n) {
    var len = str.length, i, f, res;

    for (f = i = 1; i <= len; i++)
        f *= i;

    if (n >= 0 && n < f) {
        for (res = ""; len > 0; len--) {
            f /= len;
            i = Math.floor(n / f);
            n %= f;
            res += str.charAt(i);
            str = str.substring(0, i) + str.substring(i + 1);
        }
    }
    return res;
}

Алгоритм следует следующим простым шагам:

• сначала вычислить f = len!, существуют factorial(len) полные перестановки набора из len разных элементов.
• как первый элемент, разделите номер перестановки на (len-1)! и выберите элемент в результате смещения. Существуют (len-1)! различные перестановки, которые имеют любой заданный элемент в качестве своего первого элемента.
• удалите выбранный элемент из набора и используйте оставшуюся часть деления в качестве номера перестановки для продолжения.
• выполните следующие действия с остальной частью набора, длина которого уменьшена на единицу.

Этот алгоритм очень прост и имеет интересные свойства:

• Он напрямую вычисляет n-ю перестановку.
• Если множество упорядочено, перестановки создаются в лексикографическом порядке.
• Он работает, даже если заданные элементы нельзя сравнивать друг с другом, например объекты, массивы, функции...
• Перестановочный номер 0 - это набор в указанном порядке.
• Перестановочный номер factorial(a.length)-1 является последним: набор a в обратном порядке.
• Перестановки вне этого диапазона возвращаются как undefined.

Его можно легко преобразовать для обработки набора, сохраненного в виде массива:

function array_nth_permutation(a, n) {
    var b = a.slice();  // copy of the set
    var len = a.length; // length of the set
    var res;            // return value, undefined
    var i, f;

    // compute f = factorial(len)
    for (f = i = 1; i <= len; i++)
        f *= i;

    // if the permutation number is within range
    if (n >= 0 && n < f) {
        // start with the empty set, loop for len elements
        for (res = []; len > 0; len--) {
            // determine the next element:
            // there are f/len subsets for each possible element,
            f /= len;
            // a simple division gives the leading element index
            i = Math.floor(n / f);
            // alternately: i = (n - n % f) / f;
            res.push(b.splice(i, 1)[0]);
            // reduce n for the remaining subset:
            // compute the remainder of the above division
            n %= f;
            // extract the i-th element from b and push it at the end of res
        }
    }
    // return the permutated set or undefined if n is out of range
    return res;
}

уточнение:

• f сначала вычисляется как factorial(len).
• Для каждого шага f делится на len, давая точный предыдущий факториал.
• n, деленное на это новое значение f, дает номер слота среди слотов len, имеющих один и тот же начальный элемент. Javascript не имеет интегрального деления, мы могли бы использовать (n / f) ... 0), чтобы преобразовать результат деления в его составную часть, но он вводит ограничение наборам из 12 элементов. Math.floor(n / f) допускает набор до 18 элементов. Мы могли бы также использовать (n - n % f) / f, возможно, более эффективно.
• n должно быть сведено к числу перестановок в этом слоте, то есть в остальной части деления n / f.

Мы могли бы использовать i по-разному во втором цикле, сохраняя остаток деления, избегая Math.floor() и дополнительного оператора %. Вот альтернатива для этого цикла, которая может быть даже менее читаемой:

        // start with the empty set, loop for len elements
        for (res = []; len > 0; len--) {
            i = n % (f /= len);
            res.push(b.splice((n - i) / f, 1)[0]);
            n = i;
        }

Ответ 2

Я думаю, что это сообщение должно помочь вам. Алгоритм должен быть легко переводим на JavaScript (я думаю, что он более чем на 70% уже совместим с JavaScript).

slice и reverse - это плохие вызовы, которые нужно использовать, если вы после эффективности. Алгоритм, описанный в сообщении, следует за наиболее эффективной реализацией функции next_permutation, которая даже интегрирована в некоторые языки программирования (например, С++).

ИЗМЕНИТЬ

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

ИЗМЕНИТЬ

Версия JavaScript:

function nextPermutation(array) {
    // Find non-increasing suffix
    var i = array.length - 1;
    while (i > 0 && array[i - 1] >= array[i])
        i--;
    if (i <= 0)
        return false;

    // Find successor to pivot
    var j = array.length - 1;
    while (array[j] <= array[i - 1])
        j--;
    var temp = array[i - 1];
    array[i - 1] = array[j];
    array[j] = temp;

    // Reverse suffix
    j = array.length - 1;
    while (i < j) {
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        i++;
        j--;
    }
    return true;
}

Ответ 3

Одним из способов создания перестановок является добавление каждого элемента во все промежутки между элементами во всех результатах до сих пор. Это можно сделать без рекурсии с использованием циклов и очереди.

Код JavaScript:

function ps(a){
  var res = [[]];

  for (var i=0; i<a.length; i++){
    while(res[res.length-1].length == i){
      var l = res.pop();
      for (var j=0; j<=l.length; j++){
        var copy = l.slice();
        copy.splice(j,0,a[i]);
        res.unshift(copy);
      }
    }
  }
  return res;
}

console.log(JSON.stringify(ps(['a','b','c','d'])));

Ответ 4

Вот еще одно решение, основанное на алгоритме Штайнхауса-Джонсона-Троттера:

function p(input) {
  var i, j, k, temp, base, current, outputs = [[input[0]]];
  for (i = 1; i < input.length; i++) {
    current = [];
    for (j = 0; j < outputs.length; j++) {
      base = outputs[j];
      for (k = 0; k <= base.length; k++) {
        temp = base.slice();
        temp.splice(k, 0, input[i]);
        current.push(temp);
      }
    }
    outputs = current;
  }
  return outputs;
}

// call

var outputs = p(["a", "b", "c", "d"]);
for (var i = 0; i < outputs.length; i++) {
  document.write(JSON.stringify(outputs[i]) + "<br />");
}

Ответ 5

Вот фрагмент для подхода, который я придумал сам по себе, но, естественно, также смог найти его в другом месте:

generatePermutations = function(arr) {
  if (arr.length < 2) {
    return arr.slice();
  }
  var factorial = [1];
  for (var i = 1; i <= arr.length; i++) {
    factorial.push(factorial[factorial.length - 1] * i);
  }

  var allPerms = [];
  for (var permNumber = 0; permNumber < factorial[factorial.length - 1]; permNumber++) {
    var unused = arr.slice();
    var nextPerm = [];
    while (unused.length) {
      var nextIndex = Math.floor((permNumber % factorial[unused.length]) / factorial[unused.length - 1]);
      nextPerm.push(unused[nextIndex]);
      unused.splice(nextIndex, 1);
    }
    allPerms.push(nextPerm);
  }
  return allPerms;
};

Enter comma-separated string (e.g. a,b,c):
<br/>
<input id="arrInput" type="text" />
<br/>
<button onclick="perms.innerHTML = generatePermutations(arrInput.value.split(',')).join('<br/>')">
  Generate permutations
</button>
<br/>
<div id="perms"></div>

Ответ 6

Я смею добавить еще один ответ, поставив вопрос на вопрос о slice, concat, reverse.

Ответ можно (почти), но это было бы не очень эффективно. Что вы делаете в своем алгоритме:

• Найти первую инверсию в массиве перестановок справа налево (инверсия в этом случае определяется как i и j где i < j и perm[i] > perm[j], индексы с учетом слева направо)
• поместите большее число инверсий
• объединить обработанные числа в обратном порядке, который будет таким же, как и отсортированный порядок, поскольку не было отмечено никаких инверсий.
• объединяет второе число инверсии (все еще отсортировано по совпадению с номером предыстории, поскольку не наблюдалось никаких инверсий).

Это, в основном, мой первый ответ, но немного более оптимальный.

Пример

Рассмотрим перестановку 9,10, 11, 8, 7, 6, 5, 4, 3,2,1 Первая инверсия справа налево - 10, 11. И действительно, следующая перестановка: 9,11,1,2,3,4,5,6,7,8,9,10 = 9concat (11) CONCAT (ред (8,7,6,5,4,3,2,1)) CONCAT (10)

Исходный код Здесь я включаю исходный код, как я себе это представляю:

var nextPermutation = function(arr) {
  for (var i = arr.length - 2; i >= 0; i--) {
     if (arr[i] < arr[i + 1]) {
        return arr.slice(0, i).concat([arr[i + 1]]).concat(arr.slice(i + 2).reverse()).concat([arr[i]]);
     }
  }
  // return again the first permutation if calling next permutation on last.
  return arr.reverse();
}

console.log(nextPermutation([9, 10, 11, 8, 7, 6, 5, 4, 3, 2, 1]));
console.log(nextPermutation([6, 5, 4, 3, 2, 1]));
console.log(nextPermutation([1, 2, 3, 4, 5, 6]));

Код доступен для jsfiddle здесь.

Ответ 7

Довольно простой код C++ без рекурсии.

#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <string>

// Integer data
void print_all_permutations(std::vector<int> &data) {
    std::stable_sort(std::begin(data), std::end(data));
    do {
        std::copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " ")), std::cout << '\n';
    } while (std::next_permutation(std::begin(data), std::end(data)));
}

// Character data (string)
void print_all_permutations(std::string &data) {
    std::stable_sort(std::begin(data), std::end(data));
    do {
        std::copy(data.begin(), data.end(), std::ostream_iterator<char>(std::cout, " ")), std::cout << '\n';
    } while (std::next_permutation(std::begin(data), std::end(data)));
}

int main()
{
    std::vector<int> v({1,2,3,4});
    print_all_permutations(v);

    std::string s("abcd");
    print_all_permutations(s);

    return 0;
}

Мы можем найти следующую перестановку последовательности в линейном времени.

Ответ 8

Вот ответ от @le_m. Это может помочь

Следующий очень эффективный алгоритм использует метод Heap для генерации всех перестановок из N элементов со сложностью во время выполнения в O (N!):

function permute(permutation) {
  var length = permutation.length,
      result = [permutation.slice()],
      c = new Array(length).fill(0),
      i = 1, k, p;

  while (i < length) {
    if (c[i] < i) {
      k = i % 2 && c[i];
      p = permutation[i];
      permutation[i] = permutation[k];
      permutation[k] = p;
      ++c[i];
      i = 1;
      result.push(permutation.slice());
    } else {
      c[i] = 0;
      ++i;
    }
  }
  return result;
}

console.log(JSON.stringify(permute([1, 2, 3, 4])));