如何在随机选取数组元素的时候避免相邻重复

[akira-cn]

最近，有一个开源项目叫做“狗屁不通文章生成器”受到大家关注。在github上，这个项目已经有超过1.3万人star。

这个项目的功能很简单，就是只要输入一个标题，然后就能生成一大篇看似通顺，实际上废话连篇的文章。

项目原版是用python写的，也有一个简单的JS在线版。我研究了一下，把它改写了一版，对生成的文章做了一点点改进。其中有个问题是这样的，因为这个生成器实际上随机选择句子拼接，但是有可能连续两次或多次选择到相同的句子，这样就会让文章看起来有点鬼畜感：

实际上我们可以在随机选择的时候，改进一下算法，让它不要重复选择上一次选过的句子。

那么问题来了，如何在从数组里随机选择元素的时候避免连续两次选中同一个元素呢？

数组选择随机元素非常简单，基本上一行代码就可以搞定：

function randomPick(arr) {
	return arr[Math.floor(arr.length * Math.random())];
}

但是这样不可避免会产生连续两次选到同样元素的情况。

要避免这个问题，一个最直接的思路是记住上一次选择的元素，判断如果这次选的和上次一样，那就再选一次。

let lastPicked = null;
function randomPick(arr) {
	let picked = null;
	do {
		picked = arr[Math.floor(arr.length * Math.random())];
	} while(picked === lastPicked);
    lastPicked = picked;
	return picked;
}

这样当然可以解决问题，但是这样有两个问题，一是我们要额外用一个变量来保存上一次选过的状态，二是选择重复要重新选，等于变相增加了选取次数。所以这个方案不是特别好。

那么我们能不能换个思路，先把选择过的元素从数组里取出，下次选择的时候再放回去呢？

当然是可以的：

let lastPicked = null;
function randomPick(arr) {
  const idx = Math.floor(arr.length * Math.random());
  let picked;
  if(lastPicked) picked = arr.splice(idx, 1, lastPicked);
  else picked = arr.splice(idx, 1);
  lastPicked = picked[0];
  return lastPicked;
}

但是这样做也有问题，首先，仍然要有一个额外的变量，其次，虽然现在选取次数不再增多，但是splice操作本身也是个O(n)复杂度的操作，所以性能不是特别好。

那么还有什么方式可以解决呢？

我们可以把第二个方案做改进，每次只随机选择数组前n-1项，然后将选出的项直接和数组最后一项交换位置，这样下一次就不会选择到这一项了。

function randomPick(arrs) {
  const len = arrs.length - 1;
  const index = Math.floor(len * Math.random());
  const picked = arrs[index];
  [arrs[index], arrs[len]] = [arrs[len], arrs[index]];
  return picked;
}

这么做了之后，基本上就解决了我们的问题，但是它还有一个小小的缺陷，那就是第一次选择不到数组最末尾的那个元素。不过这个也有办法解决，一种是记录一下第一次调用状态，如果第一次调用时，选择数组所有元素；之后再调用，则选择前n-1项中的元素。这样的缺点是还是需要一个额外变量记录状态。如果不想要这个额外的变量，还有一个办法是抛弃掉第一次随机选择的结果。

function createRandomPicker(arrs) {
	arrs = [...arrs]; // copy 数组，以免修改原始数据
	function randomPick() {
	  const len = arrs.length - 1;
	  const index = Math.floor(len * Math.random());
	  const picked = arrs[index];
	  [arrs[index], arrs[len]] = [arrs[len], arrs[index]];
	  return picked;
	}
	randomPick(); // 抛弃第一次选择结果
	return randomPick;
}

比如上面的代码，用过程抽象的思想，定义一个createRandomPicker的高阶函数，用它来包装一个数组，生成这个数组的随机选取函数。

这么做既不用额外的状态保存，而且还有一个附带的好处，不会破坏原始数组，因为我们对数组做了复制。

以上就是今天分享的内容，这只是生成文章优化的一个小点，还做了另外一些其他的优化，具体可以看Github项目。

关于这一块，还有什么问题或想法，欢迎留言讨论。