python - 在 python 中混合使用 switch 和 rotate 对数字进行排序

Question

先说明理由:)

切换:切换位置 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 ... 方法结束。

有没有更好的方法同时使用切换和旋转来高效地获得排序结果？

Answer 1

我现在想不出最有效的方法(即使用最少数量的旋转和切换的方法)来对任何给定列表进行排序。但我可以想出一种方法，给定一个列表，找到最有效的方法。

将您的问题视为 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)