Python弹珠排序游戏：部分用例正常，部分陷入循环的排查与优化

问题背景 #

我用Python写了一款弹珠排序游戏，部分用例能正常运行，但处理较长数字元组时会陷入循环。目前仅通过比较前两个数字决定执行switch（交换首两位）或rotate（首位移至末尾、其余左移）操作，加过随机性但效果不好。需求如下：

1. 现有代码存在什么问题？MarblesBoard与Solver类的结构是否合理？
2. 在保证功能正常（暂不考虑时间优化）的前提下，探索选择switch或rotate操作的更优方案。

现有代码实现 #

MarblesBoard类 #

class MarblesBoard:
    """创建一个带有特定位置数字弹珠的弹珠板"""
    def __init__(self, marble_sequence):
        self.board = [x for x in marble_sequence]

    def switch(self):
        """交换位置0和1的弹珠"""
        self.board[0], self.board[1] = self.board[1], self.board[0]
        return self.board

    def rotate(self):
         """
         将位置0的元素移到位置N-1，其余元素左移一位
         """
        self.board = self.board[1:] + [self.board[0]]
        return self.board
    
    def is_sorted(self):
        return self.board == sorted(self.board)
    
    def should_rotate(self):
        # 用于判断执行rotate还是switch的条件
        return self.board[0] > self.board[1]

Solver类 #

class Solver:
    """输入弹珠板实例，解决弹珠排序问题"""

    def __init__(self, marbles_board):
        self.marbles_board = marbles_board

    def solve(self):
        steps = 0

        while not self.marbles_board.is_sorted():
            if steps == 10:break
            if self.marbles_board.should_rotate():
                self.marbles_board.rotate()
            else:
                self.marbles_board.switch()
            
            steps += 1
        
        print(f"步数: {steps}")
        print(self.marbles_board)

测试用例 #

• 测试用例1（运行正常）：

board1 = MarblesBoard((1,3,0,2))
solver1 = Solver(board1)
solver1.solve()

• 测试用例2（运行失败）：

board2 = MarblesBoard((1,3,0,2,4))
solver2 = Solver(board2)
solver2.solve()

一、现有代码问题与类结构分析 #

代码核心问题 #

1. 决策逻辑过于简单，易陷入循环：仅靠前两个元素的大小判断操作，完全忽略全局序列状态。比如测试用例2(1,3,0,2,4)，执行几次操作后会进入(3,1,0,2,4)→(1,0,2,4,3)→(0,2,4,3,1)的循环，永远无法推进到有序状态。
2. 硬编码步数限制不合理：固定steps==10就终止，对于需要更多步数的序列直接放弃排序，属于偷懒式的错误处理。

类结构合理性 #

MarblesBoard和Solver的职责划分是合理的：

• MarblesBoard专注维护弹珠序列状态、提供操作接口和状态判断，符合单一职责原则；
• Solver负责调用板的方法实现排序逻辑，职责明确。
  可优化细节：switch和rotate返回self.board意义不大，调用者可直接访问实例属性；should_rotate的判断逻辑可以设计得更灵活，比如支持传入自定义规则。

二、更优操作选择方案 #

方案1：贪心策略（基于逆序数） #

每次选择能减少全局逆序数的操作，逆序数越小，序列越接近有序。同时记录已出现的状态，避免循环：

def count_inversions(arr):
    """计算序列的逆序数"""
    count = 0
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] > arr[j]:
                count += 1
    return count

class Solver:
    def __init__(self, marbles_board):
        self.marbles_board = marbles_board
        self.history = set()  # 记录已出现的状态，防止循环

    def solve(self):
        steps = 0
        current_state = tuple(self.marbles_board.board)
        
        while not self.marbles_board.is_sorted():
            if current_state in self.history:
                # 检测到循环，随机选一个操作打破僵局
                import random
                self.marbles_board.switch() if random.random() > 0.5 else self.marbles_board.rotate()
            else:
                self.history.add(current_state)
                # 模拟两种操作后的状态，计算逆序数
                switch_temp = self.marbles_board.board.copy()
                switch_temp[0], switch_temp[1] = switch_temp[1], switch_temp[0]
                switch_inv = count_inversions(switch_temp)

                rotate_temp = self.marbles_board.board[1:] + [self.marbles_board.board[0]]
                rotate_inv = count_inversions(rotate_temp)

                # 选逆序数更小的操作
                if switch_inv <= rotate_inv:
                    self.marbles_board.switch()
                else:
                    self.marbles_board.rotate()
            
            current_state = tuple(self.marbles_board.board)
            steps += 1
        
        print(f"步数: {steps}")
        print(self.marbles_board.board)

方案2：广度优先搜索（BFS）找最短路径 #

不考虑时间成本的情况下，BFS能遍历所有可能的状态，找到第一次到达有序状态的最短操作路径，完全避免循环：

from collections import deque

class Solver:
    def __init__(self, marbles_board):
        self.initial_state = tuple(marbles_board.board)
        self.target_state = tuple(sorted(self.initial_state))

    def solve(self):
        queue = deque()
        queue.append((self.initial_state, []))  # (当前状态, 操作路径)
        visited = set()
        visited.add(self.initial_state)

        while queue:
            current_state, path = queue.popleft()
            if current_state == self.target_state:
                print(f"步数: {len(path)}")
                print("操作路径:", path)
                print("最终序列:", current_state)
                return
            
            # 生成switch后的状态
            switch_state = list(current_state)
            switch_state[0], switch_state[1] = switch_state[1], switch_state[0]
            switch_state = tuple(switch_state)
            if switch_state not in visited:
                visited.add(switch_state)
                queue.append((switch_state, path + ["switch"]))
            
            # 生成rotate后的状态
            rotate_state = current_state[1:] + (current_state[0],)
            if rotate_state not in visited:
                visited.add(rotate_state)
                queue.append((rotate_state, path + ["rotate"]))
        
        print("无法找到排序路径")

方案3：冒泡排序启发策略 #

参考冒泡排序的核心思想，把较大的元素逐步往后“推”：

• 如果首元素大于第二个元素，执行rotate让首元素移到后面，直到它遇到比自己大的元素；
• 如果首元素小于第二个元素，检查首元素是否是当前未排序部分的最小值，若是则rotate让它暂时移到末尾（等待前面的元素排好后再归位），否则执行switch调整前两位顺序。

内容的提问来源于stack exchange，提问作者gaurav8936