如何从二维矩阵中随机选取N个无重复的行/列或x/y坐标？

问题描述 #

现有二维矩阵示例如下：
data = [["a", "b", "c", "d"], ["e", "g"], ["i", "j", "k"]]
需求是从矩阵中随机选取N个无重复的(x, y)索引坐标，原实现仅支持固定选取2个坐标，需扩展为支持任意合法N的通用方案。

原固定2个坐标的实现代码如下：

const data = [["a", "b", "c", "d"], ["e", "g"], ["i", "j", "k"]];

function combinations(data) {
  const i11 = Math.floor(Math.random() * data.length);
  const i12 = Math.floor(Math.random() * data[i11].length);

  const dataLength = data[i11].length > 1 ? data.length : data.length - 1;

  let i21 = Math.floor(Math.random() * dataLength);
  if (i21 >= i11 && data[i11].length === 1) ++i21;

  const innerDataLength = i21 === i11 ? data[i21].length - 1 : data[i21].length;
  let i22 = Math.floor(Math.random() * innerDataLength);
  if (i21 === i11 && i22 >= i12) ++i22;
  
  return [[i11, i12], [i21, i22]];
}

通用扩展方案 #

这里提供两种适用不同场景的实现：

方案1：全坐标洗牌法（性能稳定，推荐大多数场景使用） #

实现思路：先穷举所有合法坐标，再通过Fisher-Yates洗牌算法打乱顺序，取前N个即可，完全避免重复判断，不会出现极端场景下的性能问题。
代码实现：

// Fisher-Yates 洗牌算法，打乱数组顺序
function shuffle(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}

function getRandomCoordinates(data, n) {
  // 先收集所有合法坐标
  const allCoords = [];
  for (let x = 0; x < data.length; x++) {
    for (let y = 0; y < data[x].length; y++) {
      allCoords.push([x, y]);
    }
  }
  // 校验n的合法性
  if (n > allCoords.length) {
    throw new Error(`选取数量不能超过总坐标数：${allCoords.length}`);
  }
  // 洗牌后取前n个
  return shuffle(allCoords).slice(0, n);
}

测试代码：

const data = [["a", "b", "c", "d"], ["e", "g"], ["i", "j", "k"]];
// 测试选取3个坐标
console.log(getRandomCoordinates(data, 3));

// 10000次重复测试，验证无重复
for (let i = 0; i < 10000; i++) {
  const coords = getRandomCoordinates(data, 3);
  const uniqueStr = new Set(coords.map(c => `${c[0]},${c[1]}`));
  if (uniqueStr.size !== coords.length) {
    console.log('测试失败，出现重复坐标');
  }
}

方案2：随机生成+去重法（适合N远小于总坐标数的场景） #

实现思路：每次随机生成坐标后，通过Set记录已生成的坐标字符串，直到收集到N个不同的坐标，实现非常简单，小N场景下效率更高。
代码实现：

function getRandomCoordinates(data, n) {
  // 先计算总坐标数，校验合法性
  const total = data.reduce((sum, row) => sum + row.length, 0);
  if (n > total) {
    throw new Error(`选取数量不能超过总坐标数：${total}`);
  }
  const result = [];
  const used = new Set();
  while (result.length < n) {
    const x = Math.floor(Math.random() * data.length);
    const y = Math.floor(Math.random() * data[x].length);
    const key = `${x},${y}`;
    if (!used.has(key)) {
      used.add(key);
      result.push([x, y]);
    }
  }
  return result;
}

两种方案选择建议 #

• 如果矩阵总元素量不大，或者N接近总元素量，优先选方案1，性能更稳定
• 如果矩阵非常大，且N远小于总元素量，选方案2，避免生成全量坐标的内存和时间开销

内容的提问来源于stack exchange，提问作者Amine