2

又到了一年中的那个时候，程序员想要重新排列一个列表，使得没有任何元素位于其原始位置（至少在荷兰，我们庆祝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在其原始位置。这将意味着第 5 个人必须为自己写一首诗，这不那么有趣。

编辑许多人只要需要就可以重复分配任务，并发现实际上解决方案是令人满意的。这是一种不好的方法，因为理论上这可能需要无限长的时间。Bart 确实提出了更好的方法，但出于某种原因，我无法将其纳入单线...

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

4

11 回答 11

6

我发现 shuffle 可以被滥用来解决这个问题

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)

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

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

j = randint(0, i - 1)
于 2009-11-16T04:14:35.263 回答
5

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

于 2009-11-14T21:02:42.670 回答
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，就地执行其任务。换句话说：它有一个副作用，在列表推导中通常会试图避免这种情况。正如保罗指出的那样，有一种方法可以解决这个问题，即使用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]
于 2009-11-14T21:05:17.223 回答
1

固定 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 的索引；一旦被选中，元素将不会再次移动。

打乱后，任何元素都不能留在原来的位置，因为：

  • 如果为某个插槽 i>j 选择元素 j，它将保留在那里
  • 否则，元素 j 将与插槽 i<j 中的其他元素交换，这些元素将保留在那里
  • 除了 slot 0 中的元素，如果它还没有被替换，它将无条件地与 slot 1 中的元素交换（在循环的最后一次迭代中）。

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

于 2009-11-15T08:59:51.227 回答
1

这个是 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

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

((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)
于 2009-11-15T09:03:43.433 回答
1

以下是使用 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​​ 的，但毫无疑问它很容易翻译成 python

干杯

PS：解决方案修改数组。

于 2009-11-14T22:35:29.047 回答
1

很久以来我的第一个 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

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

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

print s
于 2009-11-14T21:36:16.717 回答
0

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

from random import randrange; s = range(10); r = randrange(1,len(s)-1); print s[-r:] + s[:-r]
于 2009-11-14T22:28:13.647 回答
0

抱歉，这不是单行的，但这有效

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

干杯

于 2009-11-14T21:02:33.000 回答
0 
import random; u = range(10)
while sum(u[i]==i for i in range(10)): random.shuffle(u)

（好吧，我那里也有第 0 行……）

于 2009-11-14T21:05:28.220 回答
0

对于 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]数组中 i 之后的元素也是有效的v。

于 2009-11-14T21:18:21.127 回答