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

ラムダ関数から結果を「生成」したい場合は、ラムダ関数自体がシーケンスを返す必要があります (したがって、ラムダ関数の呼び出し元もシーケンスを返す必要があります)。そのため、関数を変更せずに必要なものを取得する方法はありません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 alphabetfyield!

次に、次のように記述できます。

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

このコードでは、.NET クローン作成メカニズムによって返されるではなく、タイプ セーフな配列のコピーを取得するために、Array.map id代わりに を使用しています。Cloneobj

ただし、実際にはラムダから複数のアイテムを生成する必要はないと思うので、yield! f alphabetjust に変更して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 に答える