因为小编主要使用Python实现,可能描述中会有Python语梗在里面。
进入正题:
例如:我有个数组对象 object[30] = new object[] {a0,b1,...x29 },我们暂定数组objectA 里面有30个对象。已知有很多数组元素中的大小关系。比方说:
已知 a0 < b1; b1 > x29 等。请满足条件的所有排列组合并展示,排列时小的在前,大的在后。
注意:a0 < b1 只能说明 ...a0 ..b1... 可能存在这样的排列不能说明 a0 后紧跟着 b1 。
我已经描述的很通俗,主要寻求满足这样的排列的最优方案,如有能有python 代码实现最好。VB.net,C# 也可以。也能看懂。或者说出一个解决方案也行,我来构代码。
另外说明一点:我现在的处理方式是先穷举所有排列后,然后逐个判断的每个数组元素的前后关系。说白了就是完全采用剔除方法实现。这样的缺点所有人都很能理解,比方说数组对象有100个时,常态的电脑就算多开线程/进程都很难实现。在没有量子计算机的时代,这种方式太low了。
可以参考拓扑排序,但是这个要求每个元素之间必须有依赖关系。你这个题目并没有说到每个元素之间有必定的依赖关系,所以可能还会需要穷举,但是比完全穷举强
最长链表
知道这个你自己就可以百度到,我也不赘述了
因为我们无法确定你给定的事实论据是否完备(逻辑式编程,事实--》推论),所以我们只能说利用链表求最长链表,或者利用图/树遍历
如果是你能确保事实论据完备,其实也不必用链表和图,直接进行快速排序算法就好
比如C#的 Array.Sort(object[] array, 比较器)
你看到了,快速排序+比较器,你给的事实论据不就是比较器么?所以如果说事实是完备的,那么直接快排就好
问题补充:我把实际遇到问题场景详细说明下。
问题:例如我有100个工序(工序1→工序100)。已知部分而非所有工序相对位置 (工序18 必需在 工序21 之前 并且在 工序1 之后 即: 工序1 < 工序18 < 工序21;工序19必须在工序5之后 即 工序5 < 工序19;... 类似于这种条件。已知条件里面并不是所有工序都有相对位置,没有描述的可以任意排列)。
求解?:求出满足以上要求的所有排列清单。最终结果我不是求满足条件排列个数,我想要知道怎么才能快速求解出清单。
我现有方法(该方法穷举次数太多,2年也算不完):首先先求解出100个工序的排列的迭代器(数量=100! = 9.332621544394418e+157) ,然后每种结果 都去 和 条件集判断,只要有个不满足就剔除。这样方式就算计算机能开1000个线程/进程 来算,我估测要算到下一个纪元。希望统计学大咖协助。csdn智囊大师你在哪里?来改变世界你该出现解决这个问题了。