单线打乱程序

Question

又到了一年中的这个时候，程序员想要对列表进行洗牌，以便没有元素位于其原始位置（至少在荷兰，我们庆祝Sinterklaas，并用吸管来决定谁写了一首诗） 。有没有人有一个很好的Python单一声明？

因此，输入示例：range(10)

输出示例：[2,8,4,1,3,7,5,9,6,0]

错误的输出将为 [2,8,4,1,3,5,7,9,6,0] 因为 5 位于其原始位置。这意味着第五个人必须给自己写一首诗，而这就不那么有趣了。

编辑许多人只是为了幸运而重复作业，并发现事实上解决方案是令人满意的。这是一个糟糕的方法，因为理论上这可能需要无限长的时间。 Bart 确实建议了更好的方法，但由于某种原因我无法将其放入 oneliner...

编辑 通过 oneliner，我的意思是单个语句。看起来，Python 还能够将多个语句压缩在一行上。我不知道。目前有非常好的解决方案，仅使用分号来模拟单行上的多行行为。因此：“你能用一句话来做到这一点吗？”

Answer 1

我发现可以滥用洗牌来解决这个问题。

from random import shuffle
L = ["Anne", "Beth", "Cath", "Dave", "Emma"]
shuffle(L, int=lambda n: int(n - 1))
print L

分布不均匀，但这不是必需的。

#For 100,000 samples

(('Beth', 'Cath', 'Dave', 'Emma', 'Anne'), 13417)
(('Beth', 'Cath', 'Emma', 'Anne', 'Dave'), 6572)
(('Beth', 'Dave', 'Anne', 'Emma', 'Cath'), 3417)
(('Beth', 'Dave', 'Emma', 'Cath', 'Anne'), 6581)
(('Beth', 'Emma', 'Anne', 'Cath', 'Dave'), 3364)
(('Beth', 'Emma', 'Dave', 'Anne', 'Cath'), 6635)
(('Cath', 'Anne', 'Dave', 'Emma', 'Beth'), 1703)
(('Cath', 'Anne', 'Emma', 'Beth', 'Dave'), 1705)
(('Cath', 'Dave', 'Beth', 'Emma', 'Anne'), 6583)
(('Cath', 'Dave', 'Emma', 'Anne', 'Beth'), 3286)
(('Cath', 'Emma', 'Beth', 'Anne', 'Dave'), 3325)
(('Cath', 'Emma', 'Dave', 'Beth', 'Anne'), 3421)
(('Dave', 'Anne', 'Beth', 'Emma', 'Cath'), 1653)
(('Dave', 'Anne', 'Emma', 'Cath', 'Beth'), 1664)
(('Dave', 'Cath', 'Anne', 'Emma', 'Beth'), 3349)
(('Dave', 'Cath', 'Emma', 'Beth', 'Anne'), 6727)
(('Dave', 'Emma', 'Anne', 'Beth', 'Cath'), 3319)
(('Dave', 'Emma', 'Beth', 'Cath', 'Anne'), 3323)
(('Emma', 'Anne', 'Beth', 'Cath', 'Dave'), 1682)
(('Emma', 'Anne', 'Dave', 'Beth', 'Cath'), 1656)
(('Emma', 'Cath', 'Anne', 'Beth', 'Dave'), 3276)
(('Emma', 'Cath', 'Dave', 'Anne', 'Beth'), 6638)
(('Emma', 'Dave', 'Anne', 'Cath', 'Beth'), 3358)
(('Emma', 'Dave', 'Beth', 'Anne', 'Cath'), 3346)

对于均匀分布，可以使用这个（较长）版本

from random import shuffle,randint
L=["Anne", "Beth", "Cath", "Dave", "Emma"]
shuffle(L, random=lambda: 1, int=lambda n: randint(0, n - 2))
print L

# For 100,000 samples

(('Beth', 'Cath', 'Dave', 'Emma', 'Anne'), 4157)
(('Beth', 'Cath', 'Emma', 'Anne', 'Dave'), 4155)
(('Beth', 'Dave', 'Anne', 'Emma', 'Cath'), 4099)
(('Beth', 'Dave', 'Emma', 'Cath', 'Anne'), 4141)
(('Beth', 'Emma', 'Anne', 'Cath', 'Dave'), 4243)
(('Beth', 'Emma', 'Dave', 'Anne', 'Cath'), 4208)
(('Cath', 'Anne', 'Dave', 'Emma', 'Beth'), 4219)
(('Cath', 'Anne', 'Emma', 'Beth', 'Dave'), 4087)
(('Cath', 'Dave', 'Beth', 'Emma', 'Anne'), 4117)
(('Cath', 'Dave', 'Emma', 'Anne', 'Beth'), 4127)
(('Cath', 'Emma', 'Beth', 'Anne', 'Dave'), 4198)
(('Cath', 'Emma', 'Dave', 'Beth', 'Anne'), 4210)
(('Dave', 'Anne', 'Beth', 'Emma', 'Cath'), 4179)
(('Dave', 'Anne', 'Emma', 'Cath', 'Beth'), 4119)
(('Dave', 'Cath', 'Anne', 'Emma', 'Beth'), 4143)
(('Dave', 'Cath', 'Emma', 'Beth', 'Anne'), 4203)
(('Dave', 'Emma', 'Anne', 'Beth', 'Cath'), 4252)
(('Dave', 'Emma', 'Beth', 'Cath', 'Anne'), 4159)
(('Emma', 'Anne', 'Beth', 'Cath', 'Dave'), 4193)
(('Emma', 'Anne', 'Dave', 'Beth', 'Cath'), 4177)
(('Emma', 'Cath', 'Anne', 'Beth', 'Dave'), 4087)
(('Emma', 'Cath', 'Dave', 'Anne', 'Beth'), 4150)
(('Emma', 'Dave', 'Anne', 'Cath', 'Beth'), 4268)
(('Emma', 'Dave', 'Beth', 'Anne', 'Cath'), 4109)

工作原理

这是random.shuffle()的代码，

def shuffle(self, x, random=None, int=int):
    """x, random=random.random -> shuffle list x in place; return None.

    Optional arg random is a 0-argument function returning a random
    float in [0.0, 1.0); by default, the standard random.random.
    """

    if random is None:
        random = self.random
    for i in reversed(xrange(1, len(x))):
        # pick an element in x[:i+1] with which to exchange x[i]
        j = int(random() * (i+1))
        x[i], x[j] = x[j], x[i]

这两种解决方案都以行为目标j = int(random() * (i+1))

第一个（非均匀）有效地使该行像这样工作

j = int(random() * (i + 1) - 1)

所以我们得到 (0..i) 而不是 (1..i) 的范围-1)

第二种解决方案将 random() 替换为始终返回 1 的函数，并使用 randint 代替 int。所以这条线现在像这样工作

j = randint(0, i - 1)

Answer 2

打乱数字列表后，让第 [i] 人为列表中的第 [i+1] 人写一首诗（并买一份礼物！） ：这样，就永远不会有人画他或她自己。当然，最后一个应该指向第一个......

Answer 3

以循环方式将列表中的每个元素移动一位，按照 Bart 的建议，很简单：

>>> def shift(seq):
...     return seq[-1:] + seq[:-1]
... 
>>> shift(range(10))
[9, 0, 1, 2, 3, 4, 5, 6, 7, 8]

至于随机解决方案：在这种情况下，请求单行代码并不是一个好主意，因为要使用明显的函数，即 random.shuffle，就地执行其任务。换句话说：它有一个副作用，这是人们在列表推导式中通常试图避免的事情。不过，正如 Paul 指出的那样，有一种解决方法，即使用 random.sample。以下代码显示了两个使用这些函数的单行代码（请注意使用 not shuffle，以解决 shuffle 返回 None 的事实...）：

>>> from itertools import repeat
>>> from random import shuffle
>>> def shake_it(seq):
...     return next(c for c in repeat(seq[::]) if not shuffle(c) and all(a != b for a, b in zip(seq, c)))
... 
>>> shake_it(range(10))
[7, 9, 0, 2, 6, 8, 5, 1, 4, 3]
>>> 
>>> from itertools import count
>>> from random import sample
>>> def shake_it(seq):
...     return next(c for c in (sample(seq, len(seq)) for _ in count()) if all(a != b for a, b in zip(seq, c)))
... 
>>> shake_it(range(10))
[1, 3, 9, 5, 2, 6, 8, 4, 0, 7]

我自己，我会选择这个：

>>> def shake_it(seq):
...     res = seq[::]
...     while any(a == b for a, b in zip(res, seq)):
...         shuffle(res)
...     return res
... 
>>> shake_it(range(10))
[5, 7, 9, 2, 6, 8, 3, 0, 4, 1]

Answer 4

以下是如何使用 O(n) 时间和 O(1) 额外内存来完成此操作：

可理解的代码：

def shuffle(a)
  n = a.length
  (0..n - 2).each do |i|
    r = rand(n - i - 1) + i + 1
    a[r], a[i] = a[i], a[r]
  end
  a
end

单行代码（假设“a”是数组）：

n = a.length and (0..n - 2).each {|i| r = rand(n - i - 1) + i + 1; a[r], a[i] = a[i], a[r]}

代码是用 ruby​​ 编写的，但毫无疑问它很容易翻译to python

Cheers

P.S.：解决方案修改数组。

Answer 5

固定 O(n) 时间内的“单行”：

import random; a=range(10)  # setup (could read in names instead)
for i in range(len(a)-1,0,-1): j=random.randint(0,i-1); a[j],a[i]=a[i],a[j]
print a  # output

循环从最大索引 (len(a)-1) 到下一个最小索引 (1) 选取元素。元素k的选择池仅包含从0到k-1的索引；一旦选择，元素将不会再次移动。

打乱后，没有元素可以驻留在其原始位置，因为：

• 如果元素 j 被某个槽 i>j 选中，它将保留在那里，
• 否则，元素 j 将与槽 i
• 除了槽 0 中的元素，如果槽 1 中的元素尚未被替换，则该元素将无条件地与槽 1 中的元素（在循环的最后一次迭代中）交换。

[编辑：我认为这在逻辑上等同于 Ruby 答案]

Answer 6

这是 O(N)。在循环中进行导入有点愚蠢，但您想要一个单行程序

L=range(10)
for i in range(1,len(L)):import random;r=random.randint(0,i-1);L[i],L[r]=L[r],L[i]
print L

这是当 L=range(5) 对于 100000 个样本时的输出分布

((1, 2, 3, 4, 0), 4231)
((1, 2, 4, 0, 3), 4115)
((1, 3, 0, 4, 2), 4151)
((1, 3, 4, 2, 0), 4108)
((1, 4, 0, 2, 3), 4254)
((1, 4, 3, 0, 2), 4101)
((2, 0, 3, 4, 1), 4158)
((2, 0, 4, 1, 3), 4177)
((2, 3, 1, 4, 0), 4190)
((2, 3, 4, 0, 1), 4117)
((2, 4, 1, 0, 3), 4194)
((2, 4, 3, 1, 0), 4205)
((3, 0, 1, 4, 2), 4325)
((3, 0, 4, 2, 1), 4109)
((3, 2, 0, 4, 1), 4131)
((3, 2, 4, 1, 0), 4153)
((3, 4, 0, 1, 2), 4081)
((3, 4, 1, 2, 0), 4118)
((4, 0, 1, 2, 3), 4294)
((4, 0, 3, 1, 2), 4167)
((4, 2, 0, 1, 3), 4220)
((4, 2, 3, 0, 1), 4179)
((4, 3, 0, 2, 1), 4090)
((4, 3, 1, 0, 2), 4132)

Answer 7

我很长一段时间以来的第一个 Python 程序。与上述许多程序不同，这个程序需要 O(n) 时间。

s = set(range(10))
r = list()
for i in range(10):
    s2 = s - set([i])
    val = s2.pop()
    r.append(val)
    s.discard(val)

print r

更新：Paul 表明上述程序是不正确的。谢谢，保罗。这是同一程序的一个不同的、更好的版本：

s = range(10)
for i in range(9):
    r = random.randrange(i+1, 10)
    s[i], s[r] = s[r], s[i]

print s

Answer 8

抱歉，这不是一句台词，但这很管用，

import random
def sinterklaas(n):
    l=[]
    for a in range(n):
        l.append(-1)

    i = 0
    while i < 10:
        index = random.randint(0,n-1)
        if l[index] == -1 and index != i:
        l[index] = i
            i += 1

干杯

Answer 9

import random; u = range(10)
while sum(u[i]==i for i in range(10)): random.shuffle(u)

（好吧，我那里也有一行 0...）

Answer 10

对于 O(n) 中的一个：

u=range(10); random.shuffle(u); v=[ u[u[i]] for i in range(10) ]; return [ v[(u[i]+1)%10] for i in u ]

u 是函数 v 的逆函数，因此 v[u[i]+1] 实际上是数组 v 中 i 后面的元素。

Answer 11

下面是 Stephan202 的循环移位，它作为具有随机选择移位增量的单行实现：

from random import randrange; s = range(10); r = randrange(1,len(s)-1); print s[-r:] + s[:-r]