algorithm - 均匀生成最多重复 k 次的排列？

Question

我们设置了 {1, 2, 3, ...,n} 个数字。我们想要生成长度为 m 的排列，这些排列由这些数字创建，每个数字最多重复 k 次。

如果我们假设n=5, k=2, m=3，那么我们可以收到:{3,3,1}，但不是 {3, 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 次来生成序列，这是很明显。

第二个不是生成统一排列(有些排列的概率比其他排列大)。

你有什么想法可以快速、一致地生成这样的序列吗？

Answer 1

这假设您有足够的内存来保存数字 [1..n] k 次。

1. 设置数组[1..n]。

2. 将数组复制 k 次:[1..n, 1..n, 1..n, ... 1..n] 变成一个大数组。

3. 运行 Fisher-Yates shuffle 的前 m 个步骤在大型重复数组上获得所需的排列。不需要打乱整个数组，因为您只需要 m 个数字。