Ocaml作業需要一些建議

我們有N組整數A1，A2，A3 ... An。發現返回一個列表方含從每個集合中的一個元素，與在列表中的最大和最小元件之間的差最小的特性的算法Ocaml作業需要一些建議

實施例：

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

我有一個想法，這個練習，首先我們需要排序的所有元素一個列表（每個元素需要分配給它的設置），所以與該輸入我們得到這樣的：

[[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的新手，所以我有編碼這個東西的一些問題：

我可以用N（無限量）參數創建一個函數嗎？
我應該創建一個新的類型，如對列表來實現假設嗎？

對不起，我的英語不好，希望你能明白我想表達的意思。

來源

2012-11-12 USER_

我只想回答你的問題，而不是評論你提出的解決方案。（但我認爲你必須要在它的工作多一點就大功告成了。）

您可以編寫一個函數，一個列表的列表。這與允許任意數量的參數幾乎相同。但它真的只有一個參數（就像OCaml中的所有函數一樣）。
您可以只使用列表和元組等內置類型，您不需要創建或顯式聲明它們。

下面是一個例子函數，它接受一個列表的列表和它們組合成一個大的長長的名單：

let rec concat lists = 
    match lists with 
    | [] -> [] 
    | head :: tail -> head @ concat tail

來源

2012-11-12 07:16:09

這裏是你的問題，讓你開始所描述的程序。請注意，我沒有注意效率。爲了清楚起見，還添加了反向應用（管道）操作員。

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-12 07:20:11 rgrinberg

這個答案是關於算法部分，而不是OCaml代碼。

您可能需要先實施您提出的解決方案，然後將其結果與我現在撰寫的改進解決方案進行比較。

以下是有關如何改進算法部分的提示。考慮排序所有集合，而不僅僅是第一個集合。現在，所有集合中所有最小元素的列表都是輸出的候選者。考慮其他候選人輸出，你如何從那裏移動？

來源

2012-11-12 09:51:57 jrouquie

你的方法聽起來並不非常有效，與n多套，每x_i elments，你的排序列表將有(n * x_i)元素，可以產生出該子列表的數量將是：(n * x_i)!（階乘）

我想提出一個不同的方法，但你必須工作的細節：

標籤（指數）與它的每個元素的集標識符（像你這樣做）。
分別對每組進行排序。
構建與您想要的結果完全相反！
優化！

我希望你能對自己搞清楚步驟3，4 ... :)

來源

2012-11-12 10:14:08

Ocaml作業需要一些建議

回答

相關問題