Como resolver o 'Josephus Problem' utilizando força bruta?

Question

Considere n pessoas em torno de um círculo numeradas de 1 a n. Começando com a pessoa associada ao número 1, nós eliminamos todas segundas pessoas até que só reste uma única pessoa no círculo. Determine o número associado a pessoa que sobrevive. Por exemplo, se n = 6, na primeira rodada serão eliminadas as pessoas 2, 4 e 6. Na segunda rodada será eliminada a pessoa inicialmente com o número 3 e na última rodada a pessoa com o número 1, restando apenas a pessoa numerada inicialmente com 5. Implemente a solução força bruta para esse problema. Gere figuras que ajudem ao entendimento do problema (e apresente os códigos usados para isso).

Answer 1

A linguagem utilizada para implementação da solução do problema foi Python 3.6.

A solução do Josephus Problem, utilizando um algoritmo força bruta, é de relativa fácil implementação para n = 6.

Podemos pensar esse problema também como o problema da "batata-quente". Cada pessoa faz um certo número de passes (o problema considera que as pessoas estão em círculo), e com isso deixa a "batata-quente" na mão de alguém - o que faz com que esta seja eliminada. Deste modo, começamos definindo uma função josephus(list_pessoas, passes), onde o primeiro argumento é a lista de pessoas e o segundo a quantidade de passes. Utilizamos o comando list_pessoas.pop(i) para excluir cada "vítima" (e obter sua posição) em um loop. Então, nós apenas temos que nos preocupar em envolver os índices, o que pode ser feito simplesmente pegando o índice pulado e modificando o número de pessoas remanescentes.

Assim, a solução se torna:

def josephus(list_pessoas, passes):
        i = passes
        while len(list_pessoas) > 1:
            print(list_pessoas.pop(i)) # elimina a pessoa em i
            i = (i + passes) % len(list_pessoas)
        print('Sobrevivente: ', list_pessoas[0])

Testando para o problema da questão, onde:

josephus([1,2,3,4,5,6],1)

Temos como resultado:

2
4
6
3
1
Sobrevivente:  5

Observe que o comando list_pessoas.pop(i) nos dá em sequência quais serão as pessoas eliminadas - dada certa quantidade de passe(s) - até que sobre uma única sobrevivente, nesse caso n=5 (a solução final).

Gerei uma tabela que tenta simbolizar como as eliminações são feitas:

import plotly
plotly.tools.set_credentials_file(username='Felipe1303', api_key='QUn3U7DhJF5jzVs0SRGg')

import plotly.plotly as py
import plotly.figure_factory as ff

data_matrix = [[1, 2, 3, 4, 5, 6],
               [1, 1, 1, 1, 1, 1], 
               [1, 0, 1, 0, 1, 0],
               [1, 0, 0, 0, 1, 0],
               [0, 0, 0, 0, 1, 0]]

table = ff.create_table(data_matrix)
py.iplot(table)

Os rótulos da coluna simbolizam cada pessoa (1 a 6), já os valores binários (0 ou 1) em cada locus da matriz representam se a pessoa foi eliminada (0) ou é sobrevivente (1). Observe novamente que as pessoas estão organizadas em círculo; é possível constatar na última linha da tabela que o sobrevivente de fato é a pessoa número 5.

Obs.: Note que para utilizar o pacote plotly é necessário criar uma conta em seu site - as imagens são geradas em seu perfil cadastrado.

Comments

Ótima implementação!!

A título de curiosidade, eu implementei a versão recursiva deste problema.

Para que a recursão se tornasse factível, eu precisei adicionar o parâmetro "n" - que representa o comprimento da lista - e o parâmetro ind, que tem default igual a 1, mas pode ter seu valor definido pelo usuário caso o "passes" seja diferente de 1.

Segue a implementação recursiva:

def josephus_recursiva(list_pessoas,n, passes,ind=1):
        
    if(n==1):
        print('Sobrevivente: ', list_pessoas[0])
    else:
        print(list_pessoas[ind])
        list_pessoas.pop(ind)        
        ind=(ind+passes)%(n-1)
        josephus_recursiva(list_pessoas,n-1, passes,ind)

list_pessoas=[1,2,3,4,5,6]
josephus_recursiva(list_pessoas, len(list_pessoas), 1)

Answer 2

Boas implementacoes, Felipe e Pedro.

Tb fiz uma forma recursiva desta questao:

    def josephus(n, k):

        if (n == 1):
            return 1
        else:
            return (josephus(n - 1, k) + k-1) % n + 1 
n=5
k=1
print("The chosen place is ", josephus(n, k))

E assim:

The chosen place is  5