用开关混合排序数字并在python中旋转 [英] sorting numbers with mix of switch and rotate in python

问题描述

首先要论证:)

切换:在位置0和1切换弹珠.

Switch: Switch the marbles in positions 0 and 1.

旋转:将大理石从位置0移至位置N-1，并将所有其他大理石向左移动一格(降低一个索引).

Rotate: Move the marble in position 0 to position N - 1, and move all other marbles one space to the left (one index lower).

如果有数字列表(1,3,0,2)开关-旋转-开关将对数字进行排序3,1,0,2-1,0,2,3-0,1,2,3

If there is a list of number (1,3,0,2) switch - rotate - switch will sort the numbers 3,1,0,2 - 1,0,2,3 - 0,1,2,3

但是如果我们有(3,1,0,2)，则它永远不会以switch -rotate-switch-rotate ...方法结束.

But if we have (3,1,0,2), it never ends with switch - rotate - switch - rotate ... method.

是否有更好的方法同时使用开关和旋转来有效地获得排序结果?

Is there a better way to use both switch and rotate to efficiently get the sorted result?

推荐答案

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

I cannot now think of the most efficient way (meaning the way that uses the smallest number of rotations and switches) to sort any given list. But I can think of a way, given a list, to find the most efficient way.

将您的问题考虑为图形数据中的宽度优先搜索问题结构体.如果可以通过一次交换或单次旋转从当前列表中获取列表，则考虑将其直接指向另一个列表.进行广度优先搜索，直到获得排序列表.这样，从原始列表到排序列表的路径就是最有效的方法".您实际上不需要设置图形数据结构，这只是给出了算法的思想.

Consider your problem to be a breadth-first search problem in a graph data structure. Consider a list to point directly to another list if it can be gotten from the current list by a single swap or single rotation. Do a breadth-first search until the sorted list is obtained. Then the path from the original list to the sorted list is "the most efficient way." You need not actually set up the graph data structure--this just gives the algorithm's idea.

我将尽力在这里获得一些特定的代码，但这只是概述.从仅包含原始列表(将是一个元组，因此我将开始称它们为元组)的字典作为键，并以 None 作为值.该词典包含已经看到的元组"作为键，并且对于每个键，值都是导致该键的元组.同样从仅包含原始元组的队列(可能是Python的 deque )开始.这是已看到但尚未处理"的队列.然后运行一个循环:从队列中弹出一个元组，检查它是否为排序后的元组，然后通过单个开关或旋转检查每个元组是否已被看到，将其添加到字典和队列中.最终，您将到达已排序的元组(如果正确定义了原始元组).使用已经看过"的字典将已排序的元组的路径打印回原始元组.

I'll try to get some specific code here soon, but here is an outline. Start with a dictionary containing only the original list (which will need to be a tuple, so I'll start calling them tuples) as a key and None as the value. This dictionary contains the "already seen tuples" as keys, and for each key the value is the tuple that lead to that key. Also start with a queue (probably Python's deque) that contains only the original tuple. This is the "seen but not yet processed" queue. Then run a loop: pop a tuple off the queue, check if it is the sorted tuple, then for each tuple reachable by a single switch or rotation check if it was already seen, add it to both the dictionary and the queue. Eventually you will reach the sorted tuple (if the original tuple was defined correctly). Use the "already seen" dictionary to print the path from the sorted tuple back to the original tuple.

这是基于该算法的代码.可以进行进一步的优化，例如内联 switched_or_rotated 例程，或者在第一次看到目标元组时检查目标元组，而不是等待处理后的元组.

Here is code based on that algorithm. Further optimizations could be done, such as in-lining the switched_or_rotated routine or checking for the target tuple when it is first seen rather than waiting for when it is processed.

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

这是您的两个示例和一些其他示例的测试代码.

Here is test code for your two examples and some additional examples.

# 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中旋转的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！