如何用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. 这样的分类总会有结果的。在

例如：

^{pr2}$

因为

(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的乘积生成的数学对象。我们对一个发电机组有很好的描述（相当于问题中的有序列表），但是当交换两个发电机时，我们需要考虑这两个元素的交换子（这是问题中元素的总和）。我还没有给这个问题一个解决方案，因为它将接近你能想到的最坏的一个。我想知道你将如何以一个好的方式来实现这一点，以便它是Python式的和快速的。我不是要一个完整的解决方案，只是一些线索。我愿意自己解决。在

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