n个元素排序自动生成代码的方法
Approach to automatically generate code for sorting n elements
根据维基百科上的 this article，根据 n 个数字对列表进行排序的理论最小值是：log (n!)
我已经设法编写了相当 "large" 的代码来排序最多 5 个元素的列表，用于排序 8 个元素列表的排序树代码将大约 60000 行长，并且人类不可能写.
请注意，虽然易于实现的排序网络既不是我所需要的，也不是比较或操作中的极简主义，因为我正在寻找线性排序方法（没有并行性）
我正在尝试找到一种编写程序的方法来编写我需要的程序。我偏向 python.
中的输出代码
我的障碍
- 我什至无法在 16 次比较中对 1 个 8 列表进行排序，所以我完全错过了基本算法，因此我需要一些指向该算法的文献。我看过有关对 6 个元素进行排序的文献，但无法将逻辑扩展到 8 个
- 假设我能够计算出算法，那么自动生成代码的最佳方法是什么。
编辑
在研究并设法设计大小为 8、9、10 的排序树后，它引起了我的注意。这是徒劳的。即使用 c 语言或直接用汇编语言实现，因为源代码的大小呈指数级增长。我创建了一个用于排序树 n = 8 的 c dll，它的大小为 10 MB。对于 9 达到 100 MB，对于 10，编译器根本无法至少在我的系统上创建 DLL。如果我将树分解成更小的函数，那么大小就会急剧减小，性能就会下降。所以没有必要进一步研究这个话题
这里是 sort5 的代码，我想得到 sort8 的类似代码
def sort5(a,b,c,d,e):
if a > b:
# a > b
if c > d:
# a > b ; c > d
if a > c:
# a > c > d ; a > b; 15 returns
if e > c:
if e > a:
# e > a > c > d; a > b
if b > d:
if b > c:
return [e, a, b, c, d]
else:
return [e, a, c, b, d]
else:
return [e, a, c, d, b]
else:
# a > e > c > d; a > b
if b > c:
if b > e:
return [a, b, e, c, d]
else:
return [a, e, b, c, d]
else:
if b > d:
return [a, e, c, b, d]
else:
return [a, e, c, d, b]
else:
if e > d:
# a > c > e > d; a > b
if b > e:
if b > c:
return [a, b, c, e, d]
else:
return [a, c, b, e, d]
else:
if b > d:
return [a, c, e, b, d]
else:
return [a, c, e, d, b]
else:
# a > c > d > e ; a > b
if b > d:
if b > c:
return [a, b, c, d, e]
else:
return [a, c, b, d, e]
else:
if b > e:
return [a, c, d, b, e]
else:
return [a, c, d, e, b]
else:
# c > a > b ; c > d; 15 returns
if e > a:
if e > c:
# e > c > a > b; c > d
if d > b:
if d > a:
return [e, c, d, a, b]
else:
return [e, c, a, d, b]
else:
return [e, c, a, b, d]
else:
# c > e > a > b; c > d
if d > a:
if d > e:
return [c, d, e, a, b]
else:
return [c, e, d, a, b]
else:
if d > b:
return [c, e, a, d, b]
else:
return [c, e, a, b, d]
else:
if e > b:
# c > a > e > b; c > d
if d > e:
if d > a:
return [c, d, a, e, b]
else:
return [c, a, d, e, b]
else:
if d > b:
return [c, a, e, d, b]
else:
return [c, a, e, b, d]
else:
# c > a > b > e ; c > d
if d > b:
if d > a:
return [c, d, a, b, e]
else:
return [c, a, d, b, e]
else:
if d > e:
return [c, a, b, d, e]
else:
return [c, a, b, e, d]
else:
# a > b ; d > c
if a > d:
# a > d > c ; a > b; 15 returns
if e > d:
if e > a:
# e > a > d > c; a > b
if b > c:
if b > d:
return [e, a, b, d, c]
else:
return [e, a, d, b, c]
else:
return [e, a, d, c, b]
else:
# a > e > d > c; a > b
if b > d:
if b > e:
return [a, b, e, d, c]
else:
return [a, e, b, d, c]
else:
if b > c:
return [a, e, d, b, c]
else:
return [a, e, d, c, b]
else:
if e > c:
# a > d > e > c; a > b
if b > e:
if b > d:
return [a, b, d, e, c]
else:
return [a, d, b, e, c]
else:
if b > c:
return [a, d, e, b, c]
else:
return [a, d, e, c, b]
else:
# a > d > c > e ; a > b
if b > c:
if b > d:
return [a, b, d, c, e]
else:
return [a, d, b, c, e]
else:
if b > e:
return [a, d, c, b, e]
else:
return [a, d, c, e, b]
else:
# d > a > b ; d > c; 15 returns
if e > a:
if e > d:
# e > d > a > b; d > c
if c > b:
if c > a:
return [e, d, c, a, b]
else:
return [e, d, a, c, b]
else:
return [e, d, a, b, c]
else:
# d > e > a > b; d > c
if c > a:
if c > e:
return [d, c, e, a, b]
else:
return [d, e, c, a, b]
else:
if c > b:
return [d, e, a, c, b]
else:
return [d, e, a, b, c]
else:
if e > b:
# d > a > e > b; d > c
if c > e:
if c > a:
return [d, c, a, e, b]
else:
return [d, a, c, e, b]
else:
if c > b:
return [d, a, e, c, b]
else:
return [d, a, e, b, c]
else:
# d > a > b > e ; d > c
if c > b:
if c > a:
return [d, c, a, b, e]
else:
return [d, a, c, b, e]
else:
if c > e:
return [d, a, b, c, e]
else:
return [d, a, b, e, c]
else:
# b > a
if c > d:
# b > a ; c > d
if b > c:
# b > c > d ; b > a; 15 returns
if e > c:
if e > b:
# e > b > c > d; b > a
if a > d:
if a > c:
return [e, b, a, c, d]
else:
return [e, b, c, a, d]
else:
return [e, b, c, d, a]
else:
# b > e > c > d; b > a
if a > c:
if a > e:
return [b, a, e, c, d]
else:
return [b, e, a, c, d]
else:
if a > d:
return [b, e, c, a, d]
else:
return [b, e, c, d, a]
else:
if e > d:
# b > c > e > d; b > a
if a > e:
if a > c:
return [b, a, c, e, d]
else:
return [b, c, a, e, d]
else:
if a > d:
return [b, c, e, a, d]
else:
return [b, c, e, d, a]
else:
# b > c > d > e ; b > a
if a > d:
if a > c:
return [b, a, c, d, e]
else:
return [b, c, a, d, e]
else:
if a > e:
return [b, c, d, a, e]
else:
return [b, c, d, e, a]
else:
# c > b > a ; c > d; 15 returns
if e > b:
if e > c:
# e > c > b > a; c > d
if d > a:
if d > b:
return [e, c, d, b, a]
else:
return [e, c, b, d, a]
else:
return [e, c, b, a, d]
else:
# c > e > b > a; c > d
if d > b:
if d > e:
return [c, d, e, b, a]
else:
return [c, e, d, b, a]
else:
if d > a:
return [c, e, b, d, a]
else:
return [c, e, b, a, d]
else:
if e > a:
# c > b > e > a; c > d
if d > e:
if d > b:
return [c, d, b, e, a]
else:
return [c, b, d, e, a]
else:
if d > a:
return [c, b, e, d, a]
else:
return [c, b, e, a, d]
else:
# c > b > a > e ; c > d
if d > a:
if d > b:
return [c, d, b, a, e]
else:
return [c, b, d, a, e]
else:
if d > e:
return [c, b, a, d, e]
else:
return [c, b, a, e, d]
else:
# b > a ; d > c
if b > d:
# b > d > c ; b > a; 15 returns
if e > d:
if e > b:
# e > b > d > c; b > a
if a > c:
if a > d:
return [e, b, a, d, c]
else:
return [e, b, d, a, c]
else:
return [e, b, d, c, a]
else:
# b > e > d > c; b > a
if a > d:
if a > e:
return [b, a, e, d, c]
else:
return [b, e, a, d, c]
else:
if a > c:
return [b, e, d, a, c]
else:
return [b, e, d, c, a]
else:
if e > c:
# b > d > e > c; b > a
if a > e:
if a > d:
return [b, a, d, e, c]
else:
return [b, d, a, e, c]
else:
if a > c:
return [b, d, e, a, c]
else:
return [b, d, e, c, a]
else:
# b > d > c > e ; b > a
if a > c:
if a > d:
return [b, a, d, c, e]
else:
return [b, d, a, c, e]
else:
if a > e:
return [b, d, c, a, e]
else:
return [b, d, c, e, a]
else:
# d > b > a ; d > c; 15 returns
if e > b:
if e > d:
# e > d > b > a; d > c
if c > a:
if c > b:
return [e, d, c, b, a]
else:
return [e, d, b, c, a]
else:
return [e, d, b, a, c]
else:
# d > e > b > a; d > c
if c > b:
if c > e:
return [d, c, e, b, a]
else:
return [d, e, c, b, a]
else:
if c > a:
return [d, e, b, c, a]
else:
return [d, e, b, a, c]
else:
if e > a:
# d > b > e > a; d > c
if c > e:
if c > b:
return [d, c, b, e, a]
else:
return [d, b, c, e, a]
else:
if c > a:
return [d, b, e, c, a]
else:
return [d, b, e, a, c]
else:
# d > b > a > e ; d > c
if c > a:
if c > b:
return [d, c, b, a, e]
else:
return [d, b, c, a, e]
else:
if c > e:
return [d, b, a, c, e]
else:
return [d, b, a, e, c]
此代码基本上构建了一个二叉树，其中特定深度的所有节点都具有 a>b 种关系。现在对于 n 个参数，将有 n*(n-1)/2 个这样的关系，这将是我们树的深度。
现在我们尝试将所有 n! 可能的输出数组推送到这棵树中。请注意，数组可以表示为 n-1 a>b 种关系，例如 'acb' -> a>c,c>b。现在将此类依赖项插入到树中（下面代码中的arr_conds）有点像插入到二叉搜索树中。假设对于深度 3 的所有节点，我们有 c>e。所以要插入 abcde 我们向左，对于 aebdc 我们向右。
此代码已针对最多 7 个元素（~22k 行！！）进行了测试。它到目前为止有效，但这绝对不能替代标准排序算法。更多细节请参考评论。
from itertools import permutations,combinations
import sys
from copy import deepcopy
sys.stdout = open("file.py","w")
N = 7
params = list(chr(97+i) for i in range(N))
permutes = list(permutations(params)) #all possbl outputs of sort function
conds = list(combinations(params,2)) #n*(n-1)/2 such conditions for each depth
conds = {i:conds[i] for i in range(len(conds))} #assign each to a particular depth
class Node:
def __init__(self,depth):
self.d = depth
self.left = None
self.right = None
def insert(self,arr_conds,arr):
if arr_conds==[]: #all n-1 conditions fulfilled, just insert
self.arr = deepcopy(arr);
return
for c in arr_conds: #one of n-1 conditions directly matched,remove it
if set(conds[self.d])==set(c):
arr_conds.remove(c)
src,dst = conds[self.d] #BST like part,recursive insertion
if arr.index(src)<arr.index(dst):
if not self.left: self.left = Node(self.d+1)
self.left.insert(arr_conds,arr)
else:
if not self.right: self.right = Node(self.d+1)
self.right.insert(arr_conds,arr)
def vis(self,sp=""):
if 'arr' in self.__dict__:
s = ','.join(self.arr)
print(sp,"return [",s,"]",sep='')
else:
x,y = conds[self.d]
if self.left:
print(sp,f"if {x}>{y}:",sep='')
self.left.vis(sp+" "*4)
if self.right:
if self.left:
print(sp,"else:",sep='')
else:
print(sp,f"if {y}>{x}:",sep='')
self.right.vis(sp+" "*4)
root = Node(0)
for p in permutes: #for all possbl answers...
arr_conds = [(p[i],p[i+1]) for i in range(N-1)]
root.insert(arr_conds,p) #insert their n-1 conditions into tree
print(f"def sort({','.join(params)}):")
root.vis(" ") #print actual tree...which is our generated code
print("print(sort(33,122,16,2,88,8,9))")
sys.stdout.close()
输出是同一文件夹中的 file.py。
这是另一个程序，但没有经过很好的测试。它产生简单的伪代码。我检查了 N=8，它生成了所有 8 个！可能的结果。
它使用索引 0, 1, 2, ... 而不是 a, b, c, ...。比较 1 和 2 表示比较第 1 项和第 2 项。
Ordering class 跟踪数字之间的关系。如果我们还不知道两个数字中哪个大哪个小，那么这对数字是无序的。比较使这对有序。当没有剩余的无序对时，整个列表完全排序。
代码生成器递归地选择一个随机无序对并首先更新 Ordering 就好像顺序是 a < b 然后好像顺序是相反的 a > b 从而创建两个分支机构（IF 和 ELSE）。
我觉得唯一有点棘手的部分是从 a > b 和 b > c 中推导出 a > c。为简单起见，程序为每个数字维护两组已知为 smaller/larger 的数字。为了简化代码，等号本身也是集合的一部分。
import itertools
class Ordering:
def __init__(self, n):
if isinstance(n, type(self)):
# make a copy
self.unordered = n.unordered.copy()
self.le = {i: le.copy() for i, le in n.le.items()}
self.ge = {i: ge.copy() for i, ge in n.ge.items()}
else:
# initialize for N *distinct* items
self.unordered = set(frozenset(pair) for pair in itertools.combinations(range(n), 2))
self.le = {i: set((i,)) for i in range(n)} # less or equal
self.ge = {i: set((i,)) for i in range(n)} # greater or equal
def a_is_less_than_b(self, a, b):
def discard(x, y):
self.unordered.discard(frozenset((x, y)))
for i in self.le[a]:
for j in self.ge[b]:
self.ge[i].add(j)
discard(i, j)
for i in self.ge[b]:
for j in self.le[a]:
self.le[i].add(j)
discard(i, j)
def final_result(self):
# valid only if self.unordered is empty
return [item[1] for item in sorted((len(le), i) for i, le in self.le.items())]
def codegen(oo, level=0):
def iprint(*args):
print(' ' * (2*level+1), *args) # indented print
if oo.unordered:
x, y = iter(next(iter(oo.unordered))) # random pair from set
copy = Ordering(oo)
iprint("IF [{}] < [{}]:".format(x, y))
oo.a_is_less_than_b(x, y)
codegen(oo, level+1)
iprint("ELSE:" )
copy.a_is_less_than_b(y, x)
codegen(copy, level+1)
else:
iprint("RESULT", oo.final_result());
if __name__ == '__main__':
N=4
codegen(Ordering(N))
根据维基百科上的 this article，根据 n 个数字对列表进行排序的理论最小值是：log (n!)
我已经设法编写了相当 "large" 的代码来排序最多 5 个元素的列表，用于排序 8 个元素列表的排序树代码将大约 60000 行长，并且人类不可能写.
请注意，虽然易于实现的排序网络既不是我所需要的，也不是比较或操作中的极简主义，因为我正在寻找线性排序方法（没有并行性）
我正在尝试找到一种编写程序的方法来编写我需要的程序。我偏向 python.
中的输出代码我的障碍
- 我什至无法在 16 次比较中对 1 个 8 列表进行排序，所以我完全错过了基本算法，因此我需要一些指向该算法的文献。我看过有关对 6 个元素进行排序的文献，但无法将逻辑扩展到 8 个
- 假设我能够计算出算法，那么自动生成代码的最佳方法是什么。
编辑 在研究并设法设计大小为 8、9、10 的排序树后，它引起了我的注意。这是徒劳的。即使用 c 语言或直接用汇编语言实现，因为源代码的大小呈指数级增长。我创建了一个用于排序树 n = 8 的 c dll，它的大小为 10 MB。对于 9 达到 100 MB，对于 10，编译器根本无法至少在我的系统上创建 DLL。如果我将树分解成更小的函数，那么大小就会急剧减小，性能就会下降。所以没有必要进一步研究这个话题
这里是 sort5 的代码，我想得到 sort8 的类似代码
def sort5(a,b,c,d,e):
if a > b:
# a > b
if c > d:
# a > b ; c > d
if a > c:
# a > c > d ; a > b; 15 returns
if e > c:
if e > a:
# e > a > c > d; a > b
if b > d:
if b > c:
return [e, a, b, c, d]
else:
return [e, a, c, b, d]
else:
return [e, a, c, d, b]
else:
# a > e > c > d; a > b
if b > c:
if b > e:
return [a, b, e, c, d]
else:
return [a, e, b, c, d]
else:
if b > d:
return [a, e, c, b, d]
else:
return [a, e, c, d, b]
else:
if e > d:
# a > c > e > d; a > b
if b > e:
if b > c:
return [a, b, c, e, d]
else:
return [a, c, b, e, d]
else:
if b > d:
return [a, c, e, b, d]
else:
return [a, c, e, d, b]
else:
# a > c > d > e ; a > b
if b > d:
if b > c:
return [a, b, c, d, e]
else:
return [a, c, b, d, e]
else:
if b > e:
return [a, c, d, b, e]
else:
return [a, c, d, e, b]
else:
# c > a > b ; c > d; 15 returns
if e > a:
if e > c:
# e > c > a > b; c > d
if d > b:
if d > a:
return [e, c, d, a, b]
else:
return [e, c, a, d, b]
else:
return [e, c, a, b, d]
else:
# c > e > a > b; c > d
if d > a:
if d > e:
return [c, d, e, a, b]
else:
return [c, e, d, a, b]
else:
if d > b:
return [c, e, a, d, b]
else:
return [c, e, a, b, d]
else:
if e > b:
# c > a > e > b; c > d
if d > e:
if d > a:
return [c, d, a, e, b]
else:
return [c, a, d, e, b]
else:
if d > b:
return [c, a, e, d, b]
else:
return [c, a, e, b, d]
else:
# c > a > b > e ; c > d
if d > b:
if d > a:
return [c, d, a, b, e]
else:
return [c, a, d, b, e]
else:
if d > e:
return [c, a, b, d, e]
else:
return [c, a, b, e, d]
else:
# a > b ; d > c
if a > d:
# a > d > c ; a > b; 15 returns
if e > d:
if e > a:
# e > a > d > c; a > b
if b > c:
if b > d:
return [e, a, b, d, c]
else:
return [e, a, d, b, c]
else:
return [e, a, d, c, b]
else:
# a > e > d > c; a > b
if b > d:
if b > e:
return [a, b, e, d, c]
else:
return [a, e, b, d, c]
else:
if b > c:
return [a, e, d, b, c]
else:
return [a, e, d, c, b]
else:
if e > c:
# a > d > e > c; a > b
if b > e:
if b > d:
return [a, b, d, e, c]
else:
return [a, d, b, e, c]
else:
if b > c:
return [a, d, e, b, c]
else:
return [a, d, e, c, b]
else:
# a > d > c > e ; a > b
if b > c:
if b > d:
return [a, b, d, c, e]
else:
return [a, d, b, c, e]
else:
if b > e:
return [a, d, c, b, e]
else:
return [a, d, c, e, b]
else:
# d > a > b ; d > c; 15 returns
if e > a:
if e > d:
# e > d > a > b; d > c
if c > b:
if c > a:
return [e, d, c, a, b]
else:
return [e, d, a, c, b]
else:
return [e, d, a, b, c]
else:
# d > e > a > b; d > c
if c > a:
if c > e:
return [d, c, e, a, b]
else:
return [d, e, c, a, b]
else:
if c > b:
return [d, e, a, c, b]
else:
return [d, e, a, b, c]
else:
if e > b:
# d > a > e > b; d > c
if c > e:
if c > a:
return [d, c, a, e, b]
else:
return [d, a, c, e, b]
else:
if c > b:
return [d, a, e, c, b]
else:
return [d, a, e, b, c]
else:
# d > a > b > e ; d > c
if c > b:
if c > a:
return [d, c, a, b, e]
else:
return [d, a, c, b, e]
else:
if c > e:
return [d, a, b, c, e]
else:
return [d, a, b, e, c]
else:
# b > a
if c > d:
# b > a ; c > d
if b > c:
# b > c > d ; b > a; 15 returns
if e > c:
if e > b:
# e > b > c > d; b > a
if a > d:
if a > c:
return [e, b, a, c, d]
else:
return [e, b, c, a, d]
else:
return [e, b, c, d, a]
else:
# b > e > c > d; b > a
if a > c:
if a > e:
return [b, a, e, c, d]
else:
return [b, e, a, c, d]
else:
if a > d:
return [b, e, c, a, d]
else:
return [b, e, c, d, a]
else:
if e > d:
# b > c > e > d; b > a
if a > e:
if a > c:
return [b, a, c, e, d]
else:
return [b, c, a, e, d]
else:
if a > d:
return [b, c, e, a, d]
else:
return [b, c, e, d, a]
else:
# b > c > d > e ; b > a
if a > d:
if a > c:
return [b, a, c, d, e]
else:
return [b, c, a, d, e]
else:
if a > e:
return [b, c, d, a, e]
else:
return [b, c, d, e, a]
else:
# c > b > a ; c > d; 15 returns
if e > b:
if e > c:
# e > c > b > a; c > d
if d > a:
if d > b:
return [e, c, d, b, a]
else:
return [e, c, b, d, a]
else:
return [e, c, b, a, d]
else:
# c > e > b > a; c > d
if d > b:
if d > e:
return [c, d, e, b, a]
else:
return [c, e, d, b, a]
else:
if d > a:
return [c, e, b, d, a]
else:
return [c, e, b, a, d]
else:
if e > a:
# c > b > e > a; c > d
if d > e:
if d > b:
return [c, d, b, e, a]
else:
return [c, b, d, e, a]
else:
if d > a:
return [c, b, e, d, a]
else:
return [c, b, e, a, d]
else:
# c > b > a > e ; c > d
if d > a:
if d > b:
return [c, d, b, a, e]
else:
return [c, b, d, a, e]
else:
if d > e:
return [c, b, a, d, e]
else:
return [c, b, a, e, d]
else:
# b > a ; d > c
if b > d:
# b > d > c ; b > a; 15 returns
if e > d:
if e > b:
# e > b > d > c; b > a
if a > c:
if a > d:
return [e, b, a, d, c]
else:
return [e, b, d, a, c]
else:
return [e, b, d, c, a]
else:
# b > e > d > c; b > a
if a > d:
if a > e:
return [b, a, e, d, c]
else:
return [b, e, a, d, c]
else:
if a > c:
return [b, e, d, a, c]
else:
return [b, e, d, c, a]
else:
if e > c:
# b > d > e > c; b > a
if a > e:
if a > d:
return [b, a, d, e, c]
else:
return [b, d, a, e, c]
else:
if a > c:
return [b, d, e, a, c]
else:
return [b, d, e, c, a]
else:
# b > d > c > e ; b > a
if a > c:
if a > d:
return [b, a, d, c, e]
else:
return [b, d, a, c, e]
else:
if a > e:
return [b, d, c, a, e]
else:
return [b, d, c, e, a]
else:
# d > b > a ; d > c; 15 returns
if e > b:
if e > d:
# e > d > b > a; d > c
if c > a:
if c > b:
return [e, d, c, b, a]
else:
return [e, d, b, c, a]
else:
return [e, d, b, a, c]
else:
# d > e > b > a; d > c
if c > b:
if c > e:
return [d, c, e, b, a]
else:
return [d, e, c, b, a]
else:
if c > a:
return [d, e, b, c, a]
else:
return [d, e, b, a, c]
else:
if e > a:
# d > b > e > a; d > c
if c > e:
if c > b:
return [d, c, b, e, a]
else:
return [d, b, c, e, a]
else:
if c > a:
return [d, b, e, c, a]
else:
return [d, b, e, a, c]
else:
# d > b > a > e ; d > c
if c > a:
if c > b:
return [d, c, b, a, e]
else:
return [d, b, c, a, e]
else:
if c > e:
return [d, b, a, c, e]
else:
return [d, b, a, e, c]
此代码基本上构建了一个二叉树，其中特定深度的所有节点都具有 a>b 种关系。现在对于 n 个参数，将有 n*(n-1)/2 个这样的关系，这将是我们树的深度。
现在我们尝试将所有 n! 可能的输出数组推送到这棵树中。请注意，数组可以表示为 n-1 a>b 种关系，例如 'acb' -> a>c,c>b。现在将此类依赖项插入到树中（下面代码中的arr_conds）有点像插入到二叉搜索树中。假设对于深度 3 的所有节点，我们有 c>e。所以要插入 abcde 我们向左，对于 aebdc 我们向右。
此代码已针对最多 7 个元素（~22k 行！！）进行了测试。它到目前为止有效，但这绝对不能替代标准排序算法。更多细节请参考评论。
from itertools import permutations,combinations
import sys
from copy import deepcopy
sys.stdout = open("file.py","w")
N = 7
params = list(chr(97+i) for i in range(N))
permutes = list(permutations(params)) #all possbl outputs of sort function
conds = list(combinations(params,2)) #n*(n-1)/2 such conditions for each depth
conds = {i:conds[i] for i in range(len(conds))} #assign each to a particular depth
class Node:
def __init__(self,depth):
self.d = depth
self.left = None
self.right = None
def insert(self,arr_conds,arr):
if arr_conds==[]: #all n-1 conditions fulfilled, just insert
self.arr = deepcopy(arr);
return
for c in arr_conds: #one of n-1 conditions directly matched,remove it
if set(conds[self.d])==set(c):
arr_conds.remove(c)
src,dst = conds[self.d] #BST like part,recursive insertion
if arr.index(src)<arr.index(dst):
if not self.left: self.left = Node(self.d+1)
self.left.insert(arr_conds,arr)
else:
if not self.right: self.right = Node(self.d+1)
self.right.insert(arr_conds,arr)
def vis(self,sp=""):
if 'arr' in self.__dict__:
s = ','.join(self.arr)
print(sp,"return [",s,"]",sep='')
else:
x,y = conds[self.d]
if self.left:
print(sp,f"if {x}>{y}:",sep='')
self.left.vis(sp+" "*4)
if self.right:
if self.left:
print(sp,"else:",sep='')
else:
print(sp,f"if {y}>{x}:",sep='')
self.right.vis(sp+" "*4)
root = Node(0)
for p in permutes: #for all possbl answers...
arr_conds = [(p[i],p[i+1]) for i in range(N-1)]
root.insert(arr_conds,p) #insert their n-1 conditions into tree
print(f"def sort({','.join(params)}):")
root.vis(" ") #print actual tree...which is our generated code
print("print(sort(33,122,16,2,88,8,9))")
sys.stdout.close()
输出是同一文件夹中的 file.py。
这是另一个程序，但没有经过很好的测试。它产生简单的伪代码。我检查了 N=8，它生成了所有 8 个！可能的结果。
它使用索引 0, 1, 2, ... 而不是 a, b, c, ...。比较 1 和 2 表示比较第 1 项和第 2 项。
Ordering class 跟踪数字之间的关系。如果我们还不知道两个数字中哪个大哪个小，那么这对数字是无序的。比较使这对有序。当没有剩余的无序对时，整个列表完全排序。
代码生成器递归地选择一个随机无序对并首先更新 Ordering 就好像顺序是 a < b 然后好像顺序是相反的 a > b 从而创建两个分支机构（IF 和 ELSE）。
我觉得唯一有点棘手的部分是从 a > b 和 b > c 中推导出 a > c。为简单起见，程序为每个数字维护两组已知为 smaller/larger 的数字。为了简化代码，等号本身也是集合的一部分。
import itertools
class Ordering:
def __init__(self, n):
if isinstance(n, type(self)):
# make a copy
self.unordered = n.unordered.copy()
self.le = {i: le.copy() for i, le in n.le.items()}
self.ge = {i: ge.copy() for i, ge in n.ge.items()}
else:
# initialize for N *distinct* items
self.unordered = set(frozenset(pair) for pair in itertools.combinations(range(n), 2))
self.le = {i: set((i,)) for i in range(n)} # less or equal
self.ge = {i: set((i,)) for i in range(n)} # greater or equal
def a_is_less_than_b(self, a, b):
def discard(x, y):
self.unordered.discard(frozenset((x, y)))
for i in self.le[a]:
for j in self.ge[b]:
self.ge[i].add(j)
discard(i, j)
for i in self.ge[b]:
for j in self.le[a]:
self.le[i].add(j)
discard(i, j)
def final_result(self):
# valid only if self.unordered is empty
return [item[1] for item in sorted((len(le), i) for i, le in self.le.items())]
def codegen(oo, level=0):
def iprint(*args):
print(' ' * (2*level+1), *args) # indented print
if oo.unordered:
x, y = iter(next(iter(oo.unordered))) # random pair from set
copy = Ordering(oo)
iprint("IF [{}] < [{}]:".format(x, y))
oo.a_is_less_than_b(x, y)
codegen(oo, level+1)
iprint("ELSE:" )
copy.a_is_less_than_b(y, x)
codegen(copy, level+1)
else:
iprint("RESULT", oo.final_result());
if __name__ == '__main__':
N=4
codegen(Ordering(N))