冒泡排序无限循环错误的变化

Question

在一个特定的棋盘游戏中，只有一行，它包含 N space 个，从左到右编号为 0 到 N - 1。还有 N 个弹珠，编号为 0 到 N - 1，最初以某种任意顺序放置。在那之后，有两个动作可以一次只能做一个：

切换：切换位置 0 和 1 的弹珠。
旋转：移动位置 0 的弹珠移动到位置 N - 1，并移动所有其他弹珠向左一 space（下一个索引）。

objective就是把弹珠按顺序排列，每个弹珠i在第i个位置。

我编写的代码适用于发布在问题 (1 3 0 2) 上的示例，但是当我将额外的数字 4 随机添加到列表时，while 循环永远不会终止。看排好序的序列，好像是重复遍历了多个相同的序列。我不确定为什么它适用于一个系列而不适用于下一个系列。

奖金，我似乎无法弄清楚如何将输出打印为由 space 分隔的数字，而不是用方括号和逗号分隔的列表。该问题要求我们将输出打印为由 space 分隔的数字。对此的任何帮助将不胜感激。

class MarblesBoard:
    """creates a marble board with number marbles in specific spots"""
    def __init__(self, marble_sequence):
        self.board = [x for x in marble_sequence]

    def __str__(self):
        return str(self.board)

    def __repr__(self):
        return "%r " % (self.board)

    def switch(self):
        """switch the marbles in position 0 and 1"""
        self.board[0], self.board[1] = self.board[1], self.board[0]
        return self.board

    def rotate(self):
        """Move the marble in position 0 to position N - 1, and move all other marbles one space to the left (one index lower)"""
        copy_board = self.board.copy()
        copy_board[len(self.board)-1] = self.board[0]
        for x in range(1, len(self.board)):
            copy_board[x - 1] = self.board[x]
        self.board = copy_board
        return self.board

    def is_sorted(self):
        return self.board == sorted(self.board):

class Solver:
    """solves the marble sorting game when given a marble board as input"""

    def __init__(self, MarblesBoard):
        self.steps = 0
        self.board = MarblesBoard.board
        return

    def solve(self):
        n = len(self.board)
        # print("n = ", n)
        print(self.board)
        while MarblesBoard.is_sorted(self) == False:
            if self.board[0] > self.board[1]:
                MarblesBoard.rotate(self)
                print(self.board)
                self.steps += 1
            else:
                MarblesBoard.switch(self)
                print(self.board)
                self.steps += 1
        print("total steps: ", self.steps)

关于输出，代码在此处的示例输出中运行良好：

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

[1, 3, 0, 2]
[3, 1, 0, 2]
[1, 0, 2, 3]
[0, 2, 3, 1]
[2, 0, 3, 1]
[0, 3, 1, 2]
[3, 0, 1, 2]
[0, 1, 2, 3]
total steps:  7

但是，如果我在起跑板上加一个 4：

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

[1, 3, 0, 2, 4]
[3, 1, 0, 2, 4]
[1, 0, 2, 4, 3]
[0, 2, 4, 3, 1]
[2, 0, 4, 3, 1]
[0, 4, 3, 1, 2]
[4, 0, 3, 1, 2]
[0, 3, 1, 2, 4]
[3, 0, 1, 2, 4]
[0, 1, 2, 4, 3]
[1, 0, 2, 4, 3]
[0, 2, 4, 3, 1]
[2, 0, 4, 3, 1]
[0, 4, 3, 1, 2]
[4, 0, 3, 1, 2]
[0, 3, 1, 2, 4]
[3, 0, 1, 2, 4]

请注意，3 0 1 2 4 重复作为第二次迭代和最后列出的迭代。由于while循环的结构，由于出现相同的顺序，执行相同的步骤，无限循环。

Answer 1

那么，它究竟是冒泡排序的变体吗？大多数排序都有一种方法可以将已排序和未排序的数据保存在不同的区域中，以便清楚地知道已经排序的内容。这种好像不行。

看起来切换发生的唯一标准是 board[0] > board[1]。真的只有这些吗？

我对代码的建议如下：

class MarblesBoard:

    def __init__(self, marble_sequence):
        self.board = [x for x in marble_sequence]

是不是有点多余？为什么不呢：

class MarblesBoard:

    def __init__(self, marble_sequence):
        self.board = marble_sequence

I can't seem to figure out how to print the output as numbers separated by a space

这让我了解了您对 __str__ 的实施：

def __str__(self):
        return str(self.board)

那不行。看看当我尝试在 shell:

中执行类似操作时返回的字符串

>>> str([1, 2, 3])
'[1, 2, 3]'
>>>

你最好使用 str.join:

def __str__(self):
    return " ".join(map(str, self.board))

您的 switch 方法看起来不错，除了您不需要 return 任何东西。只需交换元素即可。

如果我对rotate方法的理解正确，可以简化为：

def rotate(self):
    self.board.append(self.board.pop(0))

同样，您不需要 return 此函数的任何内容。

你的is_sorted也可以简化：

def is_sorted(self):
    return self.board == sorted(self.board)

我可能还会在你的 MarblesBoard class 中添加一个名为 should_rotate 的方法，这取决于 returns True 或 False关于求解器是否应该旋转或切换。稍后将由求解器使用：

def should_rotate(self):
    return self.board[0] > self.board[1]

接下来，Solverclass。首先是 __init__ 方法：

通过将参数命名为 MarblesBoard（与 class 同名），您隐藏了 class 的标识符 - 所以我不会调用参数.我认为 marbles_board 是一个更好的名字。

其次，我没有看到在 __init__ 中明确使 steps 成为实例变量的充分理由，因为您唯一使用它的地方是 solve ] 方法。我现在就摆脱它。

第三，我认为将self.board绑定到MarblesBoard实例的board对象不是一个好主意。如果你的 Solver class 基本上只是围绕着一个 MarblesBoard.board，你甚至还不如不做这个 class 而只是在 MarblesBoard class。同样，您不需要从 __init__.

中明确 return

class Solver:

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

solve也可以稍微简化一下：

def solve(self):

    number_of_steps = 0

    while not self.marbles_board.is_sorted():
        if self.marbles_board.should_rotate():
            self.marbles_board.rotate()
        else:
            self.marbles_board.switch()
        number_of_steps += 1
    print(f"Number of steps: {number_of_steps}")

有趣的是，您对 solve 的实现效果和它一样好，因为您是如何传入 self（Solver 对象）作为参数的rotate 和 switch 方法。

冒泡排序无限循环错误的变化

Variation on Bubble Sort infinite loop error

python

bubble-sort

while-loop