在javascript中找到第i个排列

问题描述

给定一个大小为 n 的数组 arr 和索引 0 我想返回第 i 个排列.

Given an array arr of size n, and and index 0<=i<n! I want to return the i'th permutation.

我能够编写一个获取所有排列的方法:

I was able to write a method that gets all permutations:

function permute (arr) {
  var permutations = [];
  if (arr.length === 1) {
    return [ arr ];
  }

  for (var i = 0; i <  arr.length; i++) {
    var subPerms = permute(arr.slice(0, i).concat(arr.slice(i + 1)));
    for (var j = 0; j < subPerms.length; j++) {
      subPerms[j].unshift(arr[i]);
      permutations.push(subPerms[j]);
    }
  }
  return permutations;
}

如何修剪它以只获得递归的一个分支?

How do I trim it to get only one branch of the recursion ?

推荐答案

您可以使用数组长度的阶乘作为获取目标排列的助手.基本上，该算法计算重新组合结果的数组索引.

You could use the factorial of the array length as helper for getting the target permutation. Basically, this algorithm calculates the array indices upon which reassembles the result.

function getN(n, array) {
    var f,
        l = array.length,
        indices = [];

    array = array.slice();
    while (l--) {
        f = factorial(l);
        indices.push(Math.floor(n / f));
        n %= f;
    }
    return indices.map(function (i) {
        return array.splice(i, 1)[0];
    });
}

function factorial(num) {
    var result = 1;
    while (num) {
        result *= num;
        num--;
    }
    return result;
}

var i, l,
    array = [1, 2, 3, 4];

for (i = 0, l = factorial(array.length); i < l; i++) {
    console.log(i, '>', getN(i, array).join(' '));
}

.as-console-wrapper { max-height: 100% !important; top: 0; }

这篇关于在javascript中找到第i个排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！