高效生成 "subtraction chains"

Question

如果您需要一些上下文，我之前发布了。看来我用这种方法走错了路。

Addition chains 可用于最小化对数字求幂所需的乘法次数。例如，a⁷ 需要四次乘法。两个计算a²=a×a和a⁴=a²×a²，另外两个计算a⁷=a⁴×a²×a.

同样，我正在尝试为一组数字生成所有可能的 "subtraction chains"。例如，给定一组数字 {1, 2, 3}，我正在尝试生成以下排列。

{1, 2, 3}

{1, 2, 3}, {1, 2}
{1, 2, 3}, {1, 2}, {1}
{1, 2, 3}, {1, 2}, {2}
{1, 2, 3}, {1, 2}, {1}, {2}

{1, 2, 3}, {1, 3}
{1, 2, 3}, {1, 3}, {1}
{1, 2, 3}, {1, 3}, {3}
{1, 2, 3}, {1, 3}, {1}, {3}

{1, 2, 3}, {2, 3}
{1, 2, 3}, {2, 3}, {2}
{1, 2, 3}, {2, 3}, {3}
{1, 2, 3}, {2, 3}, {2}, {3}

{1, 2, 3}, {1, 2}, {1, 3}
{1, 2, 3}, {1, 2}, {1, 3}, {1}
{1, 2, 3}, {1, 2}, {1, 3}, {2}
{1, 2, 3}, {1, 2}, {1, 3}, {3}
{1, 2, 3}, {1, 2}, {1, 3}, {1}, {2}
{1, 2, 3}, {1, 2}, {1, 3}, {1}, {3}
{1, 2, 3}, {1, 2}, {1, 3}, {2}, {3}
{1, 2, 3}, {1, 2}, {1, 3}, {1}, {2}, {3}

# and so on...

排列中的每个元素（{1, 2, 3} 除外）都可以通过从排列中的另一个集合中删除单个元素来找到。

例如，排列{1, 2, 3}, {1}是无效的，因为{1}不能通过从{1, 2, 3}.

中删除单个元素来构造

是否有已知的算法可以找到幂集的幂集的这个子集？我的实现将在 Python 中，但问题与语言无关。此外，我实际上不想要包含单个元素的集合的排列（例如 {1, 2, 3}, {1, 2}, {1}），因为它们对应于不感兴趣的 "dictator" 情况。

Answer 1

按照您的描述生成所有这些列表的算法可以按如下方式工作：对于当前列表中的每个集合，创建一个副本，删除一个元素，将其添加到列表中，然后递归调用该算法。您还必须确保不生成重复项，这可以通过确保新列表比前一个列表 "smaller"（按长度或（已排序）元素的成对比较）来完成。

这是 Python 中的一个实现，作为生成器函数，没有太多优化。现在这似乎工作得很好，生成所有子集而没有任何重复。

def generate_sets(sets, min_num=2):
    yield sets
    added = set() # new sets we already generated in this iteration
    for set_ in sets:
        # only if the current set has the right length
        if min_num < len(set_) <= len(sets[-1]) + 1:
            for x in set_:
                # remove each element in turn (frozenset so we can put in into added)
                new = set_.difference({x})
                # prevent same subset being reachable form multiple sets
                frozen = frozenset(new)
                if frozen not in added:
                    added.add(frozen)
                    # recurse only if current element is "smaller" than last
                    if (len(new), sorted(new)) < (len(sets[-1]), sorted(sets[-1])):
                        for result in generate_sets(sets + [new], min_num):
                            yield result

对于 generate_sets([{1,2,3}], min_num=2) 这会生成以下列表：

[{1, 2, 3}]
[{1, 2, 3}, {2, 3}]
[{1, 2, 3}, {2, 3}, {1, 3}]
[{1, 2, 3}, {2, 3}, {1, 3}, {1, 2}]
[{1, 2, 3}, {2, 3}, {1, 2}]
[{1, 2, 3}, {1, 3}]
[{1, 2, 3}, {1, 3}, {1, 2}]
[{1, 2, 3}, {1, 2}]

对于generate_sets([{1,2,3}], 1)，一共生成了45个集合列表。

但是，我看不出与您之前问题的联系：{1, 2, 3}, {1, 2}、{1, 2, 3}, {1, 3} 和 {1, 2, 3}, {2, 3} 不应该被认为是等价的吗？

高效生成 "subtraction chains"

Efficiently generating "subtraction chains"

language-agnostic

algorithm

combinatorics