برنامج Scramble Oneliner

Question

إنه في ذلك الوقت من السنة مرة أخرى أن المبرمجين يريدون خلط ورق اللعب قائمة بحيث لا يوجد عنصر يقيم في موقفه الأصلي (على الأقل في هولندا، نحتفل sinterklaas. واختيار القش لتحديد من يكتب من قصيدة). هل لدى أي شخص بيثون لطيف بيان واحد من أجل هذا؟

لذلك، مثال الإدخال: range(10)

مثال الإخراج: [2,8,4,1,3,7,5,9,6,0]

الناتج الخطأ سيكون [2,8,4,1,3,5,7,9,6,0] بسبب ال 5 في موقفه الأصلي. هذا يعني أن الشخص 5 يجب أن يكتب قصيدة لنفسه وهذا أقل متعة.

تعديل كثير من الناس يكررون المهمة طالما اللازمة ل كن محظوظا وتجد ذلك في الواقع الحل مرض. هذا نهج سيء كما هو بالنظرية، هذا يمكن أن يستغرق وقتا طويلا بلا حدود. اقترح نهج أفضل بالفعل من قبل بارت، لكنني لا أستطيع الحصول على ذلك في مشتعل لسبب أو آخر ...

تعديل بواسطة Oneliner، أقصد بيان واحد. وبعد كما يبدو، فإن بيثون قادر أيضا على ضغط بيانات متعددة على سطر واحد. لم أكن أعرف ذلك. هناك حاليا حلول لطيفة للغاية تستخدم فقط الفاصلة المنقوطة إلى سلوك MIMIC Multiline في سطر واحد. وبالتالي: "يمكنك أن تفعل ذلك في بيان واحد؟"

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)

لذلك بدلا من مجموعة من (1..i) نحصل على (0......

الحل الثاني يحل محل random() مع وظيفة تعود دائما 1، ويستخدم randint بدلاً من int. وبعد لذلك يعمل الخط الآن مثل هذا

j = randint(0, i - 1)

Answer 2

بعد خلط قائمة الأرقام، دع [i]الشخص الذي يكتب قصيدة (وشراء هدية!) ل [i+1]الشخص في القائمة: بهذه الطريقة، لا يمكن أن يكون هناك شخص يرسمه أو نفسها. بالطبع، آخر واحد يجب أن يشير إلى الأول ...

Answer 3

تحويل كل عنصر في القائمة من قبل واحد بطريقة دائرية، كما اقترح بارت, ، سهل:

>>> 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]

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]}

الرمز هو في روبي، ولكن دون أي شك هو الراحة بسهولة إلى بيثون

هتافات

ملاحظة: الحل يعدل الصفيف.

Answer 5

"بطانة واحدة" في وقت ثابت O (ن)

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؛ بمجرد الاختيار، لن يتم نقل عنصر مرة أخرى.

بعد التدافع، لا يمكن أن يقيم أي عنصر في موقعه الأصلي، لأنه:

• إذا تم اختيار Element J لبعض الفتحات I> J، فستبقى هناك
• خلاف ذلك، سيتم تبديل عنصر J مع عنصر آخر من فتحة أنا
• باستثناء العنصر في الفتحة 0، والذي سيتم تبديله دون قيد أو شرقا مع العنصر في الفتحة 1 (في التكرار النهائي للحلقة) إذا لم يتم تهجيره بالفعل.

تحرير: هذا يعادل منطقيا إجابة Ruby، وأعتقد

Answer 6

هذا واحد هو O (ن). وجود الاستيراد في الحلقات سخيفة بعض الشيء، لكنك تريد بطانة واحدة

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 = المدى (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

أول برنامج بيثون الأول منذ فترة طويلة. على عكس العديد من البرامج أعلاه، يأخذ هذا واحد O (ن) الوقت.

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

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 (ن):

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.

Answer 11

تم تنفيذ تحول Stephan202 الدائري هنا كأبطانة واحدة مع زيادة تحول مختارة عشوائيا:

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