私信  •  关注

kmh

kmh 最近创建的主题
kmh 最近回复了

我把你的问题搞砸了…尝试实现一种基于树的bc方法,我认为它很聪明,但我的笔记本电脑被它卡住了。我很好奇我们到底要用这么大的数字来寻找多少排列,然后(对我自己)把问题改成简单地计算排列,看看在一台轻量级笔记本电脑上是否可行。

我得到154135675070个独特的排列。

开始…我把itertools弄得乱七八糟,排成26列就花了一辈子。所以…为了提醒我自己,这个被遗忘已久的公式至少可以计算出不同的排列,我发现… https://socratic.org/questions/how-many-distinct-permutations-can-be-made-from-the-letters-of-the-word-infinity

带着这个,我跑了以下几步去计数。它不到一秒钟就跑了。

from numpy import prod
from math import factorial
import itertools

# number of unique permutations
def count_distinct_permutations(tup):
    value_counts = [len(list(grp)) for _, grp in itertools.groupby(tup)]
    return factorial(sum(value_counts)) / prod([float(factorial(x)) for x in value_counts])

# starting values
x = 30 # apples
y = 26 # baskets
z = 3  # max per basket

# count possible results
result = 0
for combos in itertools.combinations_with_replacement(range(z), y):
    if sum(combos) == x:
        result += count_distinct_permutations(combos)

现在。。。这显然不能回答你的具体问题。老实说,我无论如何都记不住你要找的结果。但是…你可以用这个推断…对于您选择的值,只有12个值组合,但每个组合的排列在15k到5000万之间。

你可以看看每个组合…在 count_distinct_permutations() 函数, itertools.groupby 为您提供每个数字的来源 (0,1,2) 在组合中,你可以用这12个结果中的每一个来推断一些东西。不知道是什么,但我也不太确定如何处理长度为26的1540亿个列表。:)

希望这里有有用的东西,即使它没有回答你确切的问题。祝你好运!