Подход к автоматической генерации кода для сортировки n элементов

Question

Согласно этой статье в Википедии теоретический минимум для сортировки списка по n цифрам: log (n!)

Мне удалось написать довольно «большой» код для сортировки по списку из 5 элементов. Код дерева сортировки для сортировки по списку из 8 элементов будет иметь длину около 60000 строк, и написать его по-человечески будет невозможно.

Обратите внимание, что сеть сортировки, хотя ее легко реализовать, не является ни тем, что мне нужно, ни минимализмом в сравнениях или операциях, так как я ищу подход линейной сортировки (без параллелизма)

Я пытаюсь найти подход к написанию программы для написания нужной мне программы. Я неравнодушен к выходному коду, находящемуся в python.

Мой контрольно-пропускной пункт

1. Мне даже не удалось отсортировать хотя бы 1 список из 8 в 16 сравнениях, поэтому я упускаю базовый алгоритм в целом, поэтому мне нужна литература, указывающая на алгоритм. я видел литературу по сортировке 6 элементов, но не могу расширить логику до 8
2. Предполагается, что я смогу разработать алгоритм, который будет лучшим способом для автоматической генерации кода для него.

EDIT Это привлекло мое внимание после измельчения и умения проектировать сортировку деревьев по размеру 8,9,10. это бесполезное упражнение. Даже при реализации на языке C или непосредственно на языке ассемблера, поскольку размер исходного кода увеличивается в геометрической прогрессии Я создал cll для дерева сортировки n = 8, и его размер был 10 МБ. Для 9 достиг 100 МБ, а для 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] 

Answer 1

Вот еще одна программа, но она не очень хорошо протестирована. Выдает простой псевдокод. Я проверил, что для N = 8, он генерирует все 8! возможные результаты.

Вместо a, b, c, ... используются индексы 0, 1, 2, .... Сравнение 1 и 2 означает сравнение 1-го и 2-го пунктов.

Класс Ordering отслеживает отношения между числами. Пара чисел неупорядочена, если мы еще не знаем, какое из двух больше, а какое меньше. Сравнение делает пару упорядоченной. Весь список полностью сортируется, когда не осталось неупорядоченных пар.

Генератор кода рекурсивно выбирает случайную неупорядоченную пару и сначала обновляет Ordering, как если бы порядок был a < b, а затем, как если бы порядок был противоположен a > b, создавая две ветви (IF и ELSE).

Единственная часть, которую я нахожу немного хитрой, - это вывести a > c из a > b и b > 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))

Answer 2

Этот код в основном строит двоичное дерево, где все узлы определенной глубины имеют вид 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 элементов (~ 22 тыс. Строк !!). Пока это работает, но это определенно не альтернатива стандартным алгоритмам сортировки. Пожалуйста, обратитесь к комментариям для более подробной информации.

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 в той же папке.