随机数组所以没有两个键在同一个位置

Question

我工作的一个秘密圣诞老人应用程序,我被洗牌了用户的数组,然后使用一个通过它迭代匹配达人for圈,然后调用函数,如果第一阵列中的一个关键是相同的关键在第二个数组中.但是,这在应用程序中执行时会导致一些问题,并导致它有时会挂起.另外,这个函数的理论最大执行时间是无限的,我想避免的.

是否有一种方法来重新排列一个数组,以便没有两个键位于同一位置而不重复该函数,如果它失败了？

我正在使用的代码(未在应用程序本身中实现)如下:

//underscore utility library
var _ = require('underscore');
//pretty console colors
var colors = require('colors');
//fs module to write to file
var fs = require('fs');
//path utilities
var path = require('path');
//arr will contain the UIDs of the participants.
var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50];
//sArr will be the pairings.
var sArr = [];
//plain-text data
var writeMe = '';
//i for an i
var i = 0;
//var declaration to shut up the linter
var justDoIt;
var writeIt;
var shuffleIt;
var checkIt;

var shuffleIt = function () {
  //use Underscore.js' shuffle function on the array.
  sArr = _.shuffle(arr);
};

var checkIt = function () {
  for (i = 0; i < arr.length; i++) {
    //check to make sure that there are no duplicates. 
    //otherwise, politely complain
    if (arr[i] === sArr[i]) {
      //well fuck. both are the same. Let's do it again
      console.log(arr[i] + "=>" + sArr[i]);
      console.log("ERROR".red + "\n==================\n");
      justDoIt();
      return;
    }
    //otherwise, print current pairing to console
    writeMe += arr[i] + '=>' + sArr[i] + "\n";
    console.log(arr[i] + '=>' + sArr[i]);
  }
  //we're done!
  console.log("All good!".green);
  //let's write it out
  writeIt();
  return;
};

var justDoIt = function () {
  //roll it
  shuffleIt();
  //check it
  checkIt();
};

var writeIt = function () {
  //write it to a file
  fs.writeFileSync(path.join(__dirname, 'pairings.txt'), writeMe);
};
//init
justDoIt();

Answer 1

没有元素处于原始位置的重新排列的一般术语是紊乱,这是一个令人着迷的问题.

你正在寻找一个无偏差(均匀随机),非拒绝(不是"重复直到它工作")算法的随机紊乱.

这不是微不足道的.

这是一个这样的算法(编辑:它似乎没有偏见):

function derangementNumber(n) {
    if(n == 0) {
        return 1;
    }
    var factorial = 1;
    while(n) {
        factorial *= n--;
    }
    return Math.floor(factorial / Math.E);
}

function derange(array) {
    array = array.slice();
    var mark = array.map(function() { return false; });
    for(var i = array.length - 1, u = array.length - 1; u > 0; i--) {
        if(!mark[i]) {
            var unmarked = mark.map(function(_, i) { return i; })
                .filter(function(j) { return !mark[j] && j < i; });
            var j = unmarked[Math.floor(Math.random() * unmarked.length)];

            var tmp = array[j];
            array[j] = array[i];
            array[i] = tmp;

            // this introduces the unbiased random characteristic
            if(Math.random() < u * derangementNumber(u - 1) /  derangementNumber(u + 1)) {
                mark[j] = true;
                u--;
            }
            u--;
        }
    }
    return array;
}

var a = [1, 2, 3, 4, 5, 6, 7];
derange(a);

你可以看看这篇论文,这个幻灯片,或者这个数学问题.