Мы установили {1, 2, 3, ...,n} чисел. Мы хотим сгенерировать перестановку длины m, созданную из этих чисел, с повторением каждого числа не более k раз.
Если мы предположим n=5, k=2, m=3, то мы могли бы получить: {3,3,1}, но не {3, 3, 3}, поскольку 3 во втором примере получается трижды в выходе, что больше, чем k.
Есть ли способ равномерной генерации такой перестановки быстрым способом?
Я пробовал два разных решения.
Во-первых:
1) генерация случайной перестановки с повторением, существует n^m разных перестановок.
2) проверить, является ли это правильной перестановкой (если она не содержит более k раз того же числа
3) если да, вернитесь, иначе перейдите к 1)
Фрагмент Python:
import numba
import numpy as np
@numba.jit(nopython=True)
def gen_sequence1(n, k, m):
result = np.random.randint(0, n, (1, m))[0]
while not is_correct(result, k):
result = np.random.randint(0, n, (1, m))[0]
return result
@numba.jit(nopython=True)
def most_frequent(iter):
return np.bincount(iter).max()
@numba.jit(nopython=True)
def is_correct(pruf, k):
return most_frequent(pruf) <= k
Второй метод:
Генерировать случайное целое число, добавлять его в последовательность, только если оно не появлялось до k раз. Оптимизированная версия этих слов представлена ниже (написана на Python).
Фрагмент Python:
def gen_seq(n, d, m):
choices = list(range(n))
degrees = [0] * n
result = []
k = n - 1
for i in range(m):
rand = np.random.randint(0, k)
result.append(choices[rand])
degrees[choices[rand]] += 1
if degrees[choices[rand]] == d:
choices[rand], choices[k] = choices[k], choices[rand]
k -= 1
return result
Проблема в том, что первый метод очень медленный для n=30, m=28, d=1, ему нужно 10^9 раз для генерации последовательности, что довольно очевидно.
Второй не генерирует однородные перестановки (некоторые имеют большую вероятность, чем другие).
Есть ли у вас идеи, как можно было бы генерировать такую последовательность быстро и равномерно?