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

たとえば、リスト内包表記を使用して、合計プロパティを使用してすべてのリストを作成します。次に、次のような一意性プロパティでフィルタリングします。

  1. 最初のサブリストとジェネレーターリストのリスト差分を取り、次のサブリストがジェネレーターに含まれているかどうかを確認します。
    • 変更されたジェネレーターのサブセットでない場合は、サブリストを削除します
    • または 1 と同じ手順を実行します。
  2. 変更されたジェネレーターの合計が m 未満の場合、手順を終了できます

結果は、すべてのサブリストをどのようにソートしたかによって異なることに注意してください。したがって、解決策は、サブリストの一意の最長リストではなく、合計と「一意性」プロパティで可能な多くの結果の 1 つにすぎません。

編集：いくつかのコード - 完全ではない最大の解決策

始めて考えることは、簡単な2つの要素リストのみを収集し、それ以外の場合は1つの最大リストを取得します。

次の改善点は、簡単なだけでなく、2 つの要素リストすべてを収集する関数を作成し、これを一般化して、指定された長さのサブリストを取得することです。基本的な組み合わせ論を少し見てみたいと思うかもしれません。

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 に答える