算法来重新创建一个复杂的订单

我有麻烦做一个操作的算法，我想请求帮助。由于这是相当抽象的，这只是伪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

非常感谢您的链接，我会给它一个镜头并报告进度;） –

算法来重新创建一个复杂的订单

回答

相关问题