oneliner scramble program

Question

It's that time of year again that programmers want to shuffle a list such that no element resides on its original position (at least in the Netherlands, we celebrate Sinterklaas and pick straws for deciding who writes who a poem). Does anyone have a nice Python single statement for that?

So, input example: range(10)

Output example: [2,8,4,1,3,7,5,9,6,0]

Wrong output would be [2,8,4,1,3,5,7,9,6,0] because the 5 is at its original position. This would mean that person 5 must write a poem to himself and that is less fun.

edit Many people repeat the assignment just as long as needed to get lucky and find that in fact the solution is satisfactory. This is a bad approach as in theory this can take infinitely long. The better approach is indeed suggested by Bart, but I can't get that into a oneliner for one reason or another...

edit By oneliner, I mean single statement. As it appears, Python is also able to compress multiple statements on a single line. I didn't know that. There are currently very nice solutions only using the semicolon to mimic multiline behaviour on a single line. Hence: "can you do it in a single statement?"

Answer 1

I found shuffle can be abused into solving this

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

The distribution is not uniform however this was not a requirement.

#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)

For a uniform distribution, this (longer) version can be used

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)

How it works

Here is the code for 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]

Both solutions work by targeting the line j = int(random() * (i+1))

The first(non uniform) effectively makes the line work like this

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

So instead of a range of (1..i) we obtain (0..i-1)

The second solution replaces random() with a function that always returns 1, and uses randint instead of int. So the line now works like this

j = randint(0, i - 1)

Answer 2

After shuffling the list of numbers, let the [i]th person write a poem (and buy a present!) for the [i+1]th person in the list: that way, there can never be someone who draws him- or herself. Of course, the last one should point to the first...

Answer 3

Shifting every element in the list by one in a circular manner, as suggested by Bart, is easy:

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

As for a random solution: in this case the request for a one-liner is not such a good idea, since the obvious function to use, namely random.shuffle, performs its task in place. In other words: it has a side effect, something one usually tries to avoid in list comprehensions. There is a way around this though, as Paul points out, namely by using random.sample. The following code shows two one-liners which use these functions (note the use of not shuffle, to work around the fact that shuffle returns 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]

Myself, I'd go with this one:

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

Here is how you do it with O(n) time and O(1) extra memory:

Comprehensible code:

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 one-liner (assumes "a" is the array):

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

The code is in ruby, but without any doubt it's easily translatable to python

Cheers

P.S.: The solution modifies the array.

Answer 5

"One-liner" in fixed O(n) time:

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

The loop picks elements from the maximum index (len(a)-1) down to the next-smallest (1). The choice pool for element k only includes indices from 0 to k-1; once picked, an element will not be moved again.

After the scramble, no element can reside in its original position, because:

• if element j is picked for some slot i>j, it will stay there
• otherwise, element j will be swapped with some other element from slot i<j, which will stay there
• except for the element in slot 0, which will be swapped unconditionally with the element in slot 1 (in the final iteration of the loop) if it has not already been displaced.

[edit: this is logically equivalent to the Ruby answer, I think]

Answer 6

This one is O(N). Having the import in the loops is a bit silly, but you wanted a one liner

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

Here is the output distribution when L=range(5) for 100000 samples

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

My first Python program in a long while. Unlike many of the above programs, this one takes O(n) time.

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

UPDATE: Paul showed that the above program was incorrect. Thanks, Paul. Here's a different, better version of the same program:

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

Sorry this isn't a one-liner, but this works

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

Cheers

Answer 9

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

(Ok, I have a line 0 in there too...)

Answer 10

For one in 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 is the inverse of function v, so v[u[i]+1] is effectively the element following i in array v.

Answer 11

Here's Stephan202's circular shift implemented as a one-liner with a randomly-chosen shift increment:

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