社区首页 >问答首页 >识别从集合中提取的唯一对集(顺序不重要)

问识别从集合中提取的唯一对集(顺序不重要)
EN

Stack Overflow用户

提问于 2022-08-14 12:47:48

回答 2查看 69关注 0票数 0

最后，我希望用Python构建一个算法来完成这个任务(我对语言比较新)，但我希望找到一个研究方向，帮助我理解它背后的想法--至少我可以看出它与组合学有关。

如果我们有六个元素，{a，b，c，d，e，f}，我们可以识别出15个不同的对，它们的顺序无关紧要(n = 6，k= 2，组合)。

它们是: ab，ac，ad，ae，af，bc，bd，be，bf，cd，ce，cf，de，df，ef

然而，我感兴趣的是识别不同的对集。野蛮的力量，他们似乎是：

{ab，cd，ef}

{ab，ce，df}
{ab，cf，de}
{ac，bd，ef}
{ac，df}H 210H 111{ac，bf，de}<
>H 212H 113{ad，bc }{ad，bf}< bc }H 115{ad，be }{ad>{ad><代码><<>
{ae，bf，cd}
{af，bc，de}
{af，bd，ce}
{af，be，cd}

G 231

假设我没有错误，也会有15个列表，其中有3个(或n/2)对/条目，其中配对的顺序和配对中的顺序并不重要。如前所述，我希望最终创建一些代码来构造这些对的列表。

开始点是值得赞赏的！

python

combinatorics

回答 2

Stack Overflow用户

发布于 2022-08-14 13:08:22

在您的字符集中，如果不与其自身配对，每个字符将有5个可能的配对：ab ac ad...。在您获得a的所有可能对之后，您可以移动到b上，您将再次遍历列表，但这次已经找到了a，因为ab已经找到了。你可以重复这一点，每次都省略前面的字母，直到你在最后一封信上。在此之后，您可以循环遍历成对，并将它们添加到新的列表中。

票数 0

Stack Overflow用户

发布于 2022-08-14 13:10:25

说还有K元素。如果K为0，则退出。
选择最小的。
选择与其配对的任何K-1剩余元素。
将K设置为K-2并重复。H 213G 214

这似乎确实是你在手工建立你的清单时所做的。

可能的排列总数是步骤2中K-1值的乘积。对于您的示例来说，K从6开始，因此K-1第一次通过循环为5，第二次为3，第三次为1: 5*3*1 = 15。

代码

这里有一种使用递归生成器对其进行编码的方法。这不是最快的方法，但可能是最容易理解的方法之一：

def genpairs(s):
    if len(s) % 2:
        raise ValueError("len must be even")
    if s:
        first = min(s)
        s = s - {first}
        for second in sorted(s):
            head = [(first, second)]
            for tail in genpairs(s - {second}):
                yield head + tail
    else:
        yield []

然后，例如，

>>> for a in genpairs(set("abcdef")):
...      print(a)
[('a', 'b'), ('c', 'd'), ('e', 'f')]
[('a', 'b'), ('c', 'e'), ('d', 'f')]
[('a', 'b'), ('c', 'f'), ('d', 'e')]
[('a', 'c'), ('b', 'd'), ('e', 'f')]
[('a', 'c'), ('b', 'e'), ('d', 'f')]
[('a', 'c'), ('b', 'f'), ('d', 'e')]
[('a', 'd'), ('b', 'c'), ('e', 'f')]
[('a', 'd'), ('b', 'e'), ('c', 'f')]
[('a', 'd'), ('b', 'f'), ('c', 'e')]
[('a', 'e'), ('b', 'c'), ('d', 'f')]
[('a', 'e'), ('b', 'd'), ('c', 'f')]
[('a', 'e'), ('b', 'f'), ('c', 'd')]
[('a', 'f'), ('b', 'c'), ('d', 'e')]
[('a', 'f'), ('b', 'd'), ('c', 'e')]
[('a', 'f'), ('b', 'e'), ('c', 'd')]