Блог

Учитывая массив, как я могу извлечь из него n неперекрывающиеся случайные выборки размера m ?

Например, учитывая массив:

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

вызов sample(arr, 3, 2) , например, вернул бы [[7, 8], [4, 5], [2, 3]] , вызов sample(arr, 2, 4) обязательно вернул бы [[1, 2, 3, 4], [5, 6, 7, 8] , а вызов sample(arr, 5, 2) выдал бы ошибку.

РЕДАКТИРОВАТЬ — Возможно, это было неясно в первоначальном вопросе: выборки должны быть списками смежных элементов. Вот почему sample(arr, 2, 4) может возвращать только [[1, 2, 3, 4], [5, 6, 7, 8] , а не [[2, 3, 1, 6], [5, 4, 7, 8] , например.

Вы могли бы начать с создания списка с форматом возвращаемого значения:

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

Затем для каждого элемента массива format удалите первые 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);  

вы можете использовать жадный алгоритм и взять n кортежей размером m из перетасованного массива:

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

Я думаю, что лучшей реализацией было бы сначала перемешать. Вот мои два цента:

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

Вы можете сделать это с помощью Rando.js (что криптографически безопасно), сопоставить и склеить довольно легко. Просто используйте randoSequence функцию randojs, чтобы перетасовать предоставленный массив и склеить из этого перетасованного массива массивы n размера m , чтобы получить все, что нам нужно для возврата. Если в предоставленном массиве слишком мало значений, более поздние массивы, которые мы вернем, будут просто короче.

 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>