"Josefo-problema" usando la lista en Python

Question

quería saber si será posible resolver el problema utilizando Josepheus lista en Python.

En términos simples problema Josefo se trata de encontrar una posición en una disposición circular que sería segura si las ejecuciones se manejaron a cabo utilizando un parámetro de salto que se conoce de antemano.

Por ejemplo: dada una disposición circular como [1,2,3,4,5,6,7] y un parámetro de omisión de 3, las personas se ejecutarán en el orden 3,6,2,7,5,1 y la posición 4 sería la caja fuerte.

que han estado tratando de resolver esto utilizando la lista desde hace algún tiempo, pero las posiciones de índice se vuelve difícil para mí de manejar.

a=[x for x in range(1,11)] 
skip=2 
step=2 
while (len(a)!=1): 
    value=a[step-1] 
    a.remove(value) 
    n=len(a) 
    step=step+skip 
    large=max(a) 
    if step>=n:   
     diff=abs(large-value) 
     step=diff%skip 
    print a 

Actualizado la pregunta con fragmento de código, pero no creo que mi lógica es correcta.

Answer 1

En pocas palabras, se puede utilizar para eliminar list.pop(i) cada víctima (y obtener su carné de identidad) en un bucle. Entonces, solo tenemos que preocuparnos de ajustar los índices, lo cual puede hacer simplemente tomando la modificación del índice omitido del número de prisioneros restantes.

Así pues, la solución se convierte en cuestión

def josephus(ls, skip): 
    skip -= 1 # pop automatically skips the dead guy 
    idx = skip 
    while len(ls) > 1: 
     print ls.pop(idx) # kill prisoner at idx 
     idx = (idx + skip) % len(ls) 
    print 'survivor: ', ls[0] 

salida de la prueba:

>>> josephus([1,2,3,4,5,6,7], 3) 
3 
6 
2 
7 
5 
1 
survivor: 4 

Answer 2

In [96]: def josephus(ls, skip): 
    ...:  from collections import deque 
    ...:  d = deque(ls) 
    ...:  while len(d)>1: 
    ...:   d.rotate(-skip) 
    ...:   print(d.pop()) 
    ...:  print('survivor:' , d.pop()) 
    ...:  

In [97]: josephus([1,2,3,4,5,6,7], 3) 
3 
6 
2 
7 
5 
1 
survivor: 4 

Si no desea calcular el índice, puede utilizar la estructura de datos deque.

Answer 3

Ésta es mi solución a su pregunta:

# simple queue implementation<ADT> 
class Queue: 
    def __init__(self): 
     self.q = [] 
    def enqueue(self,data): 
     self.q.insert(0,data) 
    def dequeue(self): 
     self.q.pop() 
    def sizeQ(self): 
     return len(self.q) 
    def printQ(self): 
     return self.q 


lists = ["Josephus","Mark","Gladiator","Coward"] 
to_die = 3 
Q = Queue() 
# inserting element into Q 
for i in lists: 
    Q.enqueue(i) 
# for size > 1 
while Q.sizeP() > 1: 
    for j in range(1,3): 
# every third element to be eliminated 
     Q.enqueue(Q.dequeue()) 
    Q.dequeue() 
print(Q.printQ()) 

Answer 4

def Last_Person(n): 
    person = [x for x in range(1,n+1)] 
    x = 0 
    c = 1 
    while len(person) > 1: 
     if x == len(person) - 1: 
      print("Round ", c, "- Here's who is left: ", person, "Person ", person[x], "killed person", person[0]) 
      person.pop(0) 
      x = 0 
      c = c+1 
     elif x == len(person) - 2: 
      print("Round ", c, "- Here's who is left: ", person, "Person ", person[x], "killed person", person[x + 1]) 
      person.pop(x+1) 
      x = 0 
      c = c + 1 
     else: 
      print("Round ", c, "- Here's who is left: ", person, "Person ", person[x], "killed person", person[x + 1]) 
      person.pop(x + 1) 
      x = x + 1 
      c = c + 1 
    print("Person", person[x], "is the winner") 

Last_Person(50)