如何用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且快速的。我不要求完整的解决方案，只要求一些线索。我愿意自己解决。

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

Answer 3

def s_sort(n):
    new_lst = []
    while len(n) > 0:
        new_lst.append(min(n))
        n.remove(min(n))
        if len(n) > 0:
            new_lst.append(max(n))
            n.remove(max(n))
    return new_lst

n = eval(input())
print(s_sort(n))