2

プログラマーがリストをシャッフルして、元の位置に要素が存在しないようにしたいのは、今年もその時期です（少なくともオランダでは、シンタークラースを祝い、誰が誰の詩を書くかを決めるためにストローを選びます）。誰かがそのための素晴らしい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が自分自身に詩を書かなければならないことを意味し、それはあまり楽しくありません。

編集多くの人は、幸運に恵まれ、実際に解決策が満足のいくものであることに気付くために、必要なだけ割り当てを繰り返します。理論的にはこれには無限に時間がかかる可能性があるため、これは悪いアプローチです。より良いアプローチは確かにバートによって提案されていますが、私は何らかの理由でそれをワンライナーに入れることができません...

編集ワンライナーとは、単一のステートメントを意味します。表示されているように、Pythonは1行で複数のステートメントを圧縮することもできます。私はそれを知りませんでした。現在、単一行の複数行の動作を模倣するためにセミコロンのみを使用する非常に優れたソリューションがあります。したがって、「1つのステートメントでそれを実行できますか？」

4

11 に答える 11

6

私はシャッフルがこれを解決するために悪用される可能性があることを発見しました

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）を取得します。

2番目のソリューションはrandom()、常に1を返し、randintの代わりにを使用する関数に置き換えられますint。したがって、この行は次のように機能します

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

数字のリストをシャッフルした後、その人にリストの[i]3番目の人のために詩を書かせてください（そしてプレゼントを買ってください！）。[i+1]そうすれば、自分を描く人は決していないでしょう。もちろん、最後のものは最初のものを指している必要があります...

于 2009-11-14T21:02:42.670 に答える
3

Bartが提案しているように、リスト内のすべての要素を循環的に1つずつシフトするのは簡単です。

>>> 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です。次のコードは、これらの関数を使用する2つのワンライナーを示しています（を使用して、 ...を返すnot shuffleという事実を回避することに注意してください）。shuffleNone

>>> 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）時間と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 に答える
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までのインデックスのみが含まれます。一度選択すると、要素は再び移動しません。

スクランブル後、次の理由により、要素を元の位置に配置することはできません。

  • 要素jがスロットi>jで選択された場合、そこにとどまります
  • それ以外の場合、要素jはスロットi <jの他の要素と交換され、そこに留まります。
  • ただし、スロット0の要素は、まだ置き換えられていない場合は、スロット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 に答える
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）の1つの場合：

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 に答える
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 に答える