CODEWITHSUNDEEP
haskell
Kaspar Kohler
Kaspar Kohler

Reputation: 1

Haskell sublists

I have to make a function that finds specific sublists.

function :: Integer -> Integer -> [[Integer]]
function n m = …

For example, if the numbers are n = 6 and m = 7. List is [1,2,3,4,5,6] The answer is [[6,1],[5,2],[4,3]].

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

Order is not necessary. So on I have made these steps. Any help would be useful.Also example codes would be useful. If anyone can solve this problem, I would appreciate it. Code with solution would be very useful for me.

    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 = …

Upvotes: 0

Views: 1879

Answers (2)

epsilonhalbe
epsilonhalbe

Reputation: 15965

I would go and create all lists with sum property, for example using list comprehension. And then filtering by the uniqueness property, by something like:

  1. taking list difference of the first sublist and the generatorlist and checking if the next sublist is contained in the generator,
    • then deleting a sublist if it is not subset of the altered generator
    • or doing the same procedure as in 1.
  2. you can end the procedure if the sum of the altered generators is less than m

note that the result is depending on how you have sorted all sublists - so the solution is not a unique longest list of sublists, but just one of many results possible with sum and "uniqueness" property.

Edit: Some Code - not perfect maximum solution

just something to start and think about i only collect easy two element lists and otherwise take one maximal list.

The next improvements would be to make a function collecting not only easy but all two element lists and then generalize this to get sublists of a given length, maybe you want to have a look a bit at elementary combinatorics.

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

and some test cases:

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"
                            ]

Upvotes: 1

Landei
Landei

Reputation: 54584

The function subsequences in Data.List might be helpful, e.g.

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

Then you "just" need to filter out all sub-lists that don't match your criterias.

Upvotes: 0

Related Questions