在javascript中查找ith排列

Question

給定一個大小爲n的數組arr，以及索引0<i<n!我想返回第i個排列。

我能寫獲取所有置換的方法：

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

如何修剪它，以獲得遞歸只有一個分支？

Answer 1

您可以使用數組長度的階乘作爲幫助獲取想要的置換。

基本上這個算法計算數組的索引並重新組合結果。

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

Answer 2

這裏的少計算昂貴的答案：跟蹤使用布爾標誌數組所使用的元素。它可能看起來並沒有太大的改進，因爲您仍然需要掃描標誌數組以獲取要查找的元素，從而導致O（N^2）性能。但是，如果利用陣列中元素的佈局，則可能會得到一些改進：

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

      //Instead of using splice() to remove elements that are 
      //already in the permutation, I'll use an array of bit flags 
      //to track used elements. 
      var indexMask = []; 
      indexMask.length = array.length; 
      var indexMaskInit = 0; 
      for(indexMaskInit = 0; indexMaskInit < indexMask.length; 
        indexMaskInit++) { 
       indexMask[indexMaskInit] = true; 
      } 

      array = array.slice(); 
      while(l--) { 
       f = factorial(l); 
       indices.push(Math.floor(n/f)); 
       n %= f; 
      } 

      var toReturn = []; 
      toReturn.length = array.length; 
      //Now, extract the elements using the array of indices. 
      var numUsed; 
      for(numUsed = 0; numUsed < indices.length; numUsed++) { 
       //factIndex is the index in the set of elements that have 
       //not been selected yet. 
       var factIndex = indices[numUsed]; 
       var elementFound = false; 
       //This code searches for the element by assuming that some 
       //elements have already been selected. The number of used 
       //elements can be found using the index of the outer loop. 
       //By counting the number of used elements at the beginning 
       //of the array, it may be possible to calculate an offset 
       //that can be used to find the desired element. 
       if(factIndex > 2 * numUsed) 
       { 
        var offset = 0, scanIndex; 
        //Boundary condition: no elements have been used yet, 
        //in which case we can use factIndex directly. 
        if(numUsed === 0) { 
         elementFound = true; 
        } 
        else { 
         //Loop to 2*numUsed, to avoid a linear search. 
         for(scanIndex = 0; scanIndex < 2 * numUsed; 
           scanIndex++) { 
          if(!indexMask[scanIndex]) { 
           offset++; 
          } 
          //Boundary condition: all used elements have 
          //been found. 
          if(offset >= numUsed) { 
           elementFound = true; 
           break; 
          } 
         } 
        } 
        if(elementFound) { 
         factIndex += offset; 
        } 
       } 
       //This code starts at the end of the array and counts the 
       //number of used elements. 
       else if ((indices.length - 1 - factIndex) > 2 * numUsed) { 
        var offset = 0, scanIndex; 
        //Boundary condition: no elements have been used yet, 
        //in which case we can use factIndex directly. 
        if(numUsed === 0) { 
         elementFound = true; 
        } 
        else { 
         var n = indices.length - 1; 
         //Loop to 2*numUsed, to avoid a linear search. 
         for(scanIndex = n; scanIndex > n - 2 * numUsed; 
           scanIndex--) { 
          if(!indexMask[scanIndex]) { 
           offset++; 
          } 
          //Boundary condition: all used elements have 
          //been found. 
          if(offset >= numUsed) { 
           elementFound = true; 
           break; 
          } 
         } 
        } 
        if(elementFound) { 
         factIndex += (numUsed - offset); 
        } 
       } 
       //If the number of used elements is not much greater than 
       //factIndex, or they do not all cluster at the beginning 
       //of the array, it may be better to run a linear search. 
       if(!elementFound) 
       { 
        var searchIndex = 0, i; 
        for(i = 0; i < indexMask.length; i++) { 
         if(indexMask[i]) { 
          if(searchIndex >= factIndex) { 
           break; 
          } 
          else { 
           searchIndex++; 
          } 
         } 
        } 
        factIndex = i; 
       } 
       toReturn[numUsed] = array[factIndex]; 
       indexMask[factIndex] = false; 
      } 
      return toReturn; 
     } 

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

     var i, l; 
     var array = [1, 2, 3, 4]; 
     //var array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]; 

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