0

我必须创建一个查找特定子列表的函数。

function :: Integer -> Integer -> [[Integer]]
function n m = …
  • 如果m小于则n程序退出。
  • 如果(mod (sum [1..n]) m) /= 0再报错。
  • 否则程序应该找到子列表。
  • 主要列表是从[1..n]

例如，如果数字是n = 6和m = 7。清单是[1,2,3,4,5,6]答案是[[6,1],[5,2],[4,3]]。

function 6 7
>>> [[6,1],[5,2],[4,3]]

订单不是必需的。所以我已经做了这些步骤。任何帮助都会很有用。示例代码也会很有用。如果有人能解决这个问题，我将不胜感激。带有解决方案的代码对我来说非常有用。

    function :: Integer -> Integer -> [[Integer]]
    function n m 
      |m < n = error "m is smaller than n"
      |(mod (sum [1..n]) m) /= 0 = error "list sum doesn't devide with m"
      |otherwise = …
4

2 回答 2

1

我会去创建所有具有 sum 属性的列表，例如使用列表理解。然后通过唯一性属性进行过滤，例如：

  1. 获取第一个子列表和生成器列表的列表差异并检查下一个子列表是否包含在生成器中，
    • 然后删除一个子列表，如果它不是改变的生成器的子集
    • 或执行与 1 中相同的程序。
  2. 如果更改的生成器的总和小于 m，则可以结束该过程

请注意，结果取决于您对所有子列表进行排序的方式 - 因此解决方案不是唯一的最长子列表列表，而只是具有 sum 和“唯一性”属性的众多结果之一。

编辑：一些代码 - 不是完美的最大解决方案

只是一些开始和思考的事情，我只收集简单的两个元素列表，否则取一个最大列表。

下一个改进将是使一个函数不仅容易收集，而且收集所有两个元素列表，然后将其推广到给定长度的子列表，也许你想看看基本的组合。

module Sublists where
import Data.List ((\\))

subLists :: Int -> Int -> [[Int]]
subLists n = subLists' ([],[1..n])

subLists' :: ([[Int]],[Int]) -> Int -> [[Int]]
subLists' aa m = fst (mLSubLists (tLSubLists aa m) m)

_subLists :: ([Int] -> Int -> [Int]) -> ([[Int]],[Int]) -> Int -> ([[Int]],[Int])
_subLists _ yx@(_,[ ]) _ = yx
_subLists _ yx@(_,[_]) _ = yx
_subLists f yx@(yy,xx)  m | sum xx < m = yx
                       | otherwise  = if tt == []
                                        then yx
                                        else _subLists f (tt:yy,xx\\tt) m
                       where tt = f xx m

tLSubLists :: ([[Int]],[Int]) -> Int -> ([[Int]],[Int])
tLSubLists = _subLists twoList

mLSubLists :: ([[Int]],[Int]) -> Int -> ([[Int]],[Int])
mLSubLists = _subLists manyList


twoList :: [Int] -> Int -> [Int]
twoList [ ]    _ = []
twoList [_]    _ = []
twoList xx@(x:xs) m | (x + l) < m         = []
                    |  x == l              = []
                    | (x + l) `rem` m == 0 = [x,l]
                    | otherwise           = twoList ii m
                    where l  = last xs
                          ii = init xx

manyList :: [Int] -> Int -> [Int]
manyList xx m | s < m         = []
              | s == m         = xx
              | s `rem` m == 0 = xx
              | otherwise     = manyList xs m
              where s  = sum xx
                    xs = tail xx

和一些测试用例：

import Sublists
import Test.HUnit
import Data.List ((\\))

main = testAll

testAll = runTestTT $ TestList tests

tests :: [Test]
tests = [
   "n=6 m=7" ~: "subLists"  ~:  [[3,4],[2,5],[1,6]]
                            ~=? subLists 6 7,
   "n=6 m=7" ~: "twoList"   ~:  [1,6]
                            ~=? twoList [1..6] 7,
   "n=6 m=7" ~: "twoList"   ~:  [2,5]
                            ~=? twoList ([1..6]\\[1,6]) 7,
   "n=6 m=7" ~: "twoList"   ~:  [3,4]
                            ~=? twoList (([1..6]\\[1,6])\\[2,5]) 7,
   "n=6 m=7" ~: "manyList"  ~:  [2,3,4,5]
                            ~=? manyList [1..5] 7,
   "dummy"   ~: "dummy"     ~:  "result"
                            ~=? (\_ -> "result") "function"
                            ]
于 2012-05-21T23:41:12.950 回答
0

subsequences中的功能Data.List可能会有所帮助，例如

subsequences "abc" == ["","a","b","ab","c","ac","bc","abc"]

然后，您“只”需要过滤掉所有与您的条件不匹配的子列表。

于 2012-05-21T19:26:56.923 回答