从数组中获取 n 个不重叠的 m 大小的样本

Question

给定一个数组，我如何从中提取 n 个大小为 m 的非重叠随机样本？

例如，给定数组：

const arr = [1, 2, 3, 4, 5, 6, 7, 8];

调用 sample(arr, 3, 2) 例如 return [[7, 8], [4, 5], [2, 3]]，调用 sample(arr, 2, 4) 必然 return [[1, 2, 3, 4], [5, 6, 7, 8]，调用 sample(arr, 5, 2) 会抛出错误。

编辑 - 也许这在最初的问题中并不清楚：样本应该是连续元素的列表。这就是为什么 sample(arr, 2, 4) 只能 return [[1, 2, 3, 4], [5, 6, 7, 8] 而不能 [[2, 3, 1, 6], [5, 4, 7, 8]，例如

Answer 1

你可以使用贪心算法，从打乱后的数组中取出 m-sized n 个元组：

const arr = [2, 1, 3, 4, 5, 6, 7, 8];
function sample(arr, length, size){
  if(arr.length < length*size)
    throw new Error("too short");
  arr.sort(() => Math.random() - 0.5);
  let res = [];
  for(let i = 0; i < length; i++) res.push(arr.slice(i*size, i*size+size));
  return res;
}
console.log(sample(arr, 2, 4));

Answer 2

我认为最好的实现方式是先洗牌。这是我的两分钱：

function shuffle(array){
  let a = array.slice(), i = a.length, n, h;
  while(i){
    n = Math.floor(Math.random()*i--); h = a[i]; a[i] = a[n]; a[n] = h;
  }
  return a;
}
function sample(array, chunks, count){
  const r = [], a = shuffle(array);
  for(let n=0; n<chunks; n++){
    r.push(a.splice(0, count));
  }
  return r;
}
const arr = [1, 2, 3, 4, 5, 6, 7, 8];
console.log(sample(arr, 3, 2)); console.log(sample(arr, 2, 4));

Answer 3

您可以先创建一个格式为 return 值的列表：

[ 1,  2,  3,  4,  5,  6,  7,  8]
[<---->, <---->, <---->, <>, <>] // sample(array, 3, 2)
[<------------>, <------------>] // sample(array, 2, 4)

这些格式数组可以使用以下长度写出：

[1, 2, 3, 4, 5, 6, 7, 8]
[   2,    2,    2, 1, 1] // sample(array, 3, 2)
[         4,          4] // sample(array, 2, 4)

然后打乱格式数组以获得随机样本选择：

[1, 2, 3, 4, 5, 6, 7, 8]
[   2, 1,    2,    2, 1] // sample(array, 3, 2)
[         4,          4] // sample(array, 2, 4)

然后对于格式数组的每个元素，从输入数组中删除前 n 个元素。然后存储它们，除非它是填充物（放入一个大小的块以达到数组长度）。

[1, 2, 3, 4, 5, 6, 7, 8]
[[1,2], [4,5], [6,7]]  // sample(array, 3, 2)
[[1,2,3,4], [5,6,7,8]] // sample(array, 2, 4)

最后洗牌结果样本。

[1, 2, 3, 4, 5, 6, 7, 8]
[[4,5], [1,2], [6,7]]  // sample(array, 3, 2)
[[5,6,7,8], [1,2,3,4]] // sample(array, 2, 4)

const arr = [1, 2, 3, 4, 5, 6, 7, 8];
console.log(sample(arr, 3, 2));
console.log(sample(arr, 2, 4));
console.log(sample(arr, 5, 2));

function randomInt(limit) {
  return Math.floor(Math.random() * limit);
}

function shuffle(array) {
  for (let limit = array.length; limit > 0; --limit)
    array.push(...array.splice(randomInt(limit), 1));
}

function sample(array, sampleCount, sampleLength) {
  let elementCount = sampleCount * sampleLength;
  if (elementCount > array.length)
    throw "invalid sampleCount/sampleLength arguments";
    
  const filler = {valueOf: () => 1};
  const fillerCount = array.length - elementCount;
  const lengths = Array.from(
    {length: sampleCount + fillerCount},
    (_, i) => i < sampleCount ? sampleLength : filler
  );

  shuffle(lengths);
  const samples = Array.from(array);
  for (const length of lengths) {
    const sample = samples.splice(0, length);
    if (length === filler) continue;
    samples.push(sample);
  }
  shuffle(samples);
  
  return samples;
}

请注意 === 在 length === filler 中很重要。如果您使用 ==，filler 也等于 1。这将与 sample(array, 5, 1) 之类的调用冲突，其中每个样本长度为 1.

const filler = {valueOf: () => 1};

console.log("1 == filler       //=>", 1 == filler);
console.log("2 == filler       //=>", 2 == filler);
console.log("filler == filler  //=>", filler == filler);
console.log("1 === filler      //=>", 1 === filler);
console.log("2 === filler      //=>", 2 === filler);
console.log("filler === filler //=>", filler == filler);

Answer 4

您可以使用 Rando.js (which is cryptographically secure), map, and splice 轻松做到这一点。只需使用 randojs 的 randoSequence 函数来打乱提供的数组并从打乱后的数组中拼接 n 大小-m 数组以获得我们需要的一切 return。如果提供的数组值太少，我们 return 后面的数组会更短。

function sample(arr, n, m){
  arr = randoSequence(arr).map(i => i.value), sample = [];
  for(var i = 0; i < n; i++) sample[i] = arr.splice(-m);
  return sample;
}

console.log(sample([1, 2, 3, 4, 5, 6, 7, 8], 3, 2));

<script src="https://randojs.com/2.0.0.js"></script>

从数组中获取 n 个不重叠的 m 大小的样本

Get n non overlapping m-sized samples from an array

javascript

arrays

random

sample