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

Question

我们已经设置了{1, 2, 3, ...,n} of numbers。我们想要生成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时间来生成序列，这是非常明显的。

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

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

Answer 1

这里假设您有足够的内存来保存数字1..nk次。

1. 将数组设置为k次: 1..n，1..n，1..n，... 1..n到一个大型数组中。
2. 在大型重复数组上运行Fisher-Yates shuffle的前m个步骤，以获得所需的排列。因为你只需要m个数字，所以不需要打乱整个数组。

Answer 2

如果我没记错，np.choice有一个给出概率的选项，那么你可以这样做：

1. 将数组设置k次: 1..n，1..n，1..n，... 1..n成为一个大的数组。就像这个大型阵列均匀分布的@rossum proposed.
2. Generate概率(1/(k*n))一样。

重复m次：

1. 获取一个数字以结果数组
2. 设置概率，对于抽出的项目概率将为0，而对于具有相同值的其余项目，它们之间的分布均匀为1/(k*n)，我们刚刚设置为0

示例：

设S=1,1,1,2,2,2,3,3,3,4,4,4是一个包含k个项目的大型数组，k=3且m= 4。

随机生成P= 1/12*len(S)

• result = 1

• Probabilities (S，P)假设

1. =1
2. Probabilities将像这样P= 0,1/12+1/36,1/12+1/36,1/12+1/36，

重复步骤2和3 m次

如果没有与绘制的值相同的值，则将其设置为0，并设置剩余概率，以保持该比例和总和为1。我认为最困难的部分将是操纵概率。