K out on N 实现 - SML

Question

我试图在 SML 实现 k-out-of-N，所以 "pick(3,[1,2,3,4])" 将 return [[1,2,3],[1,3,4]... ]（所有K尺寸从N个元素中挑出）

我使用了 List.map，我认为它调用函数并将其应用于每个元素。

真的想不通为什么输入 "pick(3,[1,2,3,4,5])" 时，例如 return 是一个空列表。

我的第一个想法是因为初始条件 (选择 (_,[]) = []) 但是改变它也没有用。

签名没问题（val pick = fn : int * 'a list -> 'a list list）。

fun pick (_,[]) = []
    | pick (0,_) = []
    | pick (n,hd::tl) =
      let
        val with_hd = List.map (fn x => hd::x) (pick(n-1,tl))
        val without_hd = pick(n,tl)
      in
      with_hd@without_hd
 end;

Answer 1

问题与您的怀疑有关 – 基本情况不正确，因为它们总是生成空列表，并且将 fn x => hd::x 映射到空列表会生成空列表。

从任何对象中选取零个元素应该会成功，并生成空列表。
即，pick (0, _) = [[]] — 一个只有一个元素的列表，即空列表。

您还需要重新排列案例，因为 pick(n, []) 对 n = 0 成功，但对任何其他 n 都不成功。

综上所述，

fun pick (0, _) = [[]]
  | pick (_, []) = []

其余功能与以前完全相同。

K out on N 实现 - SML

K out on N implementation - SML

ml

sml

smlnj