3

我很难提出我的问题，所以我将举例说明。

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
4

7 回答 7

4

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

如果没有限制，它将与 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 调用。如果您只处理可散列对象，则不需要它。

于 2012-04-21T04:43:34.617 回答
4

这种方法怎么样。来自索引的随机样本，如果 in和if not in ，则从两个列表推导中返回两个列表：

def random_split(lst, size):
    import random
    samp = set(random.sample(xrange(len(lst)),size))
    return ([v for i,v in enumerate(lst) if i in samp],
            [v for i,v in enumerate(lst) if i not in samp])

x = ['abc', 'c', 'w', 't', '3']

print random_split(x,3)

返回

(['abc', 't', '3'], ['c', 'w']) #random and retains order
于 2012-04-21T06:27:57.543 回答
3

好的，有很多有趣的建议，其中一个我无意中在这篇文章的先前版本中重复了。但是这里有两个没有以这种确切形式呈现的解决方案：

def random_split(seq, n):
    indices = set(random.sample(range(len(seq)), n))
    left_right = ([], [])
    for n, x in enumerate(seq):
        left_right[n not in indices].append(x)
    return left_right

这只会遍历列表并产生列表的均匀随机分区，保持顺序。这是对六角鹦鹉建议的改进，这是我无意中复制的建议。您可以使用三元运算符和两个单独的列表，但这对我来说似乎有点干净。Usingenumerate允许它处理不可散列的项目，以及具有重复项的序列。

def random_split(seq, n):
    rnd_bools = random.sample((0,) * n + (1,) * (len(seq) - n), len(seq))
    left_right = ([], [])
    for b, x in zip(rnd_bools, seq):
        left_right[b].append(x)
    return left_right

这个我觉得对。这是 Jacob Eggers 对该问题的第二次编辑的改进。它并没有太大的不同，但是它不是对列表列表进行打乱，而是对布尔列表进行打乱。我认为乍一看更容易理解。它通过 using 避免了 2-line shuffle random.sample，它会生成一个副本；有些人可能更喜欢 2-line shuffle，它很容易被替换。

请注意，这两者都基于相同的基本原理：生成一个布尔序列并使用它们来索引一个left_right元组；通过预先生成布尔列表，第一个可以很容易地与第二个几乎相同。

最后，第二个解决方案可以转换成一个非常丑陋的“单线”，我不推荐 - 显然 - 但我在这里展示它以供您娱乐和嘲笑：

random_split = lambda seq, n: reduce(lambda a, b: (a[0] + ([b[1]] if not b[0] else []), a[1] + ([b[1]] if b[0] else [])), zip(random.sample((0,) * n + (1,) * (len(seq) - n), len(seq)), seq), ([], []))
于 2012-04-21T22:24:57.817 回答
1

这是您可以转换为函数的成绩单： 

>>> a = [10,20,30,40,50,60]
>>> keep = sorted(random.sample(range(len(a)),3))
>>> keep
[0, 3, 4]
>>> ([a[i] for i in keep], [a[i] for i in range(len(a)) if i not in keep])
([10, 40, 50], [20, 30, 60])
于 2012-04-21T05:03:57.990 回答
1

随机排序主题的变体......

def random_split(L, size):
    index = range(len(L))
    random.shuffle(index)
    return ([L[i] for i in sorted(index[:size])],
            [L[i] for i in sorted(index[size:])])
于 2012-04-21T14:31:25.980 回答
0

我猜测您的 random_split 不应该给出重复元素。

如果您在原始列表中没有任何重复项，这将作为您在原始帖子中使用的单行，但它使用排序。这是一种非常简单但效率低下的方法：

import random

x = ['abc', 'c', 'w', 't', '3']

def random_split(x, n):
    k = x[:]
    random.shuffle(k)
    yield sorted(k[:n], key = x.index)
    yield sorted(k[n:], key = x.index)

a, b = random_split(x, 3)

结果示例：

>>> a
['c', 'w', 't']
>>> b
['abc', '3']
于 2012-04-21T05:29:19.290 回答
0

这里有几行：

from random import sample
x = ['abc', 'c', 'w', 't', '3']
sample_size = len(x) // 2

sample_set = set(sample(x, sample_size))
split_list = [[x[i] for i in subset] for subset in (sorted(sample_set), sorted(set(x) - sample_set))]
于 2012-04-21T16:27:40.013 回答