python - 从给定的元素列表生成随机 numpy 数组，每个元素至少重复一次

Question

我想在重采样之后从给定的 numpy(比如 input_list)创建一个数组(比如 output_list)，这样 input_list 中的每个元素在 output_list 中至少存在一次。 output_list 的长度将始终 > input_list.

的长度

我尝试了几种方法，我正在寻找一种更快的方法。不幸的是，numpy 的 random.choice 不能保证至少存在一个元素。

第 1 步:生成数据

import string
import random
import numpy as np

size = 150000
chars = string.digits + string.ascii_lowercase
input_list= [
            "".join(
                [random.choice(chars) for i in range(5)]
            ) for j in range(dict_data[1]['unique_len'])]

选项 1:让我们尝试一下 numpy 的 random.choice 在概率方面具有均匀分布。

output_list = np.random.choice(
    input_list,
    size=output_size,
    replace=True,
    p=[1/input_list.__len__()]*input_list.__len__()
    )
assert set(input_list).__len__()==set(output_list).__len__(),\
    "Output list has fewer elements than input list"

这引发了断言:

Output list has fewer elements than input list

选项 2让我们将随机数填充到 input_list 中，然后对其进行洗牌。

output_list = np.concatenate((np.array(input_list),np.random.choice(
    input_list,
    size=output_size-input_list.__len__(),
    replace=True,
    p=[1/input_list.__len__()]*input_list.__len__()
)),axis=None)

np.random.shuffle(output_list)
assert set(input_list).__len__()==set(output_list).__len__(),\
    "Output list has fewer elements than input list"

虽然这不会引发任何断言，但我正在寻找一种比这更快的解决方案，无论是通过算法还是使用 numpy 的内置函数。

感谢您的帮助。

Answer 1

令lenI为输入列表长度，lenO为输出列表长度。

1) 从源列表进行均匀随机选择的lenO - lenI 迭代

2) 然后将所有输入列表附加到输出列表的末尾

3) 然后进行 lenI 次 Fisher–Yates shuffle 迭代以均匀分布最后的元素。

import random
src = [1, 2, 3, 4]
lD = 10
lS = len(src)
dst = []
for _ in range(lD - lS):
    dst.append(src[random.randint(0, lS-1)])
dst.extend(src)
print(dst)
for i in range(lD - 1, lD - lS - 1, -1):
    r = random.randint(0, lD - 1)
    dst[r], dst[i] = dst[i], dst[r]
print(dst)

>>[4, 3, 1, 3, 4, 3, 1, 2, 3, 4]
>>[4, 3, 1, 3, 4, 3, 1, 3, 4, 2]

这是线性复杂度的方法。