Поиск чисел в списке перестановок на основе положения одного из чисел в списке

Question

Я кодирую программу, которая решает математическую задачу с конкретными условиями.

В этой математической задаче есть семь слотов.В начале, первые три слота заняты номерами 1, 2 и 3. В середине есть пустой слот.Следующие три номера 4, 5 и 6. Всего семь слотов.

Цель проблемы состоит в том, чтобы 1 2 и 3 поменялись местами с 4 5 и 6. Одновременно можно перемещать только одно число.Он может перемещаться по другому номеру в пустой слот (ноль) или перемещаться вбок, переключаясь с пустым слотом.

Ниже приведена визуализация старта:

1 2 3 0 4 5 6

---

Желаемый результат показан ниже:

4 5 6 0 1 2 3

---

Имейте в виду, что это не обязательно должно быть в этомпорядка 4 5 6 с одной стороны и 1 2 3 с другой с 0 в середине.

Программа, которую мы создаем, использует itertools для списка перестановок.Затем, основываясь на позиции нуля, находит перестановку, которая подходит к следующему ходу.

Мне нужно, чтобы конкретные комбинации были извлечены (выведены) из этого списка на основе положения нулей в комбинациях.Ниже приведен код.

import time
import itertools

nonStop = True
answerList = [1, 2, 3, 0, 4, 5, 6]

combinations = itertools.permutations([1, 2, 3, 0, 4, 5, 6])

while nonStop == True:
    for value in combinations:
        i = 0
        print(value)
        i += 1
        time.sleep(2)

Заранее спасибо.Любая помощь будет принята с благодарностью!

Answer 1

Вот несколько советов высокого уровня по вашей программе.Я предполагаю, что при каждом движении ноль поменяется местами с числом, которое находится на расстоянии одного или двух слотов от нуля.Я также предполагаю, что вы хотите найти наименьшее количество ходов, которое приведет вас от первоначального списка к «желаемому результату», и что распечатка должна показывать все позиции от начальной позиции до желаемого результата.

Если вы знакомы с теорией графов (также называемой теорией сетей), вы можете легко решить свою проблему, выполнив поиск в ширину от начальной позиции до любой желаемой позиции.Узлами на вашем графике являются 5 040 возможных перестановок, и два узла имеют грань между ними, если вы можете перейти от одной позиции к другой за один ход.

Если вы не знаете теорию графов, вы можетеиспользуйте этот следующий подход.Вы можете использовать две общие структуры данных: очередь (например, collection.deque ) и словарь.Поместите начальную позицию в очередь.Также поместите его в качестве ключа в словаре со значением None.

Затем запустите цикл.При каждом проходе по циклу удаляйте одну позицию из очереди.Из этой позиции будет не более четырех возможных ходов: поменяйте местами ноль с позицией 2 слева, 1 слева, 1 справа или 2 справа от нуля.(Если ноль находится в конце или около конца, возможных ходов будет меньше.) Для каждого из этих ходов, если результирующей позиции еще нет в словаре, добавьте ее в очередь и словарь.Значение словарной записи - это позиция, которую вы только что заняли в очереди.Если полученная позиция уже есть в словаре, ничего не делать.

Теперь проверьте, является ли полученная позиция «желаемым результатом».Если нет, продолжайте цикл.Если это так, используйте словарь, чтобы сохранить все ходы от желаемого результата обратно в исходное положение.Затем распечатайте эти позиции в нужном порядке, и все готово - прервите цикл.

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

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