尽可能多地随机播放阵列 [英] Shuffle an array as many as possible

问题描述

我有这样的数组

[0,2,3]

此阵列可能的改组是

[0,2,3], [2,3,0], [3,0,2], [3,2,0], [0,3,2], [2,0,3]

我如何获得这些组合？我目前唯一的想法是

How can I get these combinations? The only idea I have in mind currently is

n = maximum num of possible combinations, coms = []
while( coms.length <= n )
    temp = shuffle( original the array );
    if temp is there in coms
       return
    else 
       coms.push(temp);

但我不认为这是有效的，因为我们盲目地依赖于shuffle方法的均匀分布。

But I do not think this is efficient, as here we are blindly depending on uniform distribution of shuffle method.

这个问题有替代发现吗？

Is there alternative findings for this problem?

推荐答案

首先要注意的是，就元素数量而言，排列的数量增加得非常快（13个元素= 6 bilion permutations），所以任何一种生成它们的算法都会因为足够大的输入数组而在性能上下降。

The first thing to note is that the number of permutations increases very fast with regard to the number of elements (13 elements = 6 bilion permutations), so any kind of algorithm that generates them will deteriorate in performance for a large enough input array.

第二点需要注意的是，因为排列非常大，将它们存储在内存中是很昂贵的，所以你最好使用生成器进行排列，并在生成它们时使用它们。

The second thing to note is that since the number of permutations is very large, storing them in memory is expensive, so you're way better off using a generator for your permutations and doing stuff with them as they are generated.

需要注意的第三点是递归算法会带来很大的开销，所以即使你找到一个递归的解决方案，你也应该努力获得一个非递归的解决方案。如果存在递归解，则获取非递归解决方案总是可行的，但这可能会增加代码的复杂性。

The third thing to note is that recursive algorithms bring a large overhead, so even if you find a recursive solution, you should strive to get a non-recursive one. Obtaining a non-recursive solution if a recursive one exists is always possible, but it may increase the complexity of the code.

我为你写了一个非递归的实现，基于Steinhaus-Johnson-Trotter算法（ http：/ /en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm ）

I have written a non recursive implementation for you, based on the Steinhaus–Johnson–Trotter algorithm (http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm)

function swap(arr, a,b){
  var temp = arr[a];
  arr[a]=arr[b];
  arr[b]=temp;
}

function factorial(n) {
  var val = 1;
  for (var i=1; i<n; i++) {
    val *= i;
  }
  return val;
}


function permute(perm, func){
  var total = factorial(perm.length);

  for (var j=0, i=0, inc=1;  j<total;  j++, inc*=-1, i+=inc) {

    for (; i<perm.length-1 && i>=0; i+=inc) {
      func.call(perm);
      swap (perm, i, i+1);
    }  

    func.call(perm);

    if (inc === 1) {
      swap(perm, 0,1);
    } else {
      swap(perm, perm.length-1, perm.length-2);
    }
  }
}

console.clear();

count = 0;
permute([1,2,3,4,5,6], function(){console.log(this); count++;});

console.log('There have been ' + count + ' permutations');

http://jsbin.com/eXefawe/2/edit

这篇关于尽可能多地随机播放阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！