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

Мне нужен образец без замены из всех возможных наборов чисел из 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.