有效地产生“减法链". [英] Efficiently generating "subtraction chains"

问题描述

我早些时候发布了另一个问题想要一些背景.看来我采用这种方法走错了路.

I posted another question earlier if you want some context. It appears that I was on the wrong path with that approach.

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

Addition chains can be used to minimize the number of multiplications needed to exponentiate a number. For example, a⁷ requires four multiplications. Two to compute a²=a×a and a⁴=a²×a², and another two to compute a⁷=a⁴×a²×a.

类似地，我正在尝试为一组数字生成所有可能的减法链".例如，给定一组数字{1, 2, 3}，我试图生成以下排列.

Similarly, I'm trying to generate all of the possible "subtraction chains" for a set of numbers. For example, given the set of numbers {1, 2, 3}, I'm trying to generate the following permutations.

{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}之外).

Where each element in the permutation (besides {1, 2, 3}) can be found by removing a single element from another set in the permutation.

例如，置换{1, 2, 3}, {1}无效，因为无法通过从{1, 2, 3}中删除单个元素来构造{1}.

For example, the permutation {1, 2, 3}, {1} is invalid because {1} can not be constructed by removing a single element from {1, 2, 3}.

是否存在一种已知的算法来找到功率集的功率集的这个子集?我的实现将在Python中进行，但问题是与语言无关.另外，我实际上不希望包含包含单个元素的集合的排列(例如{1, 2, 3}, {1, 2}, {1})，因为它们对应于一个无关紧要的独裁者"情况.

Is there a known algorithm to find this subset of the power set of a power set? My implementation will be in Python, but the question is language agnostic. Also, I don't actually want the permutations which contain a set with a single element (e.g. {1, 2, 3}, {1, 2}, {1}) because they corresponds to a "dictator" case which is not of interest.

推荐答案

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

An algorithm to generate all those lists as you describe it could work as follows: For each set in the current list, create a copy, remove one element, add it to the list, and call the algorithm recursively. You also have to make sure not to generate duplicates, which could by done by ensuring that the new list is "smaller" (by length or pairwise comparison of the (sorted) elements) than the previous one.

这里是Python的实现，作为生成器函数，没有进行太多优化.现在，这似乎工作得很好，生成了所有子集而没有任何重复项.

Here's an implementation in Python, as a generator function, without much optimization. This seems to work pretty well now, generating all the subsets without any duplicates.

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)，将生成以下列表:

For generate_sets([{1,2,3}], min_num=2) this generates the following lists:

[{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个集合列表.

For generate_sets([{1,2,3}], 1), a total of 45 lists of sets are generated.

但是，我看不到与您之前的问题的联系:{1, 2, 3}, {1, 2}，{1, 2, 3}, {1, 3}和{1, 2, 3}, {2, 3}都不应被视为等同吗?

However, I fail to see the connection to your previous question: Shouldn't {1, 2, 3}, {1, 2}, {1, 2, 3}, {1, 3}, and {1, 2, 3}, {2, 3} all be considered equivalent?

这篇关于有效地产生“减法链".的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！