python: выборка без замены из 2D сетки

Question

Мне нужен образец без замены из всех возможных наборов чисел от range(n). То есть у меня есть коллекция (0,0), (0,1), ..., (0, n), (1,0), (1,1), ..., (1, n ), ..., (n, 0), (n, 1), (n, n), и я пытаюсь получить образец k из этих элементов. Я надеюсь избежать явного построения этой коллекции.

Я знаю, random.sample(range(n), k) прост и эффективен, если мне нужен образец из последовательности чисел, а не из наборов чисел.

Конечно, я могу явно создать список, содержащий все возможные (n * n = n^2) кортежи, и затем вызвать random.sample. Но это, вероятно, неэффективно, если k намного меньше, чем n^2.

Я не уверен, что в Python 2 и 3 все работает одинаково с точки зрения эффективности; Я использую Python 3.

Answer 1

В зависимости от того, сколько из них вы выбираете, может быть проще всего просто отслеживать то, что вы уже выбрали (через set), а затем повторно выбирать, пока не получите то, что у вас нетt уже выбрано.

Другой вариант - просто использовать простую математику:

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

Вы говорите:

Конечно, я могу явно построить список, содержащий все возможные (n * n = п ^ 2) кортежи, а затем вызвать случайный пример. Но это, вероятно, не эффективен, если к намного меньше чем п ^ 2.

Ну, а как насчет создания кортежа после , который вы случайно выбрали? То есть, если вы можете построить наборы до того, как вы случайным образом выберете, какой из них выбрать, вы можете сначала выполнить сбор, а затем построить.

Я не понимаю, как должны выглядеть ваши кортежи, но вот пример, хотя я понимаю, что ваши кортежи одинаковой длины, это показывает принцип:

Вместо этого:

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

Вы бы сделали это:

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

Answer 3

Без попытки (без Python под рукой):

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

см. Комментарии.Не спал достаточно ...