从列表中查找数字组合，这些数字总计在Haskell中

发布于 2025-02-14 01:29:03 字数 645 浏览 0 评论 0原文

我研究了这个编程问题：

编写一个函数“ howsum（targetsum，numbers）”，该函数将目标摄入目标和数字作为参数。该函数应返回一个数组，其中包含元素的任何组合，这些元素将元素累加到靶标。如果没有组合加起来目标的组合，请返回null。如果可能有多种组合，则可以返回任何一个。

我解决了一个类似的函数，该功能如果可能的话返回：

canSum target nums
    | target>0 = any (\x -> canSum (target-x) nums) nums
    | target<0 = False
    | otherwise = True

cansum通过创建一个递归树来起作用，其中第一个调用的总和和任何 abor 都会为每个数字创建一个分支剩余的款项。如果这达到0的目标，那么到达那里的分支是从NUMS中减去数字的组合，这意味着您可以使用nums中的数字来总和到> target。

但是我似乎无法获得工作功能。那将如何写？

原文

I working on this programming problem:

Write a function 'howSum(targetSum, numbers)' that takes in a targetSum and an array of numbers as arguments. The function should return an array containing any combination of elements that add up to exactly the targetSum. If there is no combination that adds up to the targetSum, then return null. If there are multiple combinations possible, you may return any single one.

I solved a similar function that returns if it is possible:

canSum target nums
    | target>0 = any (\x -> canSum (target-x) nums) nums
    | target<0 = False
    | otherwise = True

canSum works by creating a recursive tree where the first call has the total sum and any creates a branch for each number with the remaining sum needed. If this reaches a target of 0, the branch to get there was a combination of subtracting numbers from nums meaning you can use numbers in the nums to sum to target.

But i can't seem to get a howSum function to work. How would that be written?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

动听の歌 2025-02-21 01:29:03

您可以修改cansum的功能的主体，以创建howsum'。对于false，您可以返回一个空列表[]，对于true您返回包含一个列表的列表（解决方案）：空列表;因此：

howSum' :: (Num a, Ord a) => a -> [a] -> [[a]]
howSum' target nums
    | target > 0 = # …
    | target < 0 = []
    | otherwise = [[]]

对于target＆gt; 0因此，我们需要找到候选值。因此，我们将列举列表，从而进行递归电话。如果返回命中率，我们需要将该值预先介绍给该调用的所有结果。我们可以使用 ::可折叠f =＆gt; （a - ＆gt; [b]） - ＆gt; fa-＆gt; [b] 使结果串联。因此，这将看起来像：

howSum' :: (Num a, Ord a) => a -> [a] -> [[a]]
howSum' target nums
    | target > 0 = concatMap (\x -> … (howSum' (target-x) nums)) nums
    | target < 0 = []
    | otherwise = [[]]

您仍然需要填写…部分。

Howsum'将列出构建结果的可能方法。您可以将howsum'用作辅助功能，以产生单个解决方案，以防有这样的解决方案。

该解决方案允许多次使用nums中的相同值。它还将多次产生相同的解决方案，但顺序不同，因此[3，5]和[5，3]都将是8的解决方案。我将其作为进一步改进的练习。

You can modify the body of the function of canSum to create howSum'. For False you can return an empty list [], for True you return a list that contains one list (solution): the empty list; so:

howSum' :: (Num a, Ord a) => a -> [a] -> [[a]]
howSum' target nums
    | target > 0 = # …
    | target < 0 = []
    | otherwise = [[]]

For target > 0 we thus need to find candidate values. We thus will enumerate over the list, and thus make a recursive call. In case that returns a hit, we need to prepend that value to all the results of that call. We can use concatMap :: Foldable f => (a -> [b]) -> f a -> [b] to concatenate the results. This will thus look like:

howSum' :: (Num a, Ord a) => a -> [a] -> [[a]]
howSum' target nums
    | target > 0 = concatMap (\x -> … (howSum' (target-x) nums)) nums
    | target < 0 = []
    | otherwise = [[]]

where you still need to fill in the … part.

howSum' will thus list all possible ways to construct a result. You can use howSum' as a helper function to produce a single solution in case there is such solution.

This solution allows to use the same value in nums multiple times. It will also produce the same solution multiple times but in a different order, so [3, 5] and [5, 3] will both be solutions for 8. I leave it as an exercise to improve this further.

回复收藏 0 原文

~没有更多了~