python - 自动生成对 n 个元素进行排序的代码的方法
问题描述
根据Wikipedia上的这篇文章，对n个数字的列表进行排序的理论最小值是：log (n!)
我已经设法编写了一个相当“大”的代码，用于对 5 个元素列表进行排序，用于对 8 个元素列表进行排序的排序树代码大约有 60000 行长，而且人类无法编写。
请注意，排序网络虽然易于实现，但在比较或操作中既不是我需要的，也不是极简主义，因为我正在寻找一种线性排序方法（没有并行性）
我正在尝试找到一种方法来编写程序来编写我需要的程序。我偏爱python中的输出代码。
我的路障
- 我什至无法对 16 个比较中的 8 个列表进行排序，所以我完全错过了基本算法，所以我需要一些指向该算法的文献。我看过对 6 个元素进行排序的文献，但无法将逻辑扩展到 8 个
- 假设我能够制定出算法，那么自动生成代码的最佳方法是什么。
编辑 在研磨并设法设计尺寸为 8、9、10 的分类树之后，我注意到了它。这是徒劳的。即使用 c 或直接用汇编语言实现，源代码的大小也会成倍增加。我创建了用于排序树 n = 8 的 ac 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在同一个文件夹中。
推荐阅读
- pyspark - 我通过使用它的 pyspark.ml.regression.LinearRegression 在 spark 中创建一个模型
- java - Reactor Mono 发布到多种方法
- mongodb - 无法从 Docker 容器中的 Spring Boot App Deploy 访问现有的 MongoDb
- ruby-on-rails - 在 ruby on rails 上得到 Elasticsearch::Transport::Transport::Errors::BadRequest 而 create_index 和 import
- eclipse - STM32 Eclipse (CubeIDE) 调试项目不在 main.c 中启动，而是在 UcHeap 汇编代码中启动
- corda - corda - 运行 clean deployNode 时出错 - 节点启动期间出现异常：找不到节点合法身份的私钥
- php - 配置 HTML Purifier 以允许使用 file:// 协议的 href
- flutter - 如何在小部件 Flutter 上粘贴数据
- python-3.x - 为什么 Selenium 给我 NoSuchElementException 错误
- postgresql - 使用 postgres pg_dump 命令时出现此错误消息的原因是什么？