对 X、Y 和 Z 字符字符串进行排序的最小交换次数

Question

我需要找到以随机顺序和数量（不仅仅是相邻）对仅包含字母 X、Y 和 Z 的字符串进行排序所需的最小交换量。任意两个字符都可以交换。例如，字符串 ZYXZYX 将按 3 次交换排序：ZYXZYX -> XYXZYZ -> XXYZYZ -> XXYYZZ ZZXXYY - 4 次交换，XXXX - 0 次交换。到目前为止，我已经有了这个解决方案，但是排序并没有以最佳方式对字符进行排序，因此结果并不总是最小的交换量。此外，解决方案应该是 O(nlogn)。def solve(s):  n = len(s)  newS = [*enumerate(s)]   sortedS = sorted(newS, key = lambda item:item[1])  counter = 0  vis = {v:False for v in range(n)}   print(newS)  print(sortedS)  for i in range(n):    if vis[i] or sortedS[i][0] == i:       continue    cycle_size = 0    j = i     while not vis[j]:       vis[j] = True       j = sortedS[j][0]       cycle_size += 1        if cycle_size > 0:       counter += (cycle_size - 1)   return counter

Answer 1

首先对数组执行一次 O(n) 遍历并计算 X、Y 和 Z。根据计数，我们可以在数组中定义三个区域：Rx、Ry 和 Rz。Rx 表示数组中 X 应该所在的索引范围。Ry 和 Rz 也是如此。

那么就需要考虑 6 种排列：

Rx  Ry  Rz

X   Y   Z     no swaps needed

X   Z   Y     1 swap: YZ

Y   X   Z     1 swap: XY

Y   Z   X     2 swaps: XZ and XY

Z   X   Y     2 swaps: XZ and YZ

Z   Y   X     1 swap: XZ

因此，您所需要的只是再进行 5 次 O(n) 次遍历来修复每个可能的排列。从需要 1 次交换的情况开始。然后修复 2 个交换箱（如果还有）。

例如，用于查找和修复 XZY 排列的伪代码是：

y = Ry.start

z = Rz.start

while y <= Ry.end && z <= Rz.end

   if array[y] == 'Z' && array[z] == 'Y'

      array[y] <--> array[z]

      swapCount++

   if array[y] != 'Z'

      y++

   if array[z] != 'Y'

      z++

每个排列的运行时间为 O(n)，总运行时间为 O(n)。

正确性的正式证明留给读者作为练习。我只会注意到情况 XZY、YXZ 和 ZYX 以一次交换的成本修复两个元素（效率 2），而情况 YZX 和 ZXY 以两次交换的成本修复三个元素（效率 1.5）。因此，首先找到并修复有效的情况（并且仅根据需要执行低效的情况）应该给出最佳答案。

Answer 2

这可以使用广度优先搜索来解决，例如使用Raymond Hettinger 的谜题求解器（求解器的完整代码位于页面底部）：

class SwapXYZ(Puzzle):    

    def __init__(self, pos):

        self.pos = [x for x in pos]

        self.goal = sorted(pos)

    

    def __repr__(self):

        return repr(''.join(self.pos))

    

    def isgoal(self):

        return self.pos == self.goal

    

    def __iter__(self):

        for i in range(len(self.pos)):

            for j in range(i+1, len(self.pos)):

                move = self.pos[:]

                temp = move[i]

                move[i] = move[j]

                move[j] = temp

                yield SwapXYZ(''.join(move))

SwapXYZ("ZYXZYX").solve()

# ['ZYXZYX', 'XYXZYZ', 'XXYZYZ', 'XXYYZZ']

Answer 3

IMVHO 用于排序此类字符串的交换次数为零。我们得到 X、Y 和 Z (nx, ny, nz) 的计数。然后我们用 X 填充前 nx 个元素，用“Y”填充接下来的 ny 元素，用“Z”填充其余的元素。复杂度为 o(n)

def sortxyz(a):

    nx = ny = nz = 0

    for i in range(len(a)):

        if a[i] == 'X':

            nx += 1

        elif a[i] == 'Y':

            ny += 1

        else:

            nz += 1

    return ''.join(['X'] * nx + ['Y'] *  ny + ['Z'] * nz)

print(sortxyz('YXXZXZYYX'))

XXXXYYYZZ

对于更一般的情况，当列表的元素可以取值时，m复杂度将为 o(m * n)。