Approach to automatically generate code for sorting n elements

Question

According to this article on Wikipedia the theoretical minimum to sort a list on n numbers is : 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.

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.

My Roadblock

1. 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
2. Assuming I am able to work out the algorithm what would be the best way to auto-generate the code for it.

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

here is the code for sort5, i would like to get a similar code for 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] 

Answer 1

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.

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.

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.

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.

Answer 2

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.

Instead of a, b, c, ... it uses indices 0, 1, 2, .... Comparing 1 and 2 means comparing 1st and 2nd item.

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.

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).

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.

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))