According to this article on Wikipedia the theoretical minimum to sort a list on n numbers is : log (n!)
根据*上的这篇文章,对n个数字列表进行排序的理论最小值是:log(n!)
I have managed to write a rather "large" code for sorting upto a 5 element list, The Sorting tree code for sorting an 8 element list will be approximate 60000 lines long and it will not be humanly possible to write.
我已经设法编写了一个相当“大”的代码,用于排序到5个元素的列表。用于排序8个元素列表的排序树代码将是大约60000行,并且人类不可能编写。
Please note a sorting network while easy to implement is neither what i require nor minimalist in comparisons or operations as i am look for a linear sorting approach (without parallelism)
请注意一个分类网络,虽然易于实现既不是我需要的,也不是比较或操作中的极简主义,因为我正在寻找线性排序方法(没有并行性)
I am trying to find a an approach to writing a program to write the program i require. I am partial to the output code being in python.
我试图找到一种编写程序来编写我需要的程序的方法。我偏爱输出代码在python中。
My Roadblock
- I have not even been able to sort even 1 list of 8 in 16 comparisons so i am missing the basic algorithm altogether , so i need some literature pointing to the algorithm. i have seen literature for sorting 6 elements but am unable to expand the logic to 8
- Assuming I am able to work out the algorithm what would be the best way to auto-generate the code for it.
我甚至无法对16个比较中的8个列表进行排序,因此我完全错过了基本算法,所以我需要一些指向算法的文献。我已经看过排序6个元素的文献,但我无法将逻辑扩展到8
假设我能够计算出算法,那么自动生成代码的最佳方法是什么。
EDIT It has come to my attention after grinding and managing to design sorting trees for size 8,9,10. it is a futile exercise . Even when implemented in c or directly in assembly level language as the size of the source code increases exponentially. I created a c dll for sorting tree n = 8 and its size was 10 MB.. for 9 reached 100 MB and for 10 the compiler simply could not create the DLL at least on my system. If I break up the tree into smaller functions the size reduces drastically buy the performance is lost. So there is no point further researching this topic
编辑在研磨和管理设计尺寸为8,9,10的树木后,我注意到了它。这是徒劳的。即使用c或直接用汇编级语言实现,因为源代码的大小呈指数级增长。我创建了一个c dll用于排序树n = 8,其大小为10 MB ..对于9达到100 MB而对于10,编译器根本无法在我的系统上创建DLL。如果我将树分解成较小的功能,则大小会大幅减少购买,性能会丢失。所以没有必要进一步研究这个话题
here is the code for sort5, i would like to get a similar code for sort8
这是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]
2 个解决方案
#1
0
Here is another program, but it is not very well tested. It produces simple pseudocode. I checked that for N=8, it generates all 8! possible outcomes.
这是另一个程序,但它没有经过很好的测试。它产生简单的伪代码。我检查了N = 8,它生成所有8!可能的结果。
Instead of a, b, c, ... it uses indices 0, 1, 2, .... Comparing 1 and 2 means comparing 1st and 2nd item.
而不是a,b,c,......它使用索引0,1,2,....比较1和2意味着比较第1和第2项。
The Ordering class tracks relationships between numbers. A pair of numbers is unordered if we don't know yet which of the two is larger and which is smaller. A comparison makes the pair ordered. The whole list is fully sorted when there are no unordered pairs left.
Ordering类跟踪数字之间的关系。如果我们不知道两者中的哪一个更大而哪个更小,那么一对数字是无序的。比较使这对配对。当没有无序对时,整个列表完全排序。
The code generator recursively selects a random unordered pair and updates the Ordering first as if the order was a < b and then as if the order was the opposite a > b thus creating two branches (IF and ELSE).
代码生成器递归地选择一个随机无序对并首先更新Ordering,好像订单是a b相反,从而创建了两个分支(IF和ELSE)。 然后好像订单是a>
The only part which I find a little bit tricky is to deduce a > c from a > b and b > c. To make it simple, the program maintains for each number two sets of numbers known to be smaller/larger. In order to simplify the code, the equal number itself is part of the set as well.
我发现有点棘手的唯一部分是从a> b和b> c推导出> c。为简单起见,该程序为每个数字维护两组已知较小/较大的数字。为了简化代码,相同数字本身也是集合的一部分。
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))
#2
0
This code basically builds a binary tree, where all nodes of a particular depth have a a>b kind of relationship. Now for n parameters, there will be n*(n-1)/2 such relationships, which will be the depth of our tree.
此代码基本上构建了一个二叉树,其中特定深度的所有节点都具有a> b类型的关系。现在对于n个参数,将存在n *(n-1)/ 2个这样的关系,这将是我们树的深度。
Now we try to push all n! possible output arrays in this tree. Note that an array can be expressed as n-1 a>b kind of relationships e.g 'acb' -> a>c,c>b. Now inserting such dependencies into tree (arr_conds in below code) is kind of like inserting into binary search tree. Say for all nodes at depth 3 we have c>e. So to insert abcde we go left, for aebdc we go right.
现在我们试着推动所有的n!此树中可能的输出数组。注意,数组可以表示为n-1 a> b种关系,例如'acb' - > a> c,c> b。现在将这些依赖项插入到树中(下面的代码中的arr_conds)就像插入二进制搜索树一样。比如深度为3的所有节点,我们有c> e。所以为了插入abcde,我们向左走,为了aebdc我们走对了。
This code has been tested for upto 7 elements (~22k lines!!). It works so far, but this is definitely not an alternative to standard sorting algorithms. Please refer to comments for few more details.
此代码已经过最多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()
Output is a file.py in same folder.
输出是同一文件夹中的file.py.
#1
0
Here is another program, but it is not very well tested. It produces simple pseudocode. I checked that for N=8, it generates all 8! possible outcomes.
这是另一个程序,但它没有经过很好的测试。它产生简单的伪代码。我检查了N = 8,它生成所有8!可能的结果。
Instead of a, b, c, ... it uses indices 0, 1, 2, .... Comparing 1 and 2 means comparing 1st and 2nd item.
而不是a,b,c,......它使用索引0,1,2,....比较1和2意味着比较第1和第2项。
The Ordering class tracks relationships between numbers. A pair of numbers is unordered if we don't know yet which of the two is larger and which is smaller. A comparison makes the pair ordered. The whole list is fully sorted when there are no unordered pairs left.
Ordering类跟踪数字之间的关系。如果我们不知道两者中的哪一个更大而哪个更小,那么一对数字是无序的。比较使这对配对。当没有无序对时,整个列表完全排序。
The code generator recursively selects a random unordered pair and updates the Ordering first as if the order was a < b and then as if the order was the opposite a > b thus creating two branches (IF and ELSE).
代码生成器递归地选择一个随机无序对并首先更新Ordering,好像订单是a b相反,从而创建了两个分支(IF和ELSE)。 然后好像订单是a>
The only part which I find a little bit tricky is to deduce a > c from a > b and b > c. To make it simple, the program maintains for each number two sets of numbers known to be smaller/larger. In order to simplify the code, the equal number itself is part of the set as well.
我发现有点棘手的唯一部分是从a> b和b> c推导出> c。为简单起见,该程序为每个数字维护两组已知较小/较大的数字。为了简化代码,相同数字本身也是集合的一部分。
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))
#2
0
This code basically builds a binary tree, where all nodes of a particular depth have a a>b kind of relationship. Now for n parameters, there will be n*(n-1)/2 such relationships, which will be the depth of our tree.
此代码基本上构建了一个二叉树,其中特定深度的所有节点都具有a> b类型的关系。现在对于n个参数,将存在n *(n-1)/ 2个这样的关系,这将是我们树的深度。
Now we try to push all n! possible output arrays in this tree. Note that an array can be expressed as n-1 a>b kind of relationships e.g 'acb' -> a>c,c>b. Now inserting such dependencies into tree (arr_conds in below code) is kind of like inserting into binary search tree. Say for all nodes at depth 3 we have c>e. So to insert abcde we go left, for aebdc we go right.
现在我们试着推动所有的n!此树中可能的输出数组。注意,数组可以表示为n-1 a> b种关系,例如'acb' - > a> c,c> b。现在将这些依赖项插入到树中(下面的代码中的arr_conds)就像插入二进制搜索树一样。比如深度为3的所有节点,我们有c> e。所以为了插入abcde,我们向左走,为了aebdc我们走对了。
This code has been tested for upto 7 elements (~22k lines!!). It works so far, but this is definitely not an alternative to standard sorting algorithms. Please refer to comments for few more details.
此代码已经过最多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()
Output is a file.py in same folder.
输出是同一文件夹中的file.py.