programa de lucha oneliner

StackOverflow https://stackoverflow.com/questions/1735561

  •  20-09-2019
  •  | 
  •  

Pregunta

Es esa época del año otra vez que los programadores quieren mezclar una lista de tal manera que ningún elemento reside en su posición original (al menos en los Países Bajos, se celebra Sinterklaas y recoger la paja para decidir quien escribe que un poema). ¿Alguien tiene un buen pitón solo estado para eso?

Por lo tanto, el ejemplo de entrada: range(10)

ejemplo de salida: [2,8,4,1,3,7,5,9,6,0]

salida incorrecto sería [2,8,4,1,3,5,7,9,6,0] porque el 5 está en su posición original. Esto significaría que la persona 5 debe escribir un poema para sí mismo y que es menos divertido.

Editar Muchas personas repiten la tarea con tal de que necesitaba tenga suerte y encontrar que, de hecho, la solución es satisfactoria. Este es un enfoque malo como en la teoría esto puede tomar infinitamente largo. El mejor enfoque es, en efecto sugerido por Bart, pero no puedo conseguir que en un oneliner por una razón u otra ...

editar Por oneliner, me refiero a solo estado . Tal como aparece, Python también es capaz de comprimir varias instrucciones en una sola línea. No sabía eso. En este momento hay muy buenas soluciones utilizando sólo el punto y coma para imitar el comportamiento de varias líneas en una sola línea. Por lo tanto: "¿puede hacerlo en una sola instrucción?"

¿Fue útil?

Solución

He encontrado aleatoria pueden ser objeto de abuso en la solución de este 

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

La distribución no es uniforme sin embargo, esto no era un requisito. 

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

Para una distribución uniforme, esta versión (más largo) se puede utilizar 

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)

¿Cómo funciona?

Aquí está el código para 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]

Tanto las soluciones de trabajo por la orientación de la línea de j = int(random() * (i+1))

La primera (no uniforme) hace efectivamente el trabajo de línea como este 

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

Así que en lugar de un rango de (1..i) obtenemos (0..i-1)

La segunda solución sustituye random() con una función que devuelve siempre 1, y utiliza randint en lugar de int. Así que la línea ahora funciona de la siguiente 

j = randint(0, i - 1)

Otros consejos

Después de barajar la lista de números, dejar que la persona [i]th escribir un poema (y comprar un regalo!) Para la persona [i+1]th en la lista: de esa manera, nunca puede haber alguien que él o ella misma dibuja. Por supuesto, este último debe apuntar a la primera ...

Cambio de todos los elementos de la lista por uno de forma circular, como se sugiere por Bart , es fácil: 

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

En cuanto a una solución aleatoria : en este caso la solicitud de una sola línea no es una buena idea, ya que la función obvia de usar, es decir, random.shuffle , realiza su tarea en su lugar. En otras palabras: tiene un efecto secundario , algo que por lo general se trata de evitar en las listas por comprensión. Hay una forma de evitar esto, aunque, como Paul señala, es decir, mediante el uso de random.sample . El siguiente código muestra dos de una sola línea que utilizan estas funciones (nótese el uso de not shuffle, para trabajar en torno al hecho de que shuffle vuelve 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]

A mí, me quedo con ésta: 

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

Aquí es cómo lo haces con el tiempo O (n) y O (1) de memoria adicional:

código comprensible: 

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 de una sola línea (asume "a" es la matriz): 

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

El código está en rubí, pero sin ninguna duda de que es fácilmente traducible a pitón

Saludos

P.S .: La solución modifica la matriz.

"One-liner" en el tiempo fijo 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

El bucle recoge elementos del índice máximo (len (a) -1) hacia abajo a la siguiente-más pequeño (1). La piscina elección para el elemento k sólo incluye los índices de 0 a k-1; una vez recogido, un elemento no se moverá de nuevo.

Después de la lucha, ningún elemento puede residir en su posición original, ya que:

  • si el elemento j es recogido por alguna ranura i> j, se quedará allí
  • lo contrario, elemento j se intercambiará por algún otro elemento de la ranura i
  • excepto para el elemento en la ranura 0, que se intercambió incondicionalmente con el elemento en la ranura 1 (en la iteración final del bucle) si ya no se ha desplazado.

[editar: esto es lógicamente equivalente a la respuesta de Ruby, creo]

Este es O (N). Tener la importación en los bucles es un poco tonto, pero quería un chiste 

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

Aquí es la distribución de salida cuando L = rango (5) para 100000 muestras 

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

Mi primer programa en Python en mucho tiempo. A diferencia de muchos de los programas antes mencionados, éste toma tiempo 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

Actualizar : Pablo mostró que el programa anterior era incorrecta. Gracias, Paul. Aquí hay una mejor versión diferente del mismo programa: 

s = range(10)
for i in range(9):
    r = random.randrange(i+1, 10)
    s[i], s[r] = s[r], s[i]

print s

Lo sentimos, este no es una sola línea, pero esto funciona 

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

Saludos 

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

(Ok, tengo una línea 0 en allí también ...)

En una 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 es la inversa de v función, por lo v[u[i]+1] es efectivamente el siguiente elemento i en array v.

Aquí hay desplazamiento circular de Stephan202 implementado como una sola línea con un incremento de cambio elegido al azar-: 

from random import randrange; s = range(10); r = randrange(1,len(s)-1); print s[-r:] + s[:-r]
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top