python-3.x 在给定和和给定元素数的情况下，求正整数的排列

lndjwyie 于 2022-11-19 发布在 Python

关注(0)|答案(2)|浏览(113)

如何找到给定 * 总和 * 和给定 * 元素数 * 的正整数的所有排列。
例如，

Input: sum = 4, number of elements = 2. 

Output: (1,3), (3,1), (2,2)

我的想法是，既然我知道元素的数量是N，我将创建N个数组，每个数组从1到和S-1。因此，对于这个例子，我将从两个数组开始，[1,2,3]和[1,2,3]。然后我将遍历每个数组，类似于

output = []
for x in array1:
  for y in array2:
    if x+y == target:
      output.append((x,y))

但我不知道如何为任何N创建它，因为这将是可变数量的for循环。
现在我有了第二个想法，我认为这是可行的。

import numpy as np
from itertools import combinations
 
def find_permutations(S,N):
  x = np.asarray([x+1 for x in range(S)]*N)
  y = [seq for seq in combinations(x,N) if sum(seq)==S]
  return list(dict.fromkeys(y)) # remove duplicates

find_permutations(4,2)
[(1, 3), (2, 2), (3, 1)]

但这是非常慢的，因为它首先创建一个非常长的数组，找到所有的组合，然后过滤下来。像find_permutations(16,16)的东西需要非常长的时间，但它显然只是[(1,1,...,1)]。

python-3.x

来源：https://stackoverflow.com/questions/74452864/find-permutations-of-positive-integers-given-sum-and-given-number-of-elements

2条答案

按热度按时间

vlju58qv1#

下面是一个递归解决方案，它将生成满足要求的元组。

def get_combinations(target, num_elements, combinations=None):
    # Initialise an empty list
    if combinations == None:
        combinations = []
    # Calculate the sum of the current list of numbers
    combinations_sum = sum(combinations)
    # Check if the target is reached -> No further recursion necessary
    if (combinations_sum == target and len(combinations) == num_elements):
        # Return this combination of numbers
        yield tuple(combinations)
    else:
        # The combination of numbers doesn't yet total to target value
        # Iterate over each number from 1 to the target value 
        for number in range(1, target + 1):
            # Check that neither the target value nor number of elements will be exceeded
            if (combinations_sum + number <= target 
                and len(combinations) < num_elements):
                # Add the number to the list
                new_combo = combinations + [number]
                # Find all solutions for the list
                for c in get_combinations(target, num_elements, new_combo):
                    yield c

示例输出：

[c for c in get_combinations(4, 2)]
> [(1, 3), (2, 2), (3, 1)]

赞(0）回复(0）举报 2022-11-19

bd1hkmkf2#

下面是一个较短的例子（经过编辑以涵盖边框大小写k <= 1）：

def f(sum, k):
    if k < 1:
        return []
    if k == 1:
        return [(sum,)]
    if k == 2:
        return [(i,sum-i) for i in range(1, sum-k+2)]
    
    return [tup[:-1] + ab for tup in f(sum, k-1) for ab in f(tup[-1], 2)]

测试输出：

f(2, 0)  # []
f(3, 1)  # [(3,)]
f(4, 2)  # [(1, 3), (2, 2), (3, 1)]
f(5, 3)  # [(1, 1, 3), (1, 2, 2), (1, 3, 1), (2, 1, 2), (2, 2, 1), (3, 1, 1)]

该算法取k-1的结果（即，f(sum, k-1)，递归地），并应用相同的函数来将所有最后的元素分解成2元组（即，f(tup[-1], 2)，再次递归地）。
时序比较：f(5, 3)的10.000次重复：0.07秒
对于get_combinations(5, 3)：0.30秒
以及对于find_permutations(5, 3)：2.35秒
至于速度，我假设这是一个类似的情况，像斐波那契序列，这种嵌套递归是非常低效的，不会让你超过f(20, 10)。

赞(0）回复(0）举报 2022-11-19

我来回答

python-3.x 在给定和和给定元素数的情况下，求正整数的排列

2条答案

相关问题

热门标签

最新问答