Как можно реализовать?

Question

[ily94]

Есть две строки из А={0,1,2,3}* Нужно выяснить можно ли одну из них получить из другой несколькими бинарными перестановками и найти количество таких перестановок.

Насколько я понимаю получить одну из другой - это узнать,является ли первая анаграммой другой?
Как можно реализовать "найти количество таких перестановок"?(Сложность в том,что символы могут повторяться)

Answer 1

[Алексей]

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

Comments

[ily94]

Спасибо! С удалением отличная идея вышла!

Answer 2

[Mercury13]

Подсчитать кол-во нулей (единиц, двоек, троек). Если неодинаково — нельзя.
Иначе — подсчитаем такую матрицу (4×4). Если в 1-й строке на i-м месте 1, а во 2-й 3, прибавляем единицу к a[1, 3].
a[i, i] не учитываем: они уже на своих местах.
a[i, j] и a[j, i] взаимокоменсируем: каждая такая парочка даёт min(a[i, j], a[j, i]) перестановок.
Точно так же пересматриваем все тройки a[i, j], a[j, k] и a[k, i]. Как всегда, взаимокомпенсируем их; каждая такая тройка даёт 2·min(•, •, •) пререстановок.
Остаётся просуммировать всё, что осталось (кроме диагонали, разумеется), и помножить на 3/4.

Answer 3

[iegor]

Если правильно понял задачу, изучите динамическое программирование, в сторону поиска наимешего расстояния редактирования.
Для сравнения строк в python есть стандартная библиотека difflib.