Haskell函数输出输入列表中添加到输入数字的所有组合 [英] Haskell function that outputs all combinations within the input list that add to the input number

问题描述

我想在haskell中编写一个函数，它接受一个整数列表和一个整数值作为输入，并输出包含元素组合的所有列表的列表，这些元素的总和等于输入整数。

例如：

myFunc [3,7,5,9,13,17] 30 = [[13,17]， [3,5,9,13]]

尝试：

  myFunc :: [Integer]  - >整数 - > [[Integer]] 
 myFunc列表sm =案例列表
 []  - > [] 
 [x] 
 | x == sm  - > [x] 
 |否则 - > [] 
（x：xs）
 | x + myFunc xs == sm  - > [x] ++ myFunc [xs] 
 |否则 - > myFunc xs 
  

我的代码只产生一个组合，而且这个组合必须是连续的，这不是我想要的实现

解决方案

编写一个函数来创建所有子集

<$ p $ （x：xs）= f xs ++ map（x :)（f xs）
f [] = [[]]

然后使用过滤器



  filter（（= = 30）。sum）$ f [3,7,5,9,13,17] 
 
 [[13,17]，[3,5,9,13]] 
  

按照@Ingo的建议，您可以在生成列表时修剪列表，例如

  f ::（Num a，Ord a）=> [a]  - > [（a）] 
f [] = [[]] 
f（x：xs）= f xs ++（filter（（< = 30）。sum）$ map（x :) $ f xs）
  

应该比生成所有2 ^ N元素更快。

I want to write a function in haskell that takes a list of integers and an integer value as input and outputs a list of all the lists that contain combinations of elements that add up to the input integer.

For example:

myFunc [3,7,5,9,13,17] 30 = [[13,17],[3,5,9,13]]

Attempt:

myFunc :: [Integer] -> Integer -> [[Integer]]
myFunc list sm = case list of
    [] -> []
    [x]
        | x == sm -> [x]
        | otherwise -> []
    (x : xs)
        | x + myFunc xs == sm -> [x] ++ myFunc[xs]
        | otherwise -> myFunc xs

My code produces just one combination and that combination must be consecutive, which is not what I want to achieve

解决方案

Write a function to create all subsets

f [] = [[]]
f (x:xs) = f xs ++ map (x:) (f xs)

then use the filter

filter ((==30) . sum) $ f [3,7,5,9,13,17]

[[13,17],[3,5,9,13]]

as suggested by @Ingo you can prune the list while it's generated, for example

f :: (Num a, Ord a) => [a] -> [[a]]
f [] = [[]]
f (x:xs) = f xs ++ (filter ((<=30) . sum) $ map (x:) $ f xs)

should work faster than generating all 2^N elements.

这篇关于Haskell函数输出输入列表中添加到输入数字的所有组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！