如何在Python中编写这种“奇怪的”排序

Question

我想编写一个能够高效执行这种“奇怪”排序的函数（我对这个伪代码感到抱歉，在我看来，这是引入问题的最明显的方式） ：

l=[[A,B,C,...]] 
while some list in l is not sorted (increasingly) do 
    find a non-sorted list (say A) in l 
    find the first two non-sorted elements of A (i.e. A=[...,b,a,...] with b>a) 
    l=[[...,a,b,...],[...,b+a,...],B,C,...] 

两个重要的事情应该提到：

1. 排序是依赖于前两个 未分选元素的选择：if A=[...,b,a,r,...], r<a<b，我们选择 排序WRT到(a,r)则最终结果将不会一样。这是 为什么我们修复了A的两个第一个非排序元素。
2. 排序这种方式总是会结束。

一个例子：

In: Sort([[4,5,3,10]]) 
Out: [[3,4,5,10],[5,7,10],[10,12],[22],[4,8,10]] 

因为

(a,b)=(5,3): [4,5,3,10]->[[4,3,5,10],[4,8,10]] 
(a,b)=(4,3): [[4,3,5,10],[4,8,10]]->[[3,4,5,10],[7,5,10],[4,8,10]] 
(a,b)=(7,5): [[3,4,5,10],[7,5,10],[4,8,10]]->[[3,4,5,10],[5,7,10],[12,10],[4,8,10]] 
(a,b)=(12,10): [[3,4,5,10],[5,7,10],[12,10],[4,8,10]]->[[3,4,5,10],[5,7,10],[10,12],[22],[4,8,10]] 

谢谢您的帮助！

编辑

为什么我会考虑这个问题： 我试图做一些计算与李代数的普遍包络代数。这是由某些生成器x_1，... x_n的乘积生成的数学对象。我们对一个生成集（它等于问题中的有序列表）有一个很好的描述，但是当交换两个生成器时，我们需要考虑这两个元素的换向器（这是问题中元素的总和） ）。我没有解决这个问题，因为它接近你能想到的最糟糕的一个。我想知道你会如何以一种好的方式来实现这个目标，所以它是pythonic和fast。我不是要求一个完整的解决方案，只有一些线索。我愿意自己解决。

Answer 1

下面是一个简单的实现，可以使用一些改进：

def strange_sort(lists_to_sort): 
    # reverse so pop and append can be used 
    lists_to_sort = lists_to_sort[::-1] 
    sorted_list_of_lists = [] 
    while lists_to_sort: 
     l = lists_to_sort.pop() 
     i = 0 
     # l[:i] is sorted 
     while i < len(l) - 1: 
      if l[i] > l[i + 1]: 
       # add list with element sum to stack 
       lists_to_sort.append(l[:i] + [l[i] + l[i + 1]] + l[i + 2:]) 
       # reverse elements 
       l[i], l[i + 1] = l[i + 1], l[i] 
       # go back if necessary 
       if i > 0 and l[i - 1] > l [i]: 
        i -= 1 
        continue 
      # move on to next index 
      i += 1 
     # done sorting list 
     sorted_list_of_lists.append(l) 
    return sorted_list_of_lists 

print(strange_sort([[4,5,3,10]])) 

此跟踪哪些列表是通过留下使用堆栈进行排序。时间复杂度非常好，但我不认为它是理想的

Answer 2

首先，你将不得不实现一个while循环，它将检查列表中的所有数字是否被排序。我将使用all来检查序列中的所有对象是否为True。

def a_sorting_function_of_some_sort(list_to_sort): 
    while not all([all([number <= numbers_list[numbers_list.index(number) + 1] for number in numbers_list 
         if not number == numbers_list[-1]]) 
        for numbers_list in list_to_sort]): 

     for numbers_list in list_to_sort: 

      # There's nothing to do if the list contains just one number 
      if len(numbers_list) > 1: 
       for number in numbers_list: 
        number_index = numbers_list.index(number) 
        try: 
         next_number_index = number_index + 1 
         next_number = numbers_list[next_number_index] 
        # If IndexError is raised here, it means we don't have any other numbers to check against, 
        # so we break this numbers iteration to go to the next list iteration 
        except IndexError: 
         break 
        if not number < next_number: 
         numbers_list_index = list_to_sort.index(numbers_list) 
         list_to_sort.insert(numbers_list_index + 1, [*numbers_list[:number_index], number + next_number, 
                    *numbers_list[next_number_index + 1:]]) 
         numbers_list[number_index] = next_number 
         numbers_list[next_number_index] = number 
         # We also need to break after parsing unsorted numbers 
         break 
    return list_to_sort