F#中的组合和排列

Question

我最近为F#项目编写了以下组合和排列函数,但我很清楚它们远未优化.

/// Rotates a list by one place forward.
let rotate lst =
    List.tail lst @ [List.head lst]

/// Gets all rotations of a list.
let getRotations lst =
    let rec getAll lst i = if i = 0 then [] else lst :: (getAll (rotate lst) (i - 1))
    getAll lst (List.length lst)

/// Gets all permutations (without repetition) of specified length from a list.
let rec getPerms n lst = 
    match n, lst with
    | 0, _ -> seq [[]]
    | _, [] -> seq []
    | k, _ -> lst |> getRotations |> Seq.collect (fun r -> Seq.map ((@) [List.head r]) (getPerms (k - 1) (List.tail r)))

/// Gets all permutations (with repetition) of specified length from a list.
let rec getPermsWithRep n lst = 
    match n, lst with
    | 0, _ -> seq [[]]
    | _, [] -> seq []
    | k, _ -> lst |> Seq.collect (fun x -> Seq.map ((@) [x]) (getPermsWithRep (k - 1) lst))
    // equivalent: | k, _ -> lst |> getRotations |> Seq.collect (fun r -> List.map ((@) [List.head r]) (getPermsWithRep (k - 1) r))

/// Gets all combinations (without repetition) of specified length from a list.
let rec getCombs n lst = 
    match n, lst with
    | 0, _ -> seq [[]]
    | _, [] -> seq []
    | k, (x :: xs) -> Seq.append (Seq.map ((@) [x]) (getCombs (k - 1) xs)) (getCombs k xs)

/// Gets all combinations (with repetition) of specified length from a list.
let rec getCombsWithRep n lst = 
    match n, lst with
    | 0, _ -> seq [[]]
    | _, [] -> seq []
    | k, (x :: xs) -> Seq.append (Seq.map ((@) [x]) (getCombsWithRep (k - 1) lst)) (getCombsWithRep k xs)

有没有人对如何加速这些功能(算法)有任何建议？我特别感兴趣的是如何改进排列(有和没有重复).回顾起来,涉及轮换列表的业务对我来说效率不高.

更新

这是我对该getPerms功能的新实现,受Tomas的回答启发.

不幸的是,它并不比现有的快.建议？

let getPerms n lst =
    let rec getPermsImpl acc n lst = seq {
        match n, lst with
        | k, x :: xs ->
            if k > 0 then
                for r in getRotations lst do
                    yield! getPermsImpl (List.head r :: acc) (k - 1) (List.tail r)
            if k >= 0 then yield! getPermsImpl acc k []
        | 0, [] -> yield acc
        | _, [] -> ()
        }
    getPermsImpl List.empty n lst

Answer 1

如果您想编写有效的功能代码,那么避免使用@运算符是个好主意,因为列表的连接效率非常低.

以下是如何编写函数以生成所有组合的示例:

let rec combinations acc size set = seq {
  match size, set with 
  | n, x::xs -> 
      if n > 0 then yield! combinations (x::acc) (n - 1) xs
      if n >= 0 then yield! combinations acc n xs 
  | 0, [] -> yield acc 
  | _, [] -> () }

combinations [] 3 [1 .. 4]

该函数的参数是:

• acc 用于记住已选择包含在组合中的元素(最初这是一个空列表)
• size是我们需要添加的剩余元素数acc(最初这是组合所需的大小)
• set 是可供选择的集合元素

该函数使用简单的递归实现.如果我们需要生成大小的组合,n那么我们可以添加或不添加当前元素,因此我们尝试使用两个选项(第一种情况)生成组合,并使用它们将所有这些组合添加到生成的序列中yield!.如果我们需要0个元素,那么我们成功地生成了一个组合(第二种情况),如果我们以其他数字结尾但没有剩余的元素可供使用,那么我们就不能返回任何内容(最后一种情况).

重复的组合将是类似的 - 区别在于您不需要从列表中删除元素(通过仅xs在递归调用中使用),因此有更多选项可以做什么.

Answer 2

我注意到你更新的getPerms函数包含重复项.这是我对无欺骗版本的破解.希望这些评论不言而喻.最难的部分是编写一个有效的distrib函数,因为连接运算符必须在某处使用.幸运的是它只用于小的子列表,因此性能仍然合理.下面我的getAllPerms代码在大约四分之一秒内生成[1..9]的所有排列,所有10个元素的排列大约在2.5秒内.

编辑:好笑,我没看过Tomas的代码,但他的组合功能和我的选择功能几乎相同.

// All ordered picks {x_i1, x_i2, .. , x_ik} of k out of n elements {x_1,..,x_n}
// where i1 < i2 < .. < ik
let picks n L = 
    let rec aux nleft acc L = seq {
        match nleft,L with
        | 0,_ -> yield acc
        | _,[] -> ()
        | nleft,h::t -> yield! aux (nleft-1) (h::acc) t
                        yield! aux nleft acc t }
    aux n [] L

// Distribute an element y over a list:
// {x1,..,xn} --> {y,x1,..,xn}, {x1,y,x2,..,xn}, .. , {x1,..,xn,y}
let distrib y L =
    let rec aux pre post = seq {
        match post with
        | [] -> yield (L @ [y])
        | h::t -> yield (pre @ y::post)
                  yield! aux (pre @ [h]) t }
    aux [] L

// All permutations of a single list = the head of a list distributed
// over all permutations of its tail
let rec getAllPerms = function
    | [] -> Seq.singleton []
    | h::t -> getAllPerms t |> Seq.collect (distrib h)

// All k-element permutations out of n elements = 
// all permutations of all ordered picks of length k combined
let getPerms2 n lst = picks n lst |> Seq.collect getAllPerms

编辑:响应评论的更多代码

// Generates the cartesian outer product of a list of sequences LL
let rec outerProduct = function
    | [] -> Seq.singleton []
    | L::Ls -> L |> Seq.collect (fun x -> 
                outerProduct Ls |> Seq.map (fun L -> x::L))

// Generates all n-element combination from a list L
let getPermsWithRep2 n L = 
    List.replicate n L |> outerProduct