陷入时间复杂性，需要一个不太复杂的解决方案来从给定的边长度列表生成多边形

Question

我已经写了一个代码来计算多边形的数量，可以从给定的棍子（即：长度）创建。你知道吗

For sticks = [2, 3, 4, 5, 6], the output should be polygonsCount(sticks) = 13.

Here are all the polygons that can be obtained from sticks with lengths 2, 3, 4, 5, and 6:

(2, 3, 4);
(3, 4, 5);
(2, 4, 5);
(2, 5, 6);
(3, 4, 6);
(3, 5, 6);
(4, 5, 6);
(2, 3, 4, 5);
(2, 3, 4, 6);
(2, 3, 5, 6);
(2, 4, 5, 6);
(3, 4, 5, 6);
(2, 3, 4, 5, 6);

该程序运行良好，但由于时间复杂性，它正在跨越更大列表的时间限制。你知道吗

首先，我生成一个给定的棍子列表的幂集。我试图避免[]到所有的[x，x]--2个元素子集，但是失败了，而且，我不认为这会降低时间复杂度。 然后我检查可能的多边形。但我有时间限制。代码如下：

def powersetGenerator(sticks,blankSet):
    if sticks ==[]:
        yield blankSet
    else:
        for item in powersetGenerator(sticks[1:],blankSet+[sticks[0]]):
            yield item
        for item in powersetGenerator(sticks[1:],blankSet):
            yield item

def possiblePolygons(array):
    sumOfAll = sum(array)
    longestSide = max(array)
    return longestSide < sumOfAll - longestSide

def polygonsCount(sticks):
    powerset = list(powersetGenerator(sticks,[]))
    count = 0
    for index in range(len(powerset)):
        if len(powerset[index])>=3 and possiblePolygons(powerset[index]) == 1:
            count=(count+1)%((10**9) + 7)
    return count

Answer 1

这基本上是相同的解决方案，具有相同的复杂性，但为了防止重复操作，进行了大量优化。你知道吗

# updated version
import functools

@functools.lru_cache(None)
def s_s_l(items):
    """return a list of items [subset, sum, length]"""
    if not items:
        return [[[], 0, 0]] 
    first, *rest = items    # python3 syntax
    ss1 = s_s_l(tuple(rest))
    ss2 = [[[first]+ss[0], first+ss[1], 1+ss[2]] for ss in ss1]
    return ss1 + ss2 

def polygons(sticks):
    """yield polygons"""
    sticks = sorted(sticks, reverse=True)
    prev_longest = None
    for i in range(len(sticks)-2):
        longest = sticks[i]
        if longest == prev_longest:
            continue
        prev_longest = longest
        for subset, nsum, nlen in s_s_l(tuple(sticks[i+1:])):
            if nsum > longest and nlen >= 2:
                yield([longest] + subset)

def count_pg(sticks):
    """count unique polygons"""
    solutions = {tuple(pg) for pg in polygons(sticks)}
    return len(solutions)

print(count_pg([2, 3, 4, 5, 6]))
print(count_pg([88, 88, 88, 88, 88, 88, 88, 88, 88, 88, 88, 88, 88, 88, 88]))

---

我可能错了，但正确的解决方案的关键可能是计算计数而不构造多边形。数学基础较好的人可能知道答案。你知道吗

Answer 2

另一种方法是使用itertools.组合（）从Python标准库生成多边形：

def polygonGenerator(sticks):
    for r in range(3, len(sticks)+1):
        polygons = itertools.combinations(sticks, r)
        # for lexicographical order & pretty printing
        polygons = list(set(polygons))
        polygons.sort()
        #
        for polygon in polygons:
            yield polygon

对于没有词典排序的Python3，polygonggenerator（）可以重构为：

def polygonGenerator(sticks):
    for r in range(3, len(sticks)+1):
        yield from set(itertools.combinations(sticks, r))