programme bousculade oneliner

Question

Il est cette période de l'année que les programmeurs veulent mélanger une liste de telle sorte qu'aucun élément se trouve sur sa position initiale (au moins aux Pays-Bas, nous célébrons Sinterklaas et ramasser des pailles pour décider qui écrit qui un poème). Est-ce que quelqu'un a une belle Python Déclaration unique pour cela?

Ainsi, par exemple l'entrée: range(10)

Exemple de sortie: [2,8,4,1,3,7,5,9,6,0]

sortie incorrect serait [2,8,4,1,3,5,7,9,6,0] parce que le 5 est à sa position d'origine. Cela signifie que la personne 5 doit écrire un poème pour lui-même et qui est moins amusant.

modifier Beaucoup de gens répètent la mission aussi longtemps que nécessaire pour avoir de la chance et constatent que, en fait, la solution est satisfaisante. Cette approche est mauvaise en théorie, cela peut prendre infiniment longue. La meilleure approche est en effet proposée par Bart, mais je ne peux pas obtenir cela dans un oneliner pour une raison ou une autre ...

modifier Par oneliner, je veux dire seule instruction . Comme il apparaît, Python est également capable de compresser plusieurs instructions sur une seule ligne. Je ne savais pas. Il existe des solutions actuellement très agréables en utilisant uniquement le point-virgule pour imiter le comportement multiligne sur une seule ligne. Par conséquent: « pouvez-vous faire dans une seule déclaration? »

Answer 1

Je trouve lecture aléatoire peuvent être abusés dans la résolution de ce

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

La distribution n'est pas uniforme mais cela n'a pas été une exigence.

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

Pour une distribution uniforme, cette version (plus) peut être utilisé

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)

Comment ça marche?

Voici le code pour 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]

Les deux solutions de travail en ciblant la j = int(random() * (i+1)) ligne

La première (non uniforme) fait efficacement le travail de ligne comme ceci

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

Ainsi, au lieu d'une gamme de (1..i), on obtient (0..i-1)

La deuxième solution remplace random() avec une fonction qui retourne toujours 1 et utilise randint au lieu de int. Ainsi, la ligne fonctionne maintenant comme ceci

j = randint(0, i - 1)

Answer 2

Après brassage la liste des numéros, laissez la personne [i]th écrire un poème (et acheter un cadeau!) Pour la personne [i+1]th dans la liste: de cette façon, il ne peut jamais être quelqu'un qui tire lui-même. Bien sûr, le dernier doit pointer vers le premier ...

Answer 3

Déplacement chaque élément dans la liste par une d'une manière circulaire, comme suggéré par Bart , est facile:

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

En ce qui concerne une solution aléatoire : dans ce cas, la demande d'un revêtement n'est pas une bonne idée, puisque la fonction évidente à utiliser, à savoir random.shuffle , exécute sa tâche en place. En d'autres termes: il a une effet secondaire , quelque chose qu'on essaie généralement d'éviter dans la liste compréhensions. Il y a une façon de contourner cela mais, comme Paul souligne, à savoir en utilisant random.sample . Le code suivant montre deux one-liners qui utilisent ces fonctions (notez l'utilisation de not shuffle, de travailler autour du fait que revient 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]

Moi-même, je partirais avec celui-ci:

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

Voici comment vous le faites avec O (n) et O (1) mémoire supplémentaire:

Code Compréhensible:

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 (assume "a" est la matrice) d'un liner:

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

Le code est en rubis, mais sans aucun doute il est facilement traduisible à python

Vive

P.S .: La solution modifie le tableau.

Answer 5

"One-liner" en fixe 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

La boucle choisit des éléments de l'indice maximum (len (a) -1) jusqu'à la prochaine plus petite (1). La piscine de choix pour k élément ne comprend que des indices de 0 à k-1; une fois choisi, un élément ne sera pas déplacé à nouveau.

Après la bousculade, aucun élément ne peut résider dans sa position d'origine, parce que:

• si l'élément j est choisi pour une tranche i> j, il y restera
• sinon, l'élément j sera remplacée par un autre élément de la fente i
• à l'exception de l'élément à l'emplacement 0, qui sera échangé sans condition avec l'élément dans la fente 1 (dans la dernière itération de la boucle) si elle n'a pas déjà été déplacé.

[edit: ceci est logiquement équivalent à la réponse Ruby, je pense]

Answer 6

Celui-ci est O (N). Ayant l'importation dans les boucles est un peu stupide, mais vous vouliez une seule ligne

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

Voici la distribution de sortie lorsque L = portée (5) pour les échantillons 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

Mon premier programme Python depuis longtemps. Contrairement à la plupart des programmes ci-dessus, celui-ci prend 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

UPDATE : Paul a montré que le programme ci-dessus était incorrect. Merci, Paul. Voici une autre, une meilleure version du même programme:

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

Désolé, ce n'est pas une seule ligne, mais cela fonctionne

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

Vive

Answer 9

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

(Ok, j'ai une ligne 0 là aussi ...)

Answer 10

Pour une en 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 est l'inverse de la fonction v, de sorte v[u[i]+1] est effectivement l'élément suivant dans i v de réseau.

Answer 11

Voici décalage circulaire de Stephan202 mis en œuvre comme une seule ligne avec un incrément de décalage aléatoire choisi:

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