寫一個函數來獲取Haskell中所有大小爲n的子序列？

我試圖寫一個函數來獲取大小爲n的列表的所有子序列，但我不知道如何去做。寫一個函數來獲取Haskell中所有大小爲n的子序列？

我在想，我可以使用內建的Data.List.subsequences，只是篩選出大小不是n的列表，但它看起來像是一個相當迂迴和低效的方式，而我如果我可以避免這種情況，寧願不這樣做，所以我想知道你是否有任何想法？

我希望它是這樣的類型

subseqofsize :: Int -> [a] -> [[a]]

爲了進一步澄清，這裏是什麼，我正在尋找一個例子：

subseqofsize 2 [1,2,3,3] 
[[1,2],[1,3],[2,3],[1,3],[2,3],[3,3]]

另外，我不關心任何事物的順序。

來源

2012-03-29 Michael Holman

術語挑剔：術語「子列表」，通常意味着什麼不同於「子序列」，即子列表只包含原始列表的連續元素。所以你的函數應該被稱爲'subsequencesOfSize'。 – sepp2k 2012-03-29 10:10:17

這是功課嗎？ – augustss 2012-03-29 10:25:42

我將使用這個函數作爲家庭作業的一部分，但它不是直接的作業。我的一部分任務是評估犯人的手，我想這樣做來幫助我評分對。 – 2012-03-29 17:16:09

我假設這是家庭作業，或者你以其他方式將其作爲練習來學習，所以我會給你一個解決方案的大綱，而不是用勺子餵你正確的答案。

無論如何，這是一個遞歸問題。

有基地情況：

sublistofsize 0 _  = ... 
sublistofsize _ []  = ...

再就是2個遞歸步驟：

sublistofsize n (x : xs) = sublistsThatStartWithX ++ sublistsThatDon'tStartWithX 
    where sublistsThatStartWithX = ... 
     sublistsThatDon'tStartWithX = ...

記住的基本情況的定義需要與定義適當的工作在遞歸的情況下。仔細想想：不要只是假設基礎案例都會導致一個空的列表。

這有幫助嗎？

來源

2012-03-29 06:52:09 dave4420

您可以用數學思考一下這個計算大小的子列表ķ，大家可以看一下一個元素列表X;子列表包含x，或者它們不包含。在前一種情況下，子列表由x組成，然後由其餘元素中選擇的元素組成。在後一種情況下，子列表包括從非x的元素中選擇的元素。這適用於（相當）簡單的遞歸定義。

（有非常非常強的相似性對recursive formula for binomial coefficients，預計。）

（編輯：刪除代碼，每dave4420的原因:)）

來源

2012-03-29 06:53:08 huon

寫一個函數來獲取Haskell中所有大小爲n的子序列？

回答

相關問題