随机播放数组，因此没有两个键位于同一位置

Shuffle Array So No Two Keys Are in the Same Location

本文关键字：两个 键位 位置 于同一 数组 播放 随机      更新时间：2023-09-26

我正在开发一个秘密圣诞老人应用程序，我通过随机排列用户数组来匹配人员，然后使用 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();

没有元素处于其原始位置的重排的一般术语是一种紊乱，这是一个有趣的问题。

您正在寻找一种无偏（均匀随机）、非拒绝（不是"重复直到它起作用"）算法来随机紊乱。

这不是小事。

这是一种这样的算法（编辑：它似乎不是公正的）：

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

你也可以看看这篇论文，这张幻灯片，或者这道数学题。

正如注释中指出的那样，通过洗牌初始数组，然后将其移动 1（或任何小于数组长度的数字）将产生随机排序。

示例代码：

// Underscore Utility Library, since I was using this anyway.
var _ = require('underscore');
// Example shuffle: [4,2,1,9,5,8,3,7,6]
var arr = _.shuffle([1,2,3,4,5,6,7,8,9]);
var sArr = _.union(_.rest(arr), [_.first(arr)]);
// Log out pairs.
for (i = 0; i < arr.length; i++) {
    console.log(arr[i] + ' --> ' + sArr[i]);
}

这方面的一个示例输出是：

6 --> 3
3 --> 1
1 --> 2
2 --> 4
4 --> 7
7 --> 5
5 --> 8
8 --> 9
9 --> 6

此解决方案的警告是，它不是真正随机的。它将创造某些不可能的情况。例如，使用此解决方案，两个用户不可能相互获取。如果 6 已经有 3，则 3 不能有 6。它创造了一个链效应，将确保随机排序，并且在不知道以前的配对的情况下，每个收件人配对将是不可预测的，但它不会是真正的随机。

以下内容看起来相当随机，并保证成员不会返回到其原始位置：

// Return a new array that is a deranged version of arr
// Guarantee that no member retains its original position
function derange(arr) {
  // Make a copy of arr
  var c = arr.slice();
  // If arr.length is < 2, return copy
  if (c.length < 2) {
    return c;
  }
  var result = [];
  var idx, i, iLen;
  // Keep track of whether last member has been moved
  var lastMoved = false;
  // Randomly remove a member of c, with conditions...
  for (i=0, iLen=c.length - 1; i<iLen; i++) {
    // If get down to final two and last hasn't been moved,
    // swap last two and append to result
    if (c.length == 2 && !lastMoved) {
      result = result.concat(c.reverse().splice(0,2))
      break;
    }
    // Otherwise, select a remaining member of c
    do {
      idx = Math.random() * c.length | 0;
    // But make sure it's not going back in the same place
    } while (arr.indexOf(c[idx]) == result.length)
    // Add member to result
    result.push(c.splice(idx, 1)[0]);
    // Remember if last was just moved
    lastMoved = lastMoved || idx == c.length;
  }
  // Add the last member, saves a do..while iteration about half the time
  if (c.length) result.push(c[0]);
  return result;
}

一些结果：

console.log(derange([1,2,3,4,5,6]));
 [6, 4, 2, 5, 3, 1]
 [4, 1, 2, 5, 6, 3]
 [5, 4, 2, 6, 1, 3]
 [4, 5, 2, 3, 6, 1]
 [4, 6, 1, 5, 2, 3]
 [5, 6, 1, 3, 4, 2]
 [2, 4, 6, 1, 3, 5]
 [2, 1, 4, 5, 6, 3]
从

Math.random 中排除某些值是不可能的，所以如果你得到一个你不喜欢的值，别无选择，只能得到另一个。所以做..while 循环用于确保最初位于索引 i 的成员不会移动到新索引 i。但是，此类碰撞应降至最低。除了使用 indexOf 之外，优化原始值的查找也会很好。也许这只对非常大的数组很重要。

如果它到达最后两个成员并且原始数组的最后一个成员尚未移动，它将简单地反转然后附加最后两个成员，这是此时唯一可能的结果。

相关文章：