Descobrir a semente usada para embaralhar uma lista

[Lucas Sampaio]

Fala pessoal,

Dado o seguinte código:

    import random
    seed = 0.72
    my_list = range(10)
    random.shuffle(my_list, random=lambda: seed)
    print my_list
    # [0, 1, 8, 2, 3, 4, 9, 5, 6, 7]

O "lambda: seed" aí em cima foi só pra forçar um número em especial, por padrão o shuffle usa o random.random para gerar o seed.

A dúvida é: com a lista embaralhada, eu consigo obter a semente (0.72) de volta, ou uma lista de possibilidades?

Att,

---
Lucas S. Magalhães
Developer at Órama
http://lsmagalhaes.com

[Pedro Werneck]

Em primeiro lugar, você está usando errado. O parametro random não é para passar um seed, mas para passar uma função que vai gerar os números aleatórios, que por padrão é random.random. O que você fez foi sempre usar o valor 0.72 como multiplicador do índice para a troca feita pelo shuffle.

O que você queria fazer é isso:

>>> random.seed(0.72)

>>> my_list = range(10)

>>> random.shuffle(my_list)

>>> print my_list

[0, 4, 7, 3, 6, 9, 2, 1, 5, 8]

Respondendo à pergunta, não com uma lista desse tamanho. O MersenneTwister, o algoritmo usado pelo RNG da stdlib Python pode ser quebrado se você tiver acesso ao valor de 624 iterações consecutivas, porém como o shuffle usa os valores randomicos como multiplicador para reordenar a lista, pela ordem final você não teria acesso aos valores exatos com uma lista de 624 items e precisaria de uma amostra bem maior.

2012/12/27 Lucas Sampaio <m...@lsmagalhaes.com>

--
--
------------------------------------
Grupo Python-Brasil
http://www.python.org.br/wiki/AntesDePerguntar
 
<*> Para visitar o site do grupo na web, acesse:
http://groups.google.com/group/python-brasil
 
<*> Para sair deste grupo, envie um e-mail para:
python-brasi...@googlegroups.com
 
 
 

--
---
Pedro Werneck

[Lucas Sampaio]

Olá Pedro,

Desculpe, não deixei muito claro meu exemplo anterior. Eu não estou fazendo errado, conheço o uso do parâmetro random, fiz um lambda que retorna um valor fixo pra facilitar meus testes, só por isso.

De toda forma, tu já resolveu um monte de dúvidas minhas. Valeu, cara ;)

---
Lucas S. Magalhães
Developer at Órama
http://lsmagalhaes.com

[Pedro Werneck]

Continua não fazendo sentido, mas se você tem certeza do que está falando, ok.

2012/12/27 Lucas Sampaio <m...@lsmagalhaes.com>

--
---
Pedro Werneck

[Lucas Sampaio]

Só pra esclarecer, Pedro,

Estou estudando uma aplicação específica do shuffle, e queria testar a possibilidade da semente usada funcionar também como uma espécie de chave, assim eu poderia obter duas sequências iguais, desde que usasse as mesmas listas de entrada e a mesma semente. Coisa de iniciante mesmo, testar e ver se rola, e rolou... rolou porque forcei uma semente em específico, daí o meu lambda hardcoded.

Na prática a ideia agora é gerar um seed usando random.random e armazená-lo em algum lugar, pra gerar a mesma sequência randomizada diversas vezes. A propósito, obrigado pela primeira resposta, li alguns artigos sobre Mersenne Twister que me ajudaram muito =D

---
Lucas S. Magalhães
Developer at Órama
http://lsmagalhaes.com

[Christian S. Perone]

Lucas, neste caso acho que faz mais sentido você usar o random.seed().

2012/12/27 Lucas Sampaio <m...@lsmagalhaes.com>

--

Blog | Github | Twitter

"Forgive, O Lord, my little jokes on Thee, and I'll forgive Thy great big joke on me."

[Pedro Werneck]

É justamente isso que não faz sentido, porque o parametro random do shuffle() não é um seed, é a função que retorna o valor que será usado para cada item da lista.

O seed é usado uma vez para inicializar o rng, por isso chama-se semente.

O parametro random é um callable que retorna um numero aleatório que é usado como multiplicador do índice atual para gerar um índice aleatório onde o item será colocado, *para cada item*, não o mesmo repetido para todas.

São duas coisas completamente diferentes, e você está de fato confundindo. 

O que você está fazendo nesse código que enviou no final das contas resume-se a uma aritmética simples, multiplicando o reverso do item de cada valor da lista por 0.72 e arredondando para baixo para escolher onde colocar. Você simplesmente não está usando o gerador de números aleatórios em lugar nenhum.

Você está fazendo isso, e note que não uso nada do módulo random em lugar nenhum...

>>> r = range(10)

>>> ij = [(i, int((i +1) * 0.72)) for i in reversed(range(1, 10))]

>>> for i, j in ij: r[i], r[j] = r[j], r[i]

... 

>>> r

[0, 1, 8, 2, 3, 4, 9, 5, 6, 7]

Quando na verdade o que você queria fazer é:

>>> import random

>>> random.seed(0.72)

>>> r = range(10)

>>> ij = [(i, int((i +1) * random.random())) for i in reversed(range(1, 10))]

>>> for i, j in ij: r[i], r[j] = r[j], r[i]

... 

>>> r

[0, 4, 7, 3, 6, 9, 2, 1, 5, 8]

Resumindo, é possível fazer o que você quer, usar sempre o mesmo seed e repetir a sequência, mas não é o que você está fazendo. 

2012/12/27 Lucas Sampaio <m...@lsmagalhaes.com>

--
---
Pedro Werneck

[Pedro Werneck]

Faltou a saída do shuffle igual:

>>> random.seed(0.72)

>>> r = range(10)

>>> random.shuffle(r)

>>> r

[0, 4, 7, 3, 6, 9, 2, 1, 5, 8]

2012/12/27 Pedro Werneck <pjwe...@gmail.com>

--
---
Pedro Werneck

[Leonardo Santagada]

2012/12/27 Lucas Sampaio <m...@lsmagalhaes.com>

A dúvida é: com a lista embaralhada, eu consigo obter a semente (0.72) de volta, ou uma lista de possibilidades?

Se você usar a seed do jeito que o werneck falou realmente vai ser muito dificil, sem a lista original mais complicado ainda. Força bruta ta ai pra isso, mas em a lista original acho complicado.

 --

Leonardo Santagada

[Pedro Werneck]

Sem a lista original é impossível.

2012/12/27 Leonardo Santagada <sant...@gmail.com>

--

--
------------------------------------
Grupo Python-Brasil
http://www.python.org.br/wiki/AntesDePerguntar
 
<*> Para visitar o site do grupo na web, acesse:
http://groups.google.com/group/python-brasil
 
<*> Para sair deste grupo, envie um e-mail para:
python-brasi...@googlegroups.com
 
 
 

--
---
Pedro Werneck