在javascript中找到ith排列 [英] Find ith permutation in javascript

问题描述

给定大小 n 的数组 arr ，并且索引 0< i< n！我想返回第i个排列。

Given an array arr of size n, and and index 0<i<n! I want to return the ith 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中找到ith排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！