"Josephus-problem" usando la lista in python

Question

Volevo sapere se sarà possibile risolvere il problema di Josepheus usando la lista in python.

In termini semplici, il problema di Josephus consiste nel trovare una posizione in una disposizione circolare che sarebbe sicura se le esecuzioni fossero gestite usando un parametro di salto che è noto in precedenza.

Ad esempio: data una disposizione circolare come [1,2,3,4,5,6,7] e un parametro di salto di 3, le persone verranno eseguite nell'ordine come 3,6,2,7,5,1 e la posizione 4 sarebbe la cassaforte.

Ho cercato di risolvere questo elenco utilizzando per un po 'di tempo, ma le posizioni dell'indice diventano difficili da gestire per me.

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 

Aggiornato la questione con il frammento di codice, ma non credo che la mia logica è corretta.

Answer 1

Semplicemente, è possibile utilizzare list.pop(i) per eliminare ogni vittima (e ottenere il suo ID) in un ciclo. Quindi, dobbiamo solo preoccuparci di avvolgere gli indici, cosa che si può fare semplicemente prendendo l'indice di indice saltato il numero di prigionieri rimasti.

Allora, la soluzione questione diventa

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] 

uscita di prova:

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

Se non si vuole calcolare l'indice, è possibile utilizzare la struttura di dati deque.

Answer 3

Questa è la mia soluzione alla tua domanda:

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