首先：）
开关：将大理石切换在位置0和1。
旋转：将大理石在位置0移动到位置n -1，然后将所有其他大理石移动到左侧的所有大理石（一个索引）。
如果有数字列表（1,3,0,2）开关 - 旋转 - 开关将排序数字3,1,0,2-1,0,2,3-0,1,2,3
但是，如果我们有（3,1,0,2），它永远不会以开关 - 旋转 - 开关 - 旋转...方法。
是否有更好的方法可以同时使用开关和旋转以有效地获得排序的结果？
我现在无法想到最有效的方法（意味着使用最小数量的旋转和开关的方式）来对任何给定的列表进行排序。但是我可以想到一种方法，以找到最有效的方法。
将您的问题视为图数据结构中的广度优先搜索问题。如果可以通过单个交换或单个旋转从当前列表中获得直接指向另一个列表的列表。进行广度优先搜索，直到获得排序的列表为止。然后，从原始列表到排序列表的路径是"最有效的方式"。您实际上不需要设置图形数据结构 - 这只是给出算法的想法。
我会尽快在这里获取一些特定的代码，但这是一个轮廓。从仅包含原始列表的字典开始（该列表需要是元组，因此我将开始将它们称为元组），将其称为键，而None作为值。该词典包含"已经看到的元组"作为钥匙，对于每个钥匙，值是导致该钥匙的元组。还要从仅包含原始元组的队列（可能是Python的deque）开始。这是"看到但尚未处理"的队列。然后运行一个循环：从队列上弹出元组，检查是否是排序的元组，然后，对于每个元组，可以通过单个开关或旋转检查是否已经看到，如果已经看到它，请将其添加到字典和队列中。最终，您将到达排序的元组（如果正确定义了原始元组）。使用"已经看到的"字典将路径从排序的元组打印回原始元组。
这是基于该算法的代码。可以进行进一步的优化，例如在第一次看到switched_or_rotated例行程序或检查目标元组时，而不是在处理何时进行处理时检查。
from collections import deque
# Constant strings: ensure they are the same length for pretty printing
START = 'Start: '
SWITCH = 'Switch:'
ROTATE = 'Rotate:'
def switched_or_rotated(atuple):
"""Generate the tuples reachable from the given tuple by one switch
or rotation, with the action that created each tuple.
"""
yield (atuple[1::-1] + atuple[2:], SWITCH) # swap first two items
yield (atuple[1:] + atuple[:1], ROTATE) # rotate first item to the end
def sort_by_switch_and_rotate(iter):
"""Sort a finite, sortable iterable by repeatedly switching the
first two items and/or rotating it left (position 0 to the end, all
others to one index lower). Print a way to do this with the
smallest number of switches and/or rotations then return the number
of steps needed.
Based on <https://stackoverflow.com/questions/54840758/
sorting-numbers-with-mix-of-switch-and-rotate-in-python>
"""
# Initialize variables
original = tuple(iter)
targettuple = tuple(sorted(original))
alreadyseen = {original: None} # tuples already seen w/ previous tuple
actions = {original: START} # actions that got each tuple
notprocessed = deque() # tuples seen but not yet processed
# Do a breadth-first search for the target tuple
thistuple = original
while thistuple!= targettuple:
for nexttuple, nextaction in switched_or_rotated(thistuple):
if nexttuple not in alreadyseen:
alreadyseen[nexttuple] = thistuple
actions[nexttuple] = nextaction
notprocessed.append(nexttuple)
thistuple = notprocessed.popleft()
# Print the path from the original to the target
path = []
while thistuple:
path.append(thistuple)
thistuple = alreadyseen[thistuple]
print('nHow to sort a list in {} steps:'.format(len(path)-1))
for thistuple in reversed(path):
print(actions[thistuple], thistuple)
# Return the minimal number of steps
return len(path) - 1
这是您的两个示例的测试代码和一些其他示例。
# Example tuples from the questioner
assert sort_by_switch_and_rotate((1, 3, 0, 2)) == 3
assert sort_by_switch_and_rotate((3, 1, 0, 2)) == 2
# Test tuples
assert sort_by_switch_and_rotate((0, 1, 2, 3)) == 0 # identity
assert sort_by_switch_and_rotate((1, 0, 2, 3)) == 1 # one switch
assert sort_by_switch_and_rotate((3, 0, 1, 2)) == 1 # one rotation
assert sort_by_switch_and_rotate((1, 2, 3, 0)) == 3 # max rotations
assert sort_by_switch_and_rotate((1, 0, 3, 2)) == 6 # from @MattTimmermans
How to sort a list in 3 steps:
Start: (1, 3, 0, 2)
Switch: (3, 1, 0, 2)
Rotate: (1, 0, 2, 3)
Switch: (0, 1, 2, 3)
How to sort a list in 2 steps:
Start: (3, 1, 0, 2)
Rotate: (1, 0, 2, 3)
Switch: (0, 1, 2, 3)
How to sort a list in 0 steps:
Start: (0, 1, 2, 3)
How to sort a list in 1 steps:
Start: (1, 0, 2, 3)
Switch: (0, 1, 2, 3)
How to sort a list in 1 steps:
Start: (3, 0, 1, 2)
Rotate: (0, 1, 2, 3)
How to sort a list in 3 steps:
Start: (1, 2, 3, 0)
Rotate: (2, 3, 0, 1)
Rotate: (3, 0, 1, 2)
Rotate: (0, 1, 2, 3)
How to sort a list in 6 steps:
Start: (1, 0, 3, 2)
Switch: (0, 1, 3, 2)
Rotate: (1, 3, 2, 0)
Rotate: (3, 2, 0, 1)
Switch: (2, 3, 0, 1)
Rotate: (3, 0, 1, 2)
Rotate: (0, 1, 2, 3)
我不知道这是否给您的问题给出答案，我发现这很棘手。
我写了一堂课要在循环中使用：
class Marbles:
def __init__(self, marbles):
self.marbles = marbles
self.len = len(marbles)
def switch(self):
self.marbles[0], self.marbles[1] = self.marbles[1], self.marbles[0]
if self.is_sorted(): raise StopIteration
return self
def rotate(self):
self.marbles = self.marbles[1:] + [self.marbles[0]]
if self.is_sorted(): raise StopIteration
return self
def is_sorted(self):
return all(self.marbles[i] <= self.marbles[i+1] for i in range(self.len-1))
def show(self):
print(self.marbles)
在移动大理石后，它会引发异常StopIteration，因此循环可以断开。
所以，对于您的示例(1,3,0,2)：
marbles = Marbles([1,3,0,2])
marbles.switch().show() #=> [3, 1, 0, 2]
marbles.rotate().show() #=> [1, 0, 2, 3]
marbles.switch().show() #=> StopIteration because it is sorted
现在，您可以使用蛮力编写几个循环，在此交换操作顺序（在这种情况下，我认为该规则是开关和旋转的替代序列）：
tested = []
original = [3,1,0,2]
marbles = Marbles(original)
while True:
try:
marbles.switch().show()
marbles.rotate().show()
except: break
if original in tested: break
tested.append(marbles.marbles)
print(marbles.is_sorted())
marbles.show()
print("-"*20)
tested = []
original = [3,1,0,2]
marbles = Marbles(original)
while True:
try:
marbles.rotate().show()
marbles.switch().show()
except: break
if original in tested: break
tested.append(marbles.marbles)
print(marbles.is_sorted())
marbles.show()
这返回
# [1, 3, 0, 2]
# [3, 0, 2, 1]
# [0, 3, 2, 1]
# [3, 2, 1, 0]
# [2, 3, 1, 0]
# [3, 1, 0, 2]
# [1, 3, 0, 2]
# [3, 0, 2, 1]
# False
# [3, 0, 2, 1]
# --------------------
# [1, 0, 2, 3]
# True
# [0, 1, 2, 3]
在开始时选择一个数字，您将从不开关代表列表中无法动的开始/结束。无论您选择哪个数字，您的简单切换级别元素和旋转的算法都将始终工作。
请注意，如果您不选择最小或最大的元素，则" Out Out Out Out Out Out of Order"会变得有些复杂，因为正确的顺序是循环的。比您选择的元素要小。
尝试所有选择以查看哪个给出最快的结果。
例如：
不要切换0：
3,1,0,2-1,3,0,2-3,0,2,1-1-0,2,1,3-2,1,3,0-1,2,3,0-2,3,0,1-3,0,1,2-0,1,2,3
不要切换1：
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
不要切换2：
3,1,0,2-1,0,2,3-0,1,2,3
不要切换3：
3,1,0,2-1,0,2,3-0,1,2,3
编辑：当所有最佳解决方案都需要所有元素参与掉期时，这并没有找到最好的。但是，它总是找到解决方案，并且是多项式时间。
python提供了使用列表sort Inproult函数对列表进行排序的最佳方法。例如：
my_list=[3,1,0,2]
my_list.sort()
print(my_list)
输出：[0,1,2,3]