对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

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）

Answer 2

首先在阵列中执行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

所以，您只需要再进行五次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 3

这可以使用广度优先搜索解决，例如使用Raymond Hettinger's puzzle solver（页面底部解算器的完整代码）：

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']