Генерация случайных неповторяющихся пар чисел в пределах 2 диапазонов

Question

Я хочу создать случайные пары чисел в пределах 2 диапазонов.

Так, например, если я хочу 3 случайные пары чисел, где 10 [[11,35],[15,30],[15,42]] но не [[11,35],[11,35],[12,39]]

Я хотел бы, чтобы эффективный (как в вычислительном отношении, так и в отношении памяти) алгоритм сделал это.Язык на самом деле не имеет значения, потому что я могу адаптировать его позже (хотя Python будет предпочтительнее).

До сих пор лучшая идея, которую я имел, - это создать словарь со всеми возможными числами в n1 и в качестве значенийсписок номеров, которые были использованы в n2.Тогда я могу просто выбрать случайное число n1 и найти число, которое не использовалось в наборе n1 [n2].

Хотя это не очень эффективно для космоса, и я надеюсь на что-то лучшее.Кажется также, что в вычислительном отношении неэффективно много раз находить число, не входящее в n1 [n2].

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

Есть ли эффективный способ сделать это?Является ли это общей проблемой?

Редактировать: Было бы хорошо, если бы ее можно было легко расширить до большего числа измерений (таким образом, наборов из N чисел).Но это пока не нужно.

Answer 1

Целочисленная пара (x, y) в [min_x, min_x + s) X [min_y, min_y + t) может быть преобразована в целое число m в одномерном пространстве [min_x * t, (min_x + s) * t) путем вычисления m = x * t + y - min_y.Обратное отображение от m до (x, y) может быть достигнуто с помощью (m // t, min_y + m % t) в Python.

Таким образом, проблема преобразуется в выбор нескольких значений из [min_x * t, (min_x + s) * t) без замены (т.е. без дубликатов в возвращаемой последовательности).Это можно сделать, просто вызвав функцию random.sample в Python.Согласно документу, базовая реализация экономит место для последовательных входов.Таким образом, вся проблема может быть решена в Python, как показано ниже:

from random import sample

# max_x and max_y are exclusive while min_x and min_y are inclusive
t = max_y - min_y
sampled_pairs = [(m//t, min_y + m%t) for m in sample(range(min_x * t, max_x * t), k=3)]