算法-给你一个小于50的数字 a ，请写出一个算法得到所有可能的数字集合，每个数字集合满足以下条件：

Question

给你一个小于50的数字 a ，请写出一个算法得到所有可能的数字集合，每个数字集合满足以下条件：

1. 集合中所有数字的和等于a;

2. 集合中的所有数字均大于1；

3. 集合中可以出现重复数字；

例如：

2 -> {2},
3->{3},
4->{[4], [2, 2]},
5->{[5], [3, 2]},
6->{[6], [4, 2], [3, 3], [2, 2, 2]}
7->{[7], [5, 2], [4, 3], [3, 2, 2]}
8->{[8], [6, 2], [5, 3], [4, 4], [4, 2, 2], [3, 3, 2], [2, 2, 2, 2]}

Answer 1

Haskell：

solve n = go [(n,[])] []
where
go [] result = result
go ((left, path):xs) result
| left == 1 = go xs result
| left == 0 = go xs (path:result)
| otherwise = go (next (left, path) ++ xs) result

next (left, path) = map (l -> (left - l, l:path))
$ filter (lessThanHead path) [2..left]

lessThanHead [] x = True
lessThanHead (y:ys) x = x <= y

-- Test --

ghci> mapM_ (print . solve) [2..8]
[[2]]
[[3]]
[[4],[2,2]]
[[5],[2,3]]
[[6],[2,4],[3,3],[2,2,2]]
[[7],[2,5],[3,4],[2,2,3]]
[[8],[2,6],[3,5],[4,4],[2,2,4],[2,3,3],[2,2,2,2]]

50时有30701种组合。

趣味:用SMT求解器求解

{-# LANGUAGE ScopedTypeVariables #-}
import Data.SBV.Bridge.Z3
import Control.Monad (foldM_, mapM_)

-- 把一个数值m分成n份，且满足题目条件
equalsMN m n = do
-- 新建n个变量(s0, s1 .. sn-1)
vars :: [SInt16] <- mkExistVars n
-- 每个变量s满足 2 <= s <= m
mapM_ (x -> constrain (x .>= 2 &&& x .<= (fromIntegral m))) vars
-- 变量满足 s0 <= s1 <= ... <= sn-1，保证结果不重复
foldM_ (x y -> constrain (x .<= y) >> return y) 0 vars
-- 全部变量的和等于m
return $ sum vars .== (fromIntegral (m::Int))

-- 依次求出把m分成 1 ... m/2 份时的解
solveM m = mapM (allSat . equalsMN m) [1 .. m `div` 2]

求解9的时候是这样的：

[Solution #1:
s0 = 9 :: SInt16
This is the only solution.,Solution #1:
s0 = 4 :: SInt16
s1 = 5 :: SInt16
Solution #2:
s0 = 2 :: SInt16
s1 = 7 :: SInt16
Solution #3:
s0 = 3 :: SInt16
s1 = 6 :: SInt16
Found 3 different solutions.,Solution #1:
s0 = 2 :: SInt16
s1 = 3 :: SInt16
s2 = 4 :: SInt16
Solution #2:
s0 = 2 :: SInt16
s1 = 2 :: SInt16
s2 = 5 :: SInt16
Solution #3:
s0 = 3 :: SInt16
s1 = 3 :: SInt16
s2 = 3 :: SInt16
Found 3 different solutions.,Solution #1:
s0 = 2 :: SInt16
s1 = 2 :: SInt16
s2 = 2 :: SInt16
s3 = 3 :: SInt16
This is the only solution.]

这个方法要比第一个解法慢很多，不过更加“声明式”。