代码之家 › 专栏 › 技术社区 › Paul

单线性加扰程序

shuffle code-golf python

Paul · 技术社区 · 16 年前

每年的这个时候,程序员都想改变一个列表,使它的原始位置上没有元素(至少在荷兰,我们庆祝 圣尼古拉斯 选择吸管来决定谁写了一首诗)。有人有漂亮的蟒蛇吗 单语句 为了这个?

因此,输入示例: range(10)

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

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

编辑很多人只要有必要就重复这个任务走运并发现其实解决方案是令人满意的。这是一个糟糕的方法,因为理论上这可能需要无限长的时间。巴特确实提出了更好的方法,但我不能因为这样或那样的原因把它放进一行程序中……

编辑我是说一行 单语句 . 如图所示,python还能够在一行中压缩多个语句。我不知道。目前有非常好的解决方案,只使用分号模拟单行上的多行行为。因此:“你能用一句话来表达吗?”

11 回复 | 直到 11 年前

John La Rooy 11 年前

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

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)而不是(1..i)的范围

第二个解决方案取代 random() 函数总是返回1,并使用 randint 而不是 int . 所以这条线现在是这样工作的

j = randint(0, i - 1)

Bart Kiers 16 年前

在整理了数字列表之后,让 [i] 这个人写诗(买礼物!)对于 [i+1] 名单上的人:那样的话,就永远不会有人画他或她自己。当然,最后一个应该指向第一个…

Community Mohan Dere 9 年前

循环移动列表中的每个元素, as suggested by 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]

glebm 16 年前

以下是使用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

干杯

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

comingstorm 16 年前

固定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中的其他元素交换,插槽i<j将留在那里。
除了槽0中的元素外,如果该元素尚未被替换,它将无条件地与槽1中的元素交换(在循环的最终迭代中)。

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

John La Rooy 16 年前

这个是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=100000个样本的范围(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)

Chip Uni 16 年前

很长一段时间内我的第一个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

inspectorG4dget Dillon Benson 16 年前

对不起,这不是一条线,但这行得通

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

干杯

Wim 16 年前

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

(好的,我还有一行0…)

Wim 16 年前

对于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 .

las3rjock 16 年前

以下是Stephan202的循环移位,它以随机选择的移位增量作为一个线性执行:

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