リストを要素数が指定されたグループで分ける

Quiz

次をみたす関数groupsを定義せよ。

groups [p_1, p_2, ..., p_n] list

は

{ {s_1, s_2, ..., s_n} | s_i ⊂ list, #s_i = p_i, s_i ∩ s_j = φ }

を返す。

順序は(与えられたリストの並びを基準にして)Haskellのsortが並べる順であることが望ましい。

例

*Grouping> groups [1,3] [1..4]
[[[1],[2,3,4]],[[2],[1,3,4]],[[3],[1,2,4]],[[4],[1,2,3]]]
*Grouping> groups [2,2] [1..4]
[[[1,2],[3,4]],[[1,3],[2,4]],[[1,4],[2,3]],[[2,3],[1,4]],[[2,4],[1,3]],[[3,4],[1,2]]]
*Grouping> groups [2,1] [1..4]
[[[1,2],[3]],[[1,2],[4]],[[1,3],[2]],[[1,3],[4]],[[1,4],[2]],[[1,4],[3]],[[2,3],[1]],[[2,3],[4]],[[2,4],[1]],[[2,4],[3]],[[3,4],[1]],[[3,4],[2]]]

背景

組合せ的な問題では以下のようなリストを生成することがよくある。

	[(x, delete x xs) | x <- xs]

deleteせずにこれを生成するものを書こうと思ったが、ただ書いても面白くないので、一般化してみた。