时间戳

首页 > 解决方案 > 编号一些整数分区

haskell - 编号一些整数分区

问题描述

这些树代表n <= 5最多m = 3部分的整数分区。

1            2                 3          4      5
|          /   \             /   \        |
|         /     \           /     \       |
|        /       \         /       \      |
1,1     2,1      2,2     3,1      3,2    4,1
|        |        |       |
|        |        |       |
|        |        |       |
1,1,1   2,1,1    2,2,1  3,1,1

让我们从上到下，从左到右枚举它们：

1 2 3 4 5 
6 7 8 9 10 11
12 13 14 15

我需要一个列表D，D!!i如果P分区编号为i，则分区编号为P ++ [1]。也就是说，对于这个例子，

以此类推，D!!7 = 13，D!!8 = 14， 和D!!9 = 15。

我完全不知道如何开始。我知道 SO 不是代码编写服务，但我只要求提供任何提示。

编辑

这是一个尝试。

dico' :: Int -> Int -> Seq (Maybe Int)
dico' m n = go 1 S.empty
  where
  go :: Int -> Seq (Maybe Int) -> Seq (Maybe Int)
  go k d'
    | k == n-1 = d'
    | otherwise = go (k+1) (inner 0 [0] [m] [m] 0 d')
      where
      inner :: Int -> [Int] -> [Int] -> [Int] -> Int -> Seq (Maybe Int) -> Seq (Maybe Int)
      inner i a b c end d
        | i >= length a = d -- what is the terminating condition here ?
        | otherwise = if b!!i > 0
          then let l = min (b!!i) (c!!i) in
          let dd = d |> (Just $ end+1) in
          inner (i+1) (a ++ [end + 1 .. end + l]) (b ++ map (\x -> b!!i - x) [1 .. l]) (c ++ [1 .. l]) (end + l) dd
          else inner (i+1) a b c end (d |> Nothing)

它可以工作，只是结果太长。我没有找到内循环的适当终止条件。

> dico' 5 3
fromList [Just 1,Just 6,Just 7,Just 9,Just 11,Nothing,Just 12,Just 13,Just 14,Just 15,Nothing,Nothing,Just 16,Just 17,Nothing,Nothing,Just 18,Nothing,Nothing]

编辑 2

好的，我现在明白了。我仍然对任何改进感兴趣。

a008284_tabl :: [[Int]]
a008284_tabl = [1] : f [[1]]
  where
  f xss = ys : f (ys : xss)
    where
    ys = map sum (zipWith take [1..] xss) ++ [1]

_P :: Int -> Int -> Int
_P m n = sum (concatMap (take (min m n)) (take m a008284_tabl))

dico' :: Int -> Int -> Seq (Maybe Int)
dico' m n = go 1 S.empty
  where
  pmn = Just $ Just $ _P m n
  go :: Int -> Seq (Maybe Int) -> Seq (Maybe Int)
  go k d'
    | k == n-1 = d'
    | otherwise = go (k+1) (inner 0 [0] [m] [m] 0 d')
      where
      inner :: Int -> [Int] -> [Int] -> [Int] -> Int -> Seq (Maybe Int)
            -> Seq (Maybe Int)
      inner i a b c end d
        | S.lookup (S.length d - 1) d == pmn = d
        | otherwise = let bi = b!!i in
          if bi > 0
            then let l = min bi (c!!i) in
              let dd = d |> (Just $ end+1) in
              let range1l = [1 .. l] in
              inner (i+1) (a ++ [end + 1 .. end + l])
                          (b ++ map (\x -> bi - x) range1l)
                          (c ++ range1l) (end + l) dd
            else inner (i+1) a b c end (d |> Nothing)


> dico' 5 3
fromList [Just 1,Just 6,Just 7,Just 9,Just 11,Nothing,Just 12,Just 13,Just 14,Just 15]
> dico' 10 7
fromList [Just 1,Just 11,Just 12,Just 14,Just 17,Just 21,Just 26,Just 30,Just 33,Just 35,Nothing,Just 36,Just 37,Just 38,Just 40,Just 41,Just 43,Just 46,Just 47,Just 49,Just 52,Just 54,Just 55,Just 57,Just 59,Nothing,Just 60,Just 61,Just 63,Nothing,Just 64,Just 65,Nothing,Just 66,Nothing,Nothing,Just 67,Just 68,Just 69,Just 70,Just 72,Just 73,Just 74,Just 76,Just 77,Just 79,Just 80,Just 81,Just 82,Just 84,Just 85,Nothing,Just 86,Nothing,Just 87,Just 88,Just 89,Just 90,Nothing,Nothing,Just 91,Just 92,Nothing,Nothing,Just 93,Nothing,Nothing,Just 94,Just 95,Just 96,Just 97,Just 98,Just 100,Just 101,Just 102,Just 103,Just 104,Just 105,Nothing,Nothing,Just 106,Just 107,Just 108,Nothing,Just 109,Nothing,Nothing,Just 110,Just 111,Nothing,Nothing,Just 112,Nothing,Nothing,Just 113,Just 114,Just 115,Just 116,Just 117,Nothing,Just 118,Just 119,Just 120,Nothing,Just 121,Nothing,Just 122,Just 123,Nothing,Nothing,Just 124,Nothing,Nothing,Just 125,Just 126,Just 127,Just 128,Nothing,Just 129,Just 130,Nothing,Nothing,Just 131]

标签： haskellcombinatorics

解决方案

推荐阅读