сортировка чисел со смесью переключателя и поворота в питоне

Question

Обоснование сначала:)

Переключатель: переключите шарики в позиции 0 и 1.

Поверните: переместите мрамор в положении 0 в положение N - 1 и переместите все остальные шарики одинпробел влево (на один индекс ниже).

Если есть список чисел (1,3,0,2), switch - rotate - switch будет сортировать числа 3,1,0,2 - 1, 0,2,3 - 0,1,2,3

Но если мы имеем (3,1,0,2), это никогда не заканчивается методом switch - rotate - switch - rotate ....

Есть ли лучший способ использовать и переключатель, и поворот, чтобы эффективно получить отсортированный результат?

Answer 1

В начале выберите одну цифру, которую вы никогда не переключите, чтобы обозначить неподвижное начало / конец в списке.Независимо от того, какое число вы выберете, ваш простой алгоритм переключения неупорядоченных элементов и поворота всегда будет работать.

Обратите внимание, что «не в порядке» становится немного сложнее, если вы не выберете наименьшееили самый большой элемент, так как правильный порядок является циклическим.Элемент, меньший, чем выбранный вами, идет после более крупного.

Попробуйте все варианты, чтобы увидеть, какой из них дает самый быстрый результат.

Например:

Не 't переключатель 0:

3,1,0,2 - 1,3,0,2 - 3,0,2,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

РЕДАКТИРОВАТЬ: Это не находитлучше всего, когда все лучшие решения требуют участия всех элементов в обменах.Тем не менее, он всегда находит решение, и это полиномиальное время.

Answer 2

Теперь я не могу придумать наиболее эффективный способ (то есть способ, который использует наименьшее количество поворотов и переключателей) для сортировки любого заданного списка.Но я могу придумать способ, исходя из списка, найти наиболее эффективный способ.

Рассмотрим вашу проблему как проблему поиска в ширину в структуре данных графа.Рассмотрим список, указывающий непосредственно на другой список, если он может быть получен из текущего списка с помощью одного свопа или одного поворота.Выполните поиск в ширину, пока не будет получен отсортированный список.Тогда путь от исходного списка к отсортированному списку является «наиболее эффективным способом».На самом деле вам не нужно настраивать структуру данных графа - это просто дает идею алгоритма.

Я постараюсь вскоре получить здесь какой-то конкретный код, но вот схема.Начните со словаря, содержащего только исходный список (который должен быть кортежем, поэтому я начну называть их кортежами) в качестве ключа и None в качестве значения.Этот словарь содержит «уже просмотренные кортежи» в качестве ключей, и для каждого ключа значением является кортеж, ведущий к этому ключу.Также начните с очереди (вероятно, Python's 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 </12365392/sortirovka-chisel-so-smesy-pereklychatelya-i-povorota-v-pitone
    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)

Answer 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]

Answer 4

Python обеспечивает лучший способ сортировки списка с помощью встроенной функции list sort.Например:

my_list=[3,1,0,2]
my_list.sort()
print(my_list)

вывод: [0,1,2,3]