算法來重新創建一個複雜的訂單

我有麻煩做一個操作的算法，我想請求幫助。由於這是相當抽象的，這只是僞C＃。算法來重新創建一個複雜的訂單

我有對象，這是在列表清單：

Object A 
Object B 
Object C

這份名單來自於一個存儲區，但用戶可以通過兩種方式在列表中創建新元素：複製一個對象或將兩個主題合併在一起。因此，用戶交互後的名單可能是這樣的：

Object A 
Object A1 - Clone of A 
Object B 
Object C 
Object BC - Merge of B and C

每一個新的對象存儲，它的「父（S）」，所以它可能是追查每個對象的來源。但有可能鏈複製並結合方式，使第三代可能是這樣的：

Object A 
Object A1 - Clone of A 
Object B 
Object A1B - Merge of A1 and B 
Object A1B2 - Cloe onf A1b 
Object C 
Object BC - Merge of B and C 
Object BC2 - Clone of BC

現在我堅持：有時候，這個名單必須從存儲例1中regenarated雖然很容易重新創建「簡單」的複製或合併對象，我無法想出一個好的算法來識別順序，在哪個組合中必須重新創建。查看迭代3：要重新創建A1B2，我必須首先克隆A1，然後將A1和B合併到A1B，然後克隆此對象。是否有某種算法可以確定必要的順序？

來源

2013-12-20 Christian Sauer

'ABC'，它是'A + BC'還是'AB + C'？你如何區分'A（B1）'和'（AB）1'之間的AB1？ –

可能是一個:(取決於用戶的選擇我存儲信息的immidiate帕內，所以美國廣播公司將知道它的父母 –

如果你知道父母，是不是這是一個簡單的情況遞歸地看着父母，然後扭轉秩序？ –

你的符號可以曖昧：

Object A 
    Object B 
    Object A1 - clone A 
    Object B1 - clone B 
    Object B2 - clone B1 
    Object A1B2 - is it a merge of A1 and B2 or clone of A1B1?

我建議使用（至少在內部）RPN（逆轉波蘭式），讓利，比如，操作是

' for clone 
    + for merge

因此，例如

A  - just A 
    A'  - clone A 
    A''  - clone A, then clone the result again 
    AB+  - merge A and B 
    A'B'+ - clone A, clone B, merge the clones 
    A'B+' - clone A, merge with B, clone the result 
    AB'+C'+' - A merged with cloned B merged with cloned C and finally cloned

RPN是明確和可容易轉變（可展開成RPN樹）到任何其他表示

來源

2013-12-20 08:22:41

你好德米特里，我不確定這是否真的有必要。在內部，所有的引用都被無條件地存儲 - 這是一個對象是一個克隆或一個合併。兩者同時是不可能的。我主要關心的是合併/克隆堆疊在一起的情況 –

我認爲你正在尋找Topological Sort，這賦予了偏序（這裏是算法的步驟），建立一個與部分順序一致的總順序。

要多解釋一下，你已經得到了每個目標和依賴項的列表。例如（拿你自己），「BC2」是一個目標，你通過克隆「BC」來構建它。因此，「BC2」的依賴關係是「BC」，因此，按照部分順序，您將擁有「BC」<「BC2」。

順便說一句（幫助理解而不是建議作爲解決問題的實際方法），這與make解決的問題完全相同。你會在一個Makefile是這樣表達這種想法：

BC2: BC 
    clone BC > BC2

即：BC2取決於BC，您通過克隆BC（用工具clone的製造的例子）建造。

有一個拓撲排序的示例實現，並在上面鏈接的維基百科頁面上有進一步的解釋。

來源

2013-12-20 09:34:49

非常感謝您的鏈接，我會給它一個鏡頭並報告進度;） –

算法來重新創建一個複雜的訂單

回答

相關問題