先说明理由:)
切换:切换位置 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)，它永远不会以 switch - rotate - switch - rotate ... 方法结束。
有没有更好的方法同时使用切换和旋转来高效地获得排序结果？
最佳答案
我现在想不出最有效的方法(即使用最少数量的旋转和切换的方法)来对任何给定列表进行排序。但我可以想出一种方法，给定一个列表，找到最有效的方法。
将您的问题视为 breadth-first search problem在图形数据结构中。如果可以通过单次交换或单次轮换从当前列表中获取一个列表，则考虑将其直接指向另一个列表。进行广度优先搜索，直到得到排序好的列表。那么从原始列表到排序列表的路径是“最高效的方式”。您不需要实际设置图形数据结构——这只是给出了算法的想法。
我很快会尝试在这里获取一些特定的代码，但这里是一个大纲。从仅包含原始列表(需要是元组，因此我将开始称它们为元组)作为键和 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)
关于python - 在 python 中混合使用 switch 和 rotate 对数字进行排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54840758/