得到均匀分布的无重复组合子集

Question

我正在尝试从总组合集中获取组合的子集，以便每个选项的使用次数相同，或接近，而不重复。例如，我有 8 个选项（比方说 A-H），我需要 4 个字母的组合，顺序无关紧要。那会给我 70 种可能的组合。我想取这些组合的一个子集，使得 A 与其他字母出现的次数一样多，A 与 B 一起出现的次数与 C 与 D 一起出现的次数一样多，等等。我知道有些子集不可能让每个字母都出现出现相同次数并且与另一个字母出现相同次数所以当我在这篇文章中说“相同次数”时，我的意思是相同或接近它。

如果选项写在如下所示的有组织的列表中，我不能只选择前 N 个选项，因为这会给 A 带来比 H 更多的使用。而且，A 和 B 一起出现的次数比 C 多和 D. 主要思想是尽可能均匀地分布使用每个字母组合。

ABCD ABCE ABCF ABCG ABCH ABDE ABDF ABDG ABDH ABEF ABEG ABEH ABFG ABFH ABGH ACDE ACDF ACDG ACDH ACEF ACEG ACEH ACFG ACFH ACGH ADEF ADEG ADEH ADFG ADFH ADGH AEFG AEFH AEGH AFGH BCDE BCDF BCDG BCDH BCEF BCEG BDF BGDEH BCGHDEH BCFG BCFG BDFH BDGH BEFG BEFH BEGH BFGH CDEF CDEG CDEH CDFG CDFH CDGH CEFG CEFH CEGH CFGH DEFG DEFH DEGH DFGH EFGH

我可以抽取一个随机样本，但它是随机的，它不完全符合我有意抽取一个子集以获得均匀分布的要求。它可以随机选择一个非常不均匀的分布。

是否有工具或数学公式可以像我要求的那样生成列表？如果我知道如何去做，用 Python 或其他编码语言构建一个是一种选择。

编辑 - 把它想象成配料。 A-H 是每种独特的成分，如面粉、糖、黄油等。我正在创建使用四种可用成分的食谱（不用担心测量，只担心使用的成分）。

8 种成分有 70 种可能的组合（在这里放置 8 个对象和 4 个样本大小）。我想要这些组合的子集的列表，其大小是我放入公式中的。例如，假设我想要 20 个组合。我希望每种配料都和其他配料一样多，这意味着在这些组合中，可能 A（面粉）用了 3 次，B（糖）用了 3 次，C（黄油）用了 3 次，等等。

我也希望A（面粉）和B（糖）一起使用的次数与B（糖）和C（黄油）一起使用的次数一样多。

大多数子集大小不允许项目的完美分布，但它应该给出一个尽可能接近均匀分布的列表。

我创建了一个 Python 脚本，我认为它可以满足我的需求。我正在清理它并对其进行更多测试，然后我会在这里发布它。

为了展示正确结果的示例，我发现大小为 14 的子集将产生完美的分布：

ABCD  ADEG  BDGH
ABEH  ADFH  CDEH
ABFG  BCEG  CDFG
ACEF  BCFH  EFGH
ACGH  BDEF

你可以看到在那个子集中，每个字母被使用了 7 次，每个配对（比如 A 和 B）出现了 3 次，每个三元组（比如 A 和 B 和 C）出现了一次。这正是我正在寻找的结果类型。我希望这能为读者澄清问题。

我会尽快发布我的 python 代码。

Answer 1

您要求庄家洗牌。

python 标准库有一个名为 random 的模块，其中包含一个 shuffle 函数。展示您的八个选项，将它们洗牌，然后返回前四个或您需要的任何数量。它将是随机的，服从你想要的分布。

编辑

我不确定如何更清楚地表达“洗牌” 但我会尝试数学、英语和代码。

绘制 8 个不同元素的随机排列并选择前 4 个。

取一副洗好的 8 张不同的牌，处理其中 4 张，丢弃其余的。

#! /usr/bin/env python
from pprint import pp
import random

import matplotlib.pyplot as plt
import pandas as pd
import typer


class Options:
    def __init__(self, all_options, k=4):
        self.all_options = all_options
        self.k = k

    def new_deck(self):
        deck = self.all_options.copy()
        random.shuffle(deck)
        return deck

    def choose_options(self):
        return self.new_deck()[: self.k]

    def choose_many_options(self, n):
        for _ in range(n):
            yield "".join(self.choose_options())


def main(n: int = 10_000_000):
    opt = Options(list("ABCDEFGH"))
    demo = list(opt.choose_many_options(3))
    pp(demo, width=22)

    df = pd.DataFrame(opt.choose_many_options(n), columns=["opt"])
    df["cnt"] = 1
    with pd.option_context("display.min_rows", 16):
        print(df.groupby("opt").sum())
    cnts = df.groupby("opt").sum().cnt.tolist()
    plt.plot(range(len(cnts)), cnts)
    plt.gca().set_xlim((0, 1700))
    plt.gca().set_ylim((0, None))
    plt.gca().set_xlabel("combination of options")
    plt.gca().set_ylabel("number of occurrences")
    plt.show()


if __name__ == "__main__":
    typer.run(main)

输出：

['FABE',
 'GEDC',
 'FBAC']
       cnt
opt       
ABCD  6041
ABCE  5851
ABCF  6111
ABCG  5917
ABCH  6050
ABDC  5885
ABDE  5935
ABDF  5937
...    ...
HGEC  5796
HGED  5922
HGEF  5859
HGFA  5936
HGFB  5880
HGFC  5869
HGFD  5942
HGFE  6049

[1680 rows x 1 columns]

P(n, k) = P(8, 4) = n! / (n - k)!

= 40,320 / 24

= 1680

所有可能的选项组合都是随机抽取的

这是每次不同抽奖的出现次数。 请注意，5952 次出现 × 1680 次使我们达到约 1000 万次。 PRNG安排事项 “这样每个选项的使用次数都相同，或者接近。” 反复掷多面骰子后， 我们看到预期的均值和标准差 出现在实验结果中。