4

私は単純なアルゴリズムのように見えるものに苦労してきましたが、関数型のスタイルで表現するためのきれいな方法を見つけることができません。問題の概要は次のとおりです。2 つの配列 X と Y があるとします。

X = [| 1; 2; 2; 3; 3 |]
Y = [| 5; 4; 4; 3; 2; 2 |]

私が望むのは、次のように、一致する要素と一致しない要素を取得することです。

matched = [| 2; 2; 3 |]
unmatched = [| 1; 3 |], [| 4; 4; 5 |]

疑似コードでは、これは私が問題にアプローチすることを考える方法です:

let rec match matches x y =
    let m = find first match from x in y
    if no match, (matches, x, y)
    else
        let x' = remove m from x
        let y' = remove m from y
        let matches' = add m to matches
        match matches' x' y'

私が遭遇する問題はその"remove m from x"部分です-これを行うためのきれいな方法が見つかりません(動作するコードはありますが、それは地獄のように醜いです)。その問題にアプローチするための優れた慣用的な機能的な方法、削除部分、またはアルゴリズム自体を記述する別の方法はありますか?

4

2 に答える 2

3

マルチセット（バッグ）とその操作について説明しているようです。

適切なデータ構造を使用すると、操作は非常に簡単に実装できます。

// Assume that X, Y are initialized bags
let matches = X.IntersectWith(Y)
let x = X.Difference(Y)
let y = Y.Difference(X)

.NET フレームワークには組み込みの Bag コレクションはありません。上記の関数署名が取られるBag クラスを含む Power Collection ライブラリを使用できます。

アップデート：

弱昇順のリストでバッグを表すことができます。F# 構文での @kqr の回答の改良版を次に示します。

let overlap xs ys =
    let rec loop (matches, ins, outs) xs ys =
        match xs, ys with
        // found a match
        | x::xs', y::ys' when x = y -> loop (x::matches, ins, outs) xs' ys'
        // `x` is smaller than every element in `ys`, put `x` into `ins`
        | x::xs', y::ys' when x < y -> loop (matches, x::ins, outs) xs' ys
        // `y` is smaller than every element in `xs`, put `y` into `outs`
        | x::xs', y::ys' -> loop (matches, ins, y::outs) xs ys'
        // copy remaining elements in `xs` to `ins`
        | x::xs', [] -> loop (matches, x::ins, outs) xs' ys
        // copy remaining elements in `ys` to `outs`
        | [], y::ys' -> loop (matches, ins, y::outs) xs ys'
        | [], [] -> (List.rev matches, List.rev ins, List.rev outs)
    loop ([], [], []) (List.sort xs) (List.sort ys)

List.sortおそらく である を2 回呼び出した後O(nlogn)、一致を見つけることは、2 つのリストの長さの合計に比例します。

手っ取り早いバッグ モジュールが必要な場合は、次のようなモジュール シグネチャをお勧めします。

type Bag<'T> = Bag of 'T list

module Bag =
    val count : 'T -> Bag<'T> -> int
    val insert : 'T -> Bag<'T> -> Bag<'T>
    val intersect : Bag<'T> -> Bag<'T> -> Bag<'T>
    val union : Bag<'T> -> Bag<'T> -> Bag<'T>
    val difference : Bag<'T> -> Bag<'T> -> Bag<'T>
于 2013-06-07T23:31:11.723 に答える