python - 随机拆分列表，在新列表中保持原始顺序

Question

我很难提出我的问题，所以我将通过示例来展示。

x = ['abc', 'c', 'w', 't', '3']
a, b = random_split(x, 3)      # first list should be length 3
# e.g. a => ['abc', 'w', 't']
# e.g. b => ['c', '3']

有没有一种简单的方法可以在保持原始顺序的同时将列表分成两个随机样本？

---

编辑:我知道我可以使用 random.sample 然后重新排序，但我希望有一种简单、简单的单行方法。

编辑 2:这是另一个解决方案，看看您是否可以改进它:

def random_split(l, a_size):
    a, b = [], []
    m = len(l)
    which = ([a] * a_size) + ([b] * (m - a_size)) 
    random.shuffle(which)

    for array, sample in zip(which, l):
        array.append(sample)

    return a, b

编辑 3: 我担心避免排序的原因是在最好的情况下它是 O(N*log(N))。应该有可能得到一个缩放 O(N) 的函数 不幸的是，到目前为止发布的解决方案都没有真正实现 O(N) 虽然，经过一番思考后我找到了一个有效的并且与@PedroWerneck 在性能方面的回答相当。不过，我不能 100% 确定这真的是随机的。

def random_split(items, size):
  n = len(items)
  a, b = [], []
  for item in items:
    if size > 0 and random.random() < float(size)/n:
      b.append(item)
      size -= 1
    else:
      a.append(item)

    n -= 1

  return a, b

Answer 1

我认为不可能在拆分后进行限制且不排序，同时以比采样和重新排序更简单的方式保持随机性。

如果没有限制，它会像 RNG 一样随机，方法是遍历列表，并随机选择要将值发送到的目标列表:

>>> import random
>>> x = range(20)
>>> a = []
>>> b = []
>>> for v in x:
...     random.choice((a, b)).append(v)
... 
>>> a
[0, 2, 3, 4, 6, 7, 10, 12, 15, 17]
>>> b
[1, 5, 8, 9, 11, 13, 14, 16, 18, 19]

如果您可以处理一些偏差，您可以在达到限制时停止追加到第一个列表，并仍然使用上面的解决方案。如果您要处理示例中的小列表，那么在第一个列表长度正确之前重试应该没什么大不了的。

如果您希望它真的是随机的并且能够限制第一个列表的大小，那么您将不得不放弃并重新排序至少一个列表。我认为最接近单行实现的是这样的:

>>> x = range(20)
>>> b = x[:]
>>> a = sorted([b.pop(b.index(random.choice(b))) for n in xrange(limit)])
>>> a
[0, 1, 5, 10, 15, 16, 17]
>>> b
[2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 18, 19]

您必须对 a 进行排序，但 b 保留了顺序。

编辑

现在，您真的必须不惜一切代价避免重新订购吗？发布了许多简洁的解决方案，您的第二个解决方案非常好，但没有一个比以下更简单、更容易和更短:

def random_split(items, size):
    sample = set(random.sample(items, size))
    return sorted(sample), sorted(set(items) - sample)

即使考虑到这两种排序操作，我认为在简单性和效率方面也很难超越后者。考虑一下 Python 的 Timsort 是如何优化的，以及大多数其他方法如何必须对每个列表的 n 项至少迭代一次。

如果你真的必须避免重新排序，我想这个也可以，而且非常简单，但迭代两次:

def random_split(items, size):
    sample = set(random.sample(items, size))
    a = [x for x in items if x in sample]
    b = [x for x in items if x not in sample]
    return a, b

这与 Hexparrot 的解决方案基本相同，使用 senderle 建议的 set(sample) 进行比较 O(1)，并删除冗余索引 sample 和 enumerate 调用。如果您只处理可散列对象，则不需要它。