セットを列挙するより大きな問題の一部として、OCaml 関数 'choose' を書く必要があります。これはリストを取り、そのリストの要素から構成されるサイズ k のすべての可能なシーケンスのリストとして出力します (可能なシーケンスを繰り返すことなく)。順列によって互いに得られる）。それらが最終リストに入れられる順序は関係ありません。
例えば、
choose 2 [1;2;3;4] = [[1;2];[1;3];[1;4];[2;3];[2;4];[3;4]]
何か案は？
遅延リストを出力して全体を遅延させたいのですが、厳密な解決策があれば、それも非常に便利です。
これは、厳密で次善のバージョンです。明確であることを願っています。入力リストに重複がないと想定し、元のリストと同じ順序のサブリストのみを生成することで、重複を回避します。
l長さの計算は、 の長さを の引数として渡すことで因数分解できますchoose。これにより、コードが読みにくくなりますが、より効率的になります。
怠惰なバージョンの場合、コードに「lazy」と「Lazy.force」を振りかけます...
let rec choose k l =
if k = 0
then [ [] ]
else
let len = List.length l in
if len < k
then []
else if k = len
then [ l ]
else
match l with
h :: t ->
let starting_with_h =
(List.map (fun sublist -> h :: sublist) (choose (pred k) t))
in
let not_starting_with_h = choose k t in
starting_with_h @ not_starting_with_h
| [] -> assert false
;;
val choose : int -> 'a list -> 'a list list = <fun>
# choose 3 [1; 2; 3; 4; 5; 6; 7] ;;
- : int list list =
[[1; 2; 3]; [1; 2; 4]; [1; 2; 5]; [1; 2; 6]; [1; 2; 7]; [1; 3; 4]; [1; 3; 5];
[1; 3; 6]; [1; 3; 7]; [1; 4; 5]; [1; 4; 6]; [1; 4; 7]; [1; 5; 6]; [1; 5; 7];
[1; 6; 7]; [2; 3; 4]; [2; 3; 5]; [2; 3; 6]; [2; 3; 7]; [2; 4; 5]; [2; 4; 6];
[2; 4; 7]; [2; 5; 6]; [2; 5; 7]; [2; 6; 7]; [3; 4; 5]; [3; 4; 6]; [3; 4; 7];
[3; 5; 6]; [3; 5; 7]; [3; 6; 7]; [4; 5; 6]; [4; 5; 7]; [4; 6; 7]; [5; 6; 7]]
編集：
lazy_list_append以下のコメントから必要と思われるA ：
type 'a node_t =
| Empty
| Node of 'a * 'a zlist_t
and 'a zlist_t = 'a node_t lazy_t
let rec lazy_list_append l1 l2 =
lazy
(match Lazy.force l1 with
Empty -> Lazy.force l2
| Node (h, lt) ->
Node (h, lazy_list_append lt l2))
;;
Haskell ソリューションを再度プラグインします (レイジー リストは組み込みであるため、簡単に操作できます)。
combinations 0 _ = [[]]
combinations k [] = []
combinations k (x:xs) = map (x:) (combinations (k-1) xs) ++ combinations k xs
最初の 2 つのケースは、2項係数のプロパティから、より具体的には次のとおりn choose 0 = 1です。すべてnを含むn=0(これが最初に case を処理する理由です0 choose 0)。もう一つは0 choose k = 0. 3 番目の方程式は、組み合わせの再帰的な定義を正確に変換したものです。
残念ながら、それを無限リストに適用すると、簡単な解決策が返されます。
> take 10 $ combinations 3 [1..]
[[1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,2,7],[1,2,8],[1,2,9],[1,2,10],[1,2,11],[1,2,12]]
編集: では、有限数のステップで各組み合わせを実際に見ていきたいと思います。上記のバージョンでは、1 で始まる組み合わせのみを生成する左側の式のみを使用していることは明らか++です。この問題は、各引数の先頭を交互に選択してリストを作成する興味深いリスト zip 関数を定義することで回避できます。リスト (2 番目の引数で厳格でないことが重要です):
merge [] ys = ys
merge (x:xs) ys = x:merge ys xs
の代わりに使用します++。
combinations k (x:xs) = map (x:) (combinations (k-1) xs) `merge` combinations k xs
どれどれ：
> let comb_10_3 = combinations 3 [1..10]
> let comb_inf_3 = combinations 3 [1..]
> take 10 comb_inf_3
[[1,2,3],[2,3,4],[1,3,4],[3,4,5],[1,2,4],[2,4,5],[1,4,5],[4,5,6],[1,2,5],[2,3,5]]
> comb_10_3 `intersect` comb_inf_3 == comb_10_3
True
> last $ combinations 3 [1..10]
[6,8,10]
> elemIndex [6,8,10] $ combinations 3 [1..]
Just 351
すべての10 choose 3組み合わせがあります！
完全を期すために、Pascal からの厳密なコードと私の怠惰なコードおよび他のすべての Pascal の有用なコメントをまとめた最終的なコードをここに示します。
遅延リスト型が定義され、次に 2 つの補助遅延関数 (append と map)、そして最後に定義しようとしている関数 "choose" が定義されます。
type 'a node_t =
| Nil
| Cons of 'a * 'a t
and 'a t = ('a node_t) Lazy.t
let rec append l1 l2 =
match Lazy.force l1 with
| Nil -> l2
| Cons (a, l) -> lazy (Cons (a, append l l2))
let rec map f ll = lazy (
match Lazy.force ll with
| Nil -> Nil
| Cons(h,t) -> Cons(f h, map f t) )
let rec choose k l len =
if k = 0
then lazy (Cons(lazy Nil,lazy Nil))
else
if len < k
then lazy Nil
else if k = len
then lazy (Cons (l,lazy Nil))
else
match Lazy.force l with
| Cons(h,t) -> let g h sublist = lazy (Cons (h,sublist))
in let starting_with_h = (map (g h) (choose (k-1) t (len-1)))
in let not_starting_with_h = choose k t (len-1)
in append starting_with_h not_starting_with_h
| Nil -> assert false
"choose k ls n" を評価した結果は、リスト ls の k 個の要素のすべての選択肢の遅延リストであり、ls はサイズ n までと見なされます。Pascal が指摘したように、列挙が行われる方法のため、関数 choose は無限リストのすべての選択肢をカバーしないことに注意してください。
ありがとう、これは本当に役に立ちました！
最高、スリケーター。