algorithm - 高效生成 "subtraction chains"

Question

我发布了 another question如果您需要一些上下文，请早点。看来我在这种方法上走错了路。

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

同样，我正在尝试为一组数字生成所有可能的“减法链”。例如，给定一组数字 {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})，因为它们对应于不感兴趣的“独裁者”案例。

Answer 1

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

这是 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} 都被认为是等价的吗？