6

我已经在 F# 中实现了一个标准的可变就地排列算法（如果有一些内置的方法可以做类似的事情，我将不胜感激）：

let permutations f (alphabet:'a array) =
    let swap i j =
        let aux = alphabet.[i]
        alphabet.[i] <- alphabet.[j]
        alphabet.[j] <- aux
    let rec permutations' n =
        if n = alphabet.Length
        then f alphabet
        else
            for i in n..(alphabet.Length-1) do
                swap n i
                permutations' (n+1)
                swap n i
    permutations' 0

尽管该函数非常通用，但我想知道 F# 中是否有某种方法可以实现一个包装函数，它将发现的项目作为一个序列生成。类似于以下（不正确的）F# 方法的东西：

let permutations_seq (alphabet:'a array) =
    seq {
        permutations (fun arr -> yield arr.Clone()) alphabet
    }

在permutations我不想直接yield因为我想保持功能通用并且我不希望客户总是要为阵列克隆付出代价。

你会怎么做？

4

3 回答 3

3

如果你想从 lambda 函数中“产生”结果，那么 lambda 函数本身需要返回一个序列（因此 lambda 函数的调用者也需要返回一个序列）。因此，如果不修改permutations函数，就无法获得您想要的东西（因为您无法将在一个（嵌套）范围内运行的代码产生值到在其他（外部）范围内定义的列表）。

但是，您可以更改permutations为如下所示：

let permutations f (alphabet:'a array) =
    let swap i j =
        let aux = alphabet.[i]
        alphabet.[i] <- alphabet.[j]
        alphabet.[j] <- aux
    let rec permutations' n = seq {
        if n = alphabet.Length
        then yield! f alphabet
        else
            for i in n..(alphabet.Length-1) do
                swap n i
                yield! permutations' (n+1)
                swap n i }
    permutations' 0

我包装permutations'在seq { .. }块中并yield!在之前添加f alphabet（以便函数生成的所有元素f都作为结果传递），我还添加yield!到递归调用中。

然后你可以写：

permutations (fun arr -> seq { yield arr |> Array.map id }) [|1;2;3|]

代码使用Array.map id代替，Clone以便您获得数组的类型安全副本，而不是obj.NET 克隆机制返回的副本。

但是，我认为您实际上不需要从 lambda 生成多个项目，因此您可以更改yield! f alphabet为 just yield f alphabet（仅返回单个元素而不是多个元素）并编写：

permutations (fun arr -> arr |> Array.map id) [|1;2;3|]

这样，您 - 至少 - 获得了一种抽象克隆行为的好方法（并且您可以选择克隆或不轻松克隆数组）。

于 2013-06-17T10:46:45.043 回答
1

您必须生成未克隆的数组。有一个明显的奇怪行为，如果你在序列上调用 toList，那么你会得到一个数组的最后一个值的数组。所以你要做的第一件事就是Seq.map使用克隆功能。另外，如果您已经准备好使用可变对象，我认为没有必要让您的函数递归。

let permutations (alphabet:'a array) =
    let swap i j =
        let aux = alphabet.[i]
        alphabet.[i] <- alphabet.[j]
        alphabet.[j] <- aux
    let rec permutations' n = 
        seq {
                if n = alphabet.Length
                then yield alphabet
                else
                    for i in n..(alphabet.Length-1) do
                        swap n i
                        yield! permutations' (n+1)
                        swap n i
        }
    permutations' 0


let a = [|"a"; "b"; "c"; "d"|]
let p =
    (permutations a)
    |> Seq.map (fun arr -> arr.Clone() )
    |> Seq.toList

输出

  val p : obj list =
  [[|"a"; "b"; "c"; "d"|]; [|"a"; "b"; "d"; "c"|]; [|"a"; "c"; "b"; "d"|];
   [|"a"; "c"; "d"; "b"|]; [|"a"; "d"; "c"; "b"|]; [|"a"; "d"; "b"; "c"|];
   [|"b"; "a"; "c"; "d"|]; [|"b"; "a"; "d"; "c"|]; [|"b"; "c"; "a"; "d"|];
   [|"b"; "c"; "d"; "a"|]; [|"b"; "d"; "c"; "a"|]; [|"b"; "d"; "a"; "c"|];
   [|"c"; "b"; "a"; "d"|]; [|"c"; "b"; "d"; "a"|]; [|"c"; "a"; "b"; "d"|];
   [|"c"; "a"; "d"; "b"|]; [|"c"; "d"; "a"; "b"|]; [|"c"; "d"; "b"; "a"|];
   [|"d"; "b"; "c"; "a"|]; [|"d"; "b"; "a"; "c"|]; [|"d"; "c"; "b"; "a"|];
   [|"d"; "c"; "a"; "b"|]; [|"d"; "a"; "c"; "b"|]; [|"d"; "a"; "b"; "c"|]]
于 2013-06-16T07:20:17.203 回答
1

如果您真的想使用回调 ( reactive) 方法，请使用响应式扩展

https://github.com/fsharp/FSharp.Reactive/blob/master/src/Observable.fs

和写

let permutations (alphabet:'a array) =
    Observable.create (fun subscriber ->
      let swap i j =
          let aux = alphabet.[i]
          alphabet.[i] <- alphabet.[j]
          alphabet.[j] <- aux
      let rec permutations' n = 
          seq {
                  if n = alphabet.Length
                  then subscriber.OnNext(alphabet)
                  else
                      for i in n..(alphabet.Length-1) do
                          swap n i
                          permutations' (n+1)
                          swap n i
          }
      permutations' 0
    )

然后你可以做

permutations [|"a"; "b"; "c"|]
|> Observable.map ( fun arr -> arr.Clone() )
|> Observable.ToEnumerable
|> Seq.ToList

但是请注意关于我基于产量发布的其他答案的对称性，因此在这种情况下您不会获得太多收益。

于 2013-06-16T07:59:42.217 回答