对 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&nbsp; Ry&nbsp; RzX&nbsp; &nbsp;Y&nbsp; &nbsp;Z&nbsp; &nbsp; &nbsp;no swaps neededX&nbsp; &nbsp;Z&nbsp; &nbsp;Y&nbsp; &nbsp; &nbsp;1 swap: YZY&nbsp; &nbsp;X&nbsp; &nbsp;Z&nbsp; &nbsp; &nbsp;1 swap: XYY&nbsp; &nbsp;Z&nbsp; &nbsp;X&nbsp; &nbsp; &nbsp;2 swaps: XZ and XYZ&nbsp; &nbsp;X&nbsp; &nbsp;Y&nbsp; &nbsp; &nbsp;2 swaps: XZ and YZZ&nbsp; &nbsp;Y&nbsp; &nbsp;X&nbsp; &nbsp; &nbsp;1 swap: XZ因此，您所需要的只是再进行 5 次 O(n) 次遍历来修复每个可能的排列。从需要 1 次交换的情况开始。然后修复 2 个交换箱（如果还有）。例如，用于查找和修复 XZY 排列的伪代码是：y = Ry.startz = Rz.startwhile y <= Ry.end && z <= Rz.end&nbsp; &nbsp;if array[y] == 'Z' && array[z] == 'Y'&nbsp; &nbsp; &nbsp; array[y] <--> array[z]&nbsp; &nbsp; &nbsp; swapCount++&nbsp; &nbsp;if array[y] != 'Z'&nbsp; &nbsp; &nbsp; y++&nbsp; &nbsp;if array[z] != 'Y'&nbsp; &nbsp; &nbsp; 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):&nbsp; &nbsp; nx = ny = nz = 0&nbsp; &nbsp; for i in range(len(a)):&nbsp; &nbsp; &nbsp; &nbsp; if a[i] == 'X':&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; nx += 1&nbsp; &nbsp; &nbsp; &nbsp; elif a[i] == 'Y':&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ny += 1&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; nz += 1&nbsp; &nbsp; return ''.join(['X'] * nx + ['Y'] *&nbsp; ny + ['Z'] * nz)print(sortxyz('YXXZXZYYX'))XXXXYYYZZ对于更一般的情况，当列表的元素可以取值时，m复杂度将为 o(m * n)。