python: muestreo sin reemplazo desde una cuadrícula 2D

Question

Necesito una muestra, sin reemplazo, de todas las posibles tuplas de números de range(n). Es decir, tengo una colección de (0,0), (0,1), ..., (0, n), (1,0), (1,1), ..., (1, n), ..., (n, 0), (n, 1), (n, n), y estoy tratando de obtener una muestra de k de esos elementos. Espero evitar construir explícitamente esta colección.

Sé random.sample(range(n), k) es simple y eficiente si necesitaba una muestra de una secuencia de números en lugar de tuplas de números.

Por supuesto, puedo construir explícitamente la lista que contiene todas las tuplas posibles (n * n = n^2), y luego llamar al random.sample. Pero eso probablemente no sea eficiente si k es mucho más pequeño que n^2.

No estoy seguro si las cosas funcionan igual en Python 2 y 3 en términos de eficiencia; Yo uso Python 3.

Answer 1

Dependiendo de cuántos de estos seleccione, puede ser más simple simplemente hacer un seguimiento de las cosas que ya ha elegido (a través de set) y luego volver a seleccionar hasta que obtenga algo que no has elegido ya

La otra opción es usar un poco de matemática simple:

numbers_in_nxn = random.sample(range(n*n), k) # Use xrange in Python 2.x 
tuples_in_nxn = [divmod(x,n) for x in numbers_in_nxn] 

Answer 2

Sin tratar (sin pitón a mano):

random.shuffle(range(n))[:k] 

ver los comentarios. No dormir lo suficiente ...

Answer 3

Usted dice:

Por supuesto, se puede construir de forma explícita la lista que contiene todas las posibles (n * n = n^2) tuplas, y luego llamar a muestra aleatoria. Pero eso probablemente es no eficiente si k es mucho más pequeño que n^2.

Bueno, ¿qué hay de la construcción de la tupla después de que haya elegido al azar uno? Es decir, si puede construir las tuplas antes de elegir aleatoriamente cuál seleccionar, puede hacer primero la selección y luego construir.

No entiendo cómo se supone que sus tuplas para mirar, pero aquí es un ejemplo, aunque me di cuenta de sus tuplas son todos de la misma longitud, esto muestra el principio:

lugar de hacer esto:

>>> import random 
>>> all_sequences = [range(x) for x in range(10)] 
>>> all_sequences 
[[], [0], [0, 1], [0, 1, 2], [0, 1, 2, 3], [0, 1, 2, 3, 4], [0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 4, 5, 6], [0, 1, 2, 3, 4, 5, 6, 7], [0, 1, 2, 3, 4, 5, 6, 7, 8]] 
>>> random.sample(all_sequences, 3) 
[[0, 1, 2, 3, 4, 5, 6, 7], [0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 4, 5, 6, 7, 8]] 

podría hacer esto:

>>> import random 
>>> selection = random.sample(range(10), 3) 
>>> [range(x) for a in selection] 
[[0, 1, 2, 3, 4, 5, 6, 7, 8], [0, 1, 2, 3, 4, 5, 6, 7, 8], [0, 1, 2, 3, 4, 5, 6, 7, 8]]