枚举用于对给定数组进行排序的三重排序操作

Question

我正在尝试解决以下挑战：

给定长度

n

和具有

n

值的数组，枚举使数组排序的“三重”操作。

“三重”操作描述如下：

对于 3 个索引 1≤

i

<

j

<

k

≤

n

，最小值存储在

A[i]

中，中间索引存储在

A[j]

中，最大值存储在

A[k]

中。

您必须打印 Triple 操作的数量以及每个操作的

i

、

j

和

k

。

示例：

输入：

5
5 2 3 1 4  

输出：

2  
1 2 4  
3 4 5

输入：

9  
9 8 7 6 5 4 3 2 1  

输出：

4  
1 5 9  
2 5 8  
3 5 7  
4 5 6

数组变化如下：

⟨9,8,7,6,5,4,3,2,1⟩ → ⟨1,8,7,6,5,4,3,2, 9⟩ → ⟨1,2,7,6,5,4,3,8,9⟩ → ⟨1,2,3,6,5,4,7, 8,9⟩ → ⟨1,2,3,4,5,6,7,8,9⟩

注意，操作次数不必是最小的，这样保证数组可以排序

限制：

• 3≤

  n

  ≤10⁵
• 10^-9≤

  a[i]

  ≤10⁹

我尝试对数组进行排序并通过创建一个返回所需元素索引的反转函数来获取每个索引，但这不起作用，因为数组可以具有重复的元素，例如

A = 3 2 3 1

，其中 3 是重复的。

另一种强力方法是将剩余数组的最小值放在正确的位置，但这使得算法为 O(n²)，这是不合适的。

如何让它也适用于重复值？

Answer 1

首先对列表进行排序似乎是个好主意。您实际上想要拥有的是代表排序顺序的 index 序列。例如，您可以使用 numpy.argsort 来实现。

如果您遵循这些索引引用所代表的“链接”，这将为您提供更多的cycles（循环单链表）。一个想法是采用这样的循环，并使用三重运算将最终值移动到该循环的最左边的索引，并相应地更新循环，以便它会短一个节点。如果您只有上面提到的singly循环链表，那么这种删除不是很有效。最好从每个构建一个双循环链表。

需要考虑一些边界条件：

• 我们到达一个具有自引用的索引（只有一个元素的链表）：这意味着该值已经位于其排序位置并且无需执行任何操作。

• 我们得到的索引是 2 循环的一部分。在这种情况下，我们需要找到第三个值，我们可以用它来执行 Triple 操作，这样就只解决了 2 循环（交换） ，第三个值保持原样。如果某些值已放置在其最终索引处，则可以使用其中之一。如果没有，您可以延迟 2 的这个周期的工作，并稍后在有第二个 2 的周期或已到达其最终目的地的值时解决它。两个 2 的循环可以通过执行两次 Triple 操作来排序。

• 我们得到一个索引，该索引是大小至少为 3 的循环的一部分。这可以被视为一般情况。执行一次 Triple 操作可以将至少一个值放在其最后位置，并缩短剩余的周期。

此算法的 Triple 执行次数将为 O(𝑛)。总体时间复杂度是通过按排序顺序获取值的索引来确定的，并且是 O(𝑛log𝑛)。

下面是一个实现。请注意，它使用基于 0 的索引，因此要将其用于代码挑战（使用基于 1 的索引），您需要在输出结果三元组列表中的每个索引时添加 1。

import numpy as np  # Only used for argsort

# Main algorithm
def get_triples(lst):
    if len(lst) == 2 and lst[0] > lst[1]:  # Boundary case (excluded by the challenge)
        raise ValueError("Cannot sort this list with Triple operations")

    triples = []  # The list op Triple operations to be returned by this function

    # Build doubly circular linked lists, representing the sort order:
    # Get indexes of where values should be taken from to get a sorted result
    takefrom = np.argsort(lst)
    # Opposite: Get indexes of where current values should be moved to, to get a sorted result
    bringto = [0] * len(lst)
    for target, source in enumerate(takefrom):
        bringto[source] = target


    def triple(i, j, k):
        i, j, k = sorted([i, j, k])
        # Collect this operation
        triples.append((i, j, k))
        # Update takenfrom and bringto as a result of this triple operation:  
        bringto[i], bringto[j], bringto[k] = sorted([bringto[i], bringto[j], bringto[k]])
        for m in i, j, k:
            takefrom[bringto[m]] = m


    index_done = -1  # Index which already contains the value it should get in the sorted result 
    cycle_of_2 = None   # Pair of indices which should get their values swapped using a safe third participant
    for a, (b, c) in enumerate(zip(takefrom, bringto)):
        if b != c:  # Are a,b,c in a cycle larger than 2?
            triple(a, b, c)
        elif b < a:  # Is this the second index of a delayed cycle-of-2?
            continue  # Ignore
        elif a == b:  # Is this an index that already has its sorted value? (Not a cycle of 2, but 1)
            pass
        elif cycle_of_2:  # Do we have another cycle of 2 that is pending?
            # Combine and resolve both cycles of 2:
            x, y = cycle_of_2
            triple(x, y, a)  # This puts the final value at index x
            triple(y, a, b)  # This puts the final values at y, a, and b 
            cycle_of_2 = None
        elif index_done == -1:  # Do we lack an index that could serve as dummy participant in triple?
            cycle_of_2 = a, b  # Remember this cycle of 2 for later resolution
            continue  # Do not update index_done
        else: # We can use index_done as dummy participant in a call of triple
            triple(index_done, a, b)
        index_done = a
        if cycle_of_2:
            # We can use index_done as dummy participant in a call of triple
            triple(index_done, *cycle_of_2)
            cycle_of_2 = None

    return triples

上面的函数将返回一个三重操作列表，如果在给定列表上执行，这些操作将对给定列表进行排序。

这里有一个辅助函数来验证情况是否确实如此：

def apply_triples(lst, triples):
    for i, j, k in triples:
        assert i < j < k
        lst[i], lst[j], lst[k] = sorted([lst[i], lst[j], lst[k]])
    assert lst == sorted(lst)

最后是一个在多个列表上进行测试的脚本：

import itertools
import random

# Test on all permuations of a list of size 6
for lst in map(list, itertools.permutations([10, 20, 30, 40, 50, 60])):
    apply_triples(lst, get_triples(lst))

# Test on large random list
lst = list(range(100000))
random.shuffle(lst)
apply_triples(lst, get_triples(lst))

print("test completed")