0

N セットの整数 A1、A2、A3 ... An があります。リスト内の最大要素と最小要素の差が最小であるというプロパティを使用して、各セットから 1 つの要素を含むリストを返すアルゴリズムを見つけます

例：

IN: A1 = [0,4,9], A2 = [2,6,11], A3 = [3,8,13], A4 = [7,12]
OUT: [9,6,8,7]

私はこの演習についてのアイデアを持っています。まず、1 つのリストのすべての要素を並べ替える必要があるため (すべての要素をそのセットに割り当てる必要があります)、その入力で次のようになります。

[[0,1],[2,2],[3,3],[4,1],[6,2],[7,4],[8,3],[9,1],[11,2],[12,4],[13,3]]

後で、考えられるすべてのリストを作成し、最小要素と最大要素の差でこのリストを見つけ、次のように正しい結果を返します。[9,6,8,7]

私は ocaml の初心者なので、このようなコーディングについていくつか質問があります。

  1. N 個 (無限個) の引数を持つ関数を作成できますか?
  2. 仮定を実現するためにペアのリストのような新しいタイプを作成する必要がありますか?

下手な英語で申し訳ありませんが、私が表現したかったことを理解していただければ幸いです。

4

4 に答える 4

1

この回答は、OCaml コードではなく、アルゴリズム部分に関するものです。

提案されたソリューションを最初に実装して、機能するソリューションを作成し、その結果を改善されたソリューションと比較することをお勧めします。これについては、今書いています。

アルゴリズムの部分を改善する方法についてのヒントを次に示します。最初のセットだけでなく、すべてのセットをソートすることを検討してください。これで、すべてのセットからのすべての最小要素のリストが出力の候補になります。他の候補出力を検討するには、そこからどのように移行できますか?

于 2012-11-12T09:51:57.113 に答える
0

あなたのアプローチは非常に効率的ではありませんn。それぞれに要素x_iがあり、ソートされたリストには(n * x_i)要素があり、そこから生成できるサブリストの数は次のようになります:((n * x_i)!階乗)

別のアプローチを提案したいのですが、詳細を検討する必要があります。

  1. 各要素にそのセット識別子をタグ付け（インデックス）します（行ったように）。

  2. 各セットを個別に並べ替えます。

  3. 希望する結果とは正反対のものを構築してください!

  4. 最適化！

手順 3 と 4 を自分で理解していただければ幸いです... :)

于 2012-11-12T10:14:08.810 に答える
0

提案された解決策についてコメントするのではなく、質問に答えるだけです。(しかし、完了する前にもう少し作業する必要があると思います。)

  1. リストのリストを取る関数を書くことができます。これは、任意の数の引数を許可することとほとんど同じです。しかし、実際には引数が 1 つしかありません (OCaml のすべての関数と同様)。

  2. リストやタプルなどの組み込み型を使用するだけで、明示的に作成または宣言する必要はありません。

リストのリストを取り、それらを 1 つの大きな長いリストに結合する関数の例を次に示します。

let rec concat lists =
  match lists with
  | [] -> []
  | head :: tail -> head @ concat tail
于 2012-11-12T07:16:09.057 に答える
0

これが、質問で説明したルーチンであり、開始するためのものです。効率性には注意を払っていないことに注意してください。わかりやすくするために、逆適用 (パイプ) 演算子も追加されました。

let test_set = [[0;4;9];[2;6;11];[3;8;13]; [7;12]] 

let (|>) g f = f g

let linearize sets = 
  let open List in sets 
    |> mapi (fun i e -> e |> map (fun x -> (x, i+1) )) 
    |> flatten |> sort (fun (e1,_) (e2, _) -> compare e1 e2)

let sorted = linearize test_set
于 2012-11-12T07:20:11.237 に答える