均匀生成排列，最多重复 k 次？

问：

我们有一组数字。我们希望生成这些数字创建的 m 长度的排列，并在大多数时候重复每个数字。{1, 2, 3, ...,n}k

如果我们假设 ，那么我们可以得到： ，但不像第二个例子中那样恰好是输出的三倍，这比 k 多。n=5, k=2, m=3{3,3,1}{3, 3, 3}3

有没有办法快速均匀地生成这种排列？

我尝试了两种不同的解决方案。

第一：

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

第二种方法：

生成随机整数，仅当它没有出现在时间之前时才将其添加到序列中。下面介绍了这些单词的优化版本（用 Python 编写）。 Python 代码段：k

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=110^9

第二个是没有产生均匀的排列（有些比其他的概率更大）。

你有什么想法如何快速、均匀地生成这样的序列吗？