algorithm - 给定一个随机顺序的整数数组，您必须找到最小交换次数才能将其转换为循环排序数组

Question

如果数组以随机顺序给出，则必须输出转换为循环排序数组所需的最小交换次数。

例如，给定的数组是 3 5 4 2 1

所以第一次交换将是 5<-->4 结果：3 4 5 2 1 第二次交换将是 2<-->1 结果：3 4 5 1 2（最终）

输出：2

我无法理解这个问题背后的逻辑。

添加更多： 只能在相邻元素之间交换，数字在 1 到 N 之间

Answer 1

好吧，不知道它是否是可用的最佳算法，但我可以想到一个 O(n^2) 解决方案：

首先，忽略循环数组的可能性。让我们解决一个更简单的问题：对数组进行排序的最小交换次数是多少。

在这里要小心，因为这与排序算法无关。基于比较的排序算法的最坏情况至少为O(n log n). 在这个问题中，您需要的最大交换次数是n.

为什么？因为它是您可以实现的最大排列循环大小。您需要的最小交换次数恰好是排列周期大小减一。我的意思是您可以将数组的任何排列表示为排列循环，例如：

3 2 1 4 5->(2)(4)(5)(1 3)

对于大小为 1 的排列循环，您不需要任何交换。对于大小为 2 的置换循环，您恰好需要 1 个交换。这缩放为：

2 3 4 5 1->(1 2 3 4 5)

忽略这个数组已经是循环排序的，这个数组完全乱了。要正常排序，我需要 4 次交换，基本上将 1 移动到正常位置。

计算排列周期非常简单，只需将数字跟踪到数组排序后的位置即可。使用前面的示例

3 2 1 4 5

• 开始于A[0];
• 因为A[0]==3, 和 3 将是排序数组中的第三个元素，所以跟随到第三个位置；

• 因为A[2]==1, 和 1 将是...，因此排在第 1 位。因为我们已经在这里了，所以我们有一个大小为 2 的循环；

• 在下一个未访问的位置重新开始 (1)

• A[1]==2处于正确的位置，所以我们不需要做任何事情，这里我们有一个大小为 1 的循环。

• 等等……

这个算法是 O(n)，但是由于我们需要对从每个可能位置开始的数组执行此操作（因为它是圆形的），所以我们会执行 n 次，所以整个算法是 O(n^2)。

更新; 一些python代码来显示我的算法：

def offset_swaps(A, S, offset):
    visited = [False]*len(A)
    swaps = 0

    for i in xrange(len(A)):
        if visited[i]: continue

        cycle, current = 0, i
        while not visited[current]:
            cycle += 1
            visited[current] = True
            current = (S[A[current]] + offset) % len(A)

        swaps += cycle - 1

    return swaps       

def number_of_swaps(A):
    S = {x:i for i,x in enumerate(sorted(A))}
    min_swaps = len(A)
    for i in xrange(len(A)):
        min_swaps = min(min_swaps, offset_swaps(A, S, i))
    return min_swaps

print number_of_swaps((3, 5, 4, 2, 1))

Answer 2

我认为这里的方法应该是 - 将所有数字排序到一个辅助数组中。然后对于每个循环移位计算使原始数组到该循环移位所需的交换次数。选择其中最小的。

要找到使数组 A 到数组 B 所需的最小交换次数，只需计算交换值的数量（即值 a 在 A 中值 b 的左侧，但在数组 B 中反之亦然）。这个问题等同于计算给定数组中的倒数，并且可以使用修改后的归并排序再次解决O(n*log(n))。

我的方法的复杂性是O(n^2*log(n))（因为您对大小为 n 的数组的所有循环移位进行合并排序）。

我想不出更快的解决方案来解决您的问题。

Answer 3

假设：

1. 数组元素是整数 1 到 N。

脚步：

1. 分配长度为 N 的第二个（直方图）数组 H。
2. 在通过初始数组 A 的单次传递中，对于每个索引 i 递增 H[ (A[i] - i) % N]
3. 在单次通过 H 中，识别 H 中具有最大计数的元素 R
4. 清除 H。
5. 确定原始阵列中在 R 旋转下的轨道数。（通过 H 向前步进直到 H[i]=0，然后在旋转 R 下步进 A[i] 是其成员的轨道）设置 H [i]=1 对于轨道的每个成员，并重复直到元素 H[N-1] 已被处理（计算轨道的数量）。这也是 O(N)，因为 A 的每个元素只被访问一次。
6. 所需的交换次数 = N - 轨道。

这是 O(N)。

更新：我已经更新了算法以考虑多个轨道。在处理每个轨道时，最终交换会放置两个元素，而不仅仅是 1。

我怀疑轨道的数量在任何旋转下都是不变的，这将大大简化算法但不会影响它的复杂性，它保持在 O(N)。

Answer 4

def number_of_swaps(A):
    l=len(A)
    if l < 2:
        return 0
    S1={x:i for i,x in enumerate(A)}
    pos_of_0=S1[0]
    pos_of_N=S1[l-1]
    if pos_of_0 > 0:
        if pos_of_N != (l-1):
            if pos_of_N < pos_of_0:
                n=(pos_of_0+(l-1)-pos_of_N-1)
            else:
                    n=(pos_of_0+(l-1)-pos_of_N)
        else:
            n=(pos_of_0)
    else :
        n=(l-pos_of_N-1)
    A.remove(0)
    A.remove(l-1)
    B=[x-1 for x in A ]
    return n+number_of_swaps(B)

def min_number_of_swaps(A):
    B=sorted(A)
    swaps=[]
    for i in range(len(A)):
        if i == 0:
            C=B
        else:
            C=B[-i:]+B[0:len(A)-i]

        S = {x:i for i,x in enumerate(C)}
        D=[S[i] for i in A]
        swaps.append(number_of_swaps(D))
    return min(swaps)

打印 min_number_of_swaps([8,5,7,1,2,4,3,6])

7

上面的代码是解决问题复杂度 O(N^3) 的递归方法

代码已被编辑为仅打印最小交换次数。