Есть две строки. Мы считаем что они равны в случае если есть набор операций по трансформации одной из строки в другую. Доступные операции трансформации это перестановка местами нечетных символов в строке. Вторая операция перестановка местами четных символов.
Как решать? У меня есть решение, но наверное правильно будет его в конце сказать. Как бы вы решили?

Здравствуйте, Gattaka, Вы писали:

G>Есть две строки. Мы считаем что они равны в случае если есть набор операций по трансформации одной из строки в другую. Доступные операции трансформации это перестановка местами нечетных символов в строке. Вторая операция перестановка местами четных символов.
G>Как решать? У меня есть решение, но наверное правильно будет его в конце сказать. Как бы вы решили?


1) строка есть суперпозиция четной и нечетной строк
2) строки равны, если попарно равны их четные и нечетные строки
3) равенство строк считать как
a) подсчитать количества разных символов в строках
b) сравнить эти количества. если они равны, то строки равные

Не?

Здравствуйте, Gattaka, Вы писали:

G>Есть две строки. Мы считаем что они равны в случае если есть набор операций по трансформации одной из строки в другую. Доступные операции трансформации это перестановка местами нечетных символов в строке. Вторая операция перестановка местами четных символов.
G>Как решать? У меня есть решение, но наверное правильно будет его в конце сказать. Как бы вы решили?

Подзадача. Мы считаем, что две строки равны, если они равны с точностью до перестановок всех своих символов.
Тогда для сравнения (и даже введения порядка, а не только равенства) достаточно посимвольно отсортировать и сравнить отсортированные.
После этого возвращаемся к исходной задаче. Расслаиваем строки на нечётные и чётные подпоследовательности, дальше как с гусём.

Достаточно — не значит "необходимо". Всё-таки, сортировка — удовольствие дорогое.
По сути же, нам надо найти разность двух мультимножеств, заданных сырыми массивами.
Как это можно сделать:

1) отсортировать (ценой разрушения исходных строк) (или ценой размещения копий этих строк)
2) представить мультимножества таблицами счётчиков (цена вопроса — размещение этих самых таблиц) — даже одной таблицей, на самом деле: сперва туда прибавляем, потом оттуда вычитаем
3) выполнить поиск вхождения символов одной строки в другую (ценой разрушения одной строки)

Можно комбинировать методы, выбирая тот или иной в зависимости от длины строк (и от их алфавита: для байтовых сделать счётчики дёшево — 256-элементная страница, для юникодных потребуется уже хештаблица какая-нибудь, или дерево страниц).
Это надо профилировать.

Здравствуйте, Gattaka, Вы писали:

G>Есть две строки. Мы считаем что они равны в случае если есть набор операций по трансформации одной из строки в другую. Доступные операции трансформации это перестановка местами нечетных символов в строке. Вторая операция перестановка местами четных символов.
G>Как решать? У меня есть решение, но наверное правильно будет его в конце сказать. Как бы вы решили?

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

Здравствуйте, Pzz, Вы писали:

Pzz>Здравствуйте, Gattaka, Вы писали:

G>>Есть две строки. Мы считаем что они равны в случае если есть набор операций по трансформации одной из строки в другую. Доступные операции трансформации это перестановка местами нечетных символов в строке. Вторая операция перестановка местами четных символов.
G>>Как решать? У меня есть решение, но наверное правильно будет его в конце сказать. Как бы вы решили?

Pzz>Ну, казалось бы, если у строк одинаковый набор четный символов и одинаковый набор нечетных символов ("одинаковый" — значит, что встречаются одни и те же символы в одном и том же количестве), то одну строку к другой привести завсегда можно...
Точно? Есть мат. доказательство?

Здравствуйте, Gattaka, Вы писали:

Pzz>>Ну, казалось бы, если у строк одинаковый набор четный символов и одинаковый набор нечетных символов ("одинаковый" — значит, что встречаются одни и те же символы в одном и том же количестве), то одну строку к другой привести завсегда можно...
G>Точно? Есть мат. доказательство?

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

Здравствуйте, Gattaka, Вы писали:

Pzz>>Ну, казалось бы, если у строк одинаковый набор четный символов и одинаковый набор нечетных символов ("одинаковый" — значит, что встречаются одни и те же символы в одном и том же количестве), то одну строку к другой привести завсегда можно...
G>Точно? Есть мат. доказательство?

Элементарно же.

Операции обмен(i,j) создают группу всех перестановок.
Пусть у нас есть исходная тривиальная перестановка E=(0,1,2,3,...) и целевая произвольная P=(a,b,c,d,...)
P0 = E·(0,a)·(a, a'=indexof(a,P))·(a',a'')·(a'',a''')... где a', a'', a'''... — цикл в перестановке P, проходящий через 0.
P1 = E·(1,b)·(b,b')... — следующий цикл (например, проходящий через 1, — если 1 не участвовала в цикле 0).
и т.д.
P = произведение P0,P1,... — независимых циклов.

Если же у нас есть обмены только соседних, -о перации обмен(i,i+1) — то они всё равно создают группу всех перестановок потому, что (i,i+2) = (i,i+1)·(i+1,i+2)·(i,i+1), а далее — по индукции.

Здравствуйте, Кодт, Вы писали:

К>Элементарно же.

Не особо. Можно совсем тривиальной индукцией.

A[0..L-1], B[0..L-1] — строки длины L.
База: Для N = 1 утверждение очевидно.
Предположение: Пусть верно для строк длины N.
N->N+1: Берем s=A[N], ищем в B символ s и меняем его местами с B[N]. Получили, что в N-ой позиции строки совпадают. Осталось привести к единому виду A[0..N-1] и B[0..N-1]. А это мы уже умеем делать по индуктивному предположению.

Здравствуйте, Lexey, Вы писали:

К>>Элементарно же.
L>Не особо. Можно совсем тривиальной индукцией.

Ну или так.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Lexey, Вы писали:

К>>>Элементарно же.
L>>Не особо. Можно совсем тривиальной индукцией.

К>Ну или так.
Кодт у меня вопрос. Вот есть алгоритм сортировки — простой выбор, известно что он сортирует любые массивы и использует только обмены.
Является ли существование этого алгоритма доказательством того что обменами можно сделать любую перестановку? помойму да.

Здравствуйте, iriska2, Вы писали:

I>Кодт у меня вопрос. Вот есть алгоритм сортировки — простой выбор, известно что он сортирует любые массивы и использует только обмены.
I>Является ли существование этого алгоритма доказательством того что обменами можно сделать любую перестановку? помойму да.

ЕСЛИ алгоритм сортировки обменами сортирует ЛЮБЫЕ массивы (над элементами которых определён полный строгий порядок)
и поскольку обмены обратимы,
и когда мы покажем, что перестановки изоморфны наборам уникальных натуральных чисел (над которыми, очевидно, определён полный строгий порядок),
ТОГДА доказательство, что обменами можно сделать любую перестановку — у нас в кармане.

Докажите лемму в первой строчке.
Что-то мне кажется, что для этого потребуется доказать независимым способом лемму из последней строчки.
Но тогда окончательный ход мыслей здесь внезапно приобретёт такой вид: "ПОСКОЛЬКУ обменами можно сделать любую перестановку ТО обменами можно сделать любую перестановку."

Здравствуйте, Gattaka, Вы писали:

G>Как решать? У меня есть решение, но наверное правильно будет его в конце сказать. Как бы вы решили?

Какие, блин, все умные.
Нет вот что бы в лоб решать: Генерите все перестановки в одной строке ( в смысле декартово произведение всех перестановок чётной подстроки и всех перестановок нечётной) и смотрите, есть ли среди сгенерированного множества строк вторая

Здравствуйте, Erop, Вы писали:

E>Какие, блин, все умные.
E>Нет вот что бы в лоб решать: Генерите все перестановки в одной строке ( в смысле декартово произведение всех перестановок чётной подстроки и всех перестановок нечётной) и смотрите, есть ли среди сгенерированного множества строк вторая

Пусть длина первой строки N (если они не равны, то лучше взять более длинную из них)
генерим все перестановки последовательности 1, 2, 3,.. N
Фильтруем их по принципу (на чётных местах только чётные, на нечётных, только нечётные).
По каждой отфильтрованной перестановке генерим строку, используя эти числа, как позиции символов в первой строке и сравниваем полученную строку со второй

Бинго!

Здравствуйте, Erop, Вы писали:

E>Нет вот что бы в лоб решать: Генерите все перестановки в одной строке ( в смысле декартово произведение всех перестановок чётной подстроки и всех перестановок нечётной) и смотрите, есть ли среди сгенерированного множества строк вторая

Была такая задача на каком-то форуме: написать самую долгую сортировку, которая не делает ничего бессмысленного. Генерация всех перестановок и проверка упорядоченности результата, там, конечно, была, но от победителя очень сильно отставала. Деталей уже не помню.

Здравствуйте, cures, Вы писали:

C>Была такая задача на каком-то форуме: написать самую долгую сортировку, которая не делает ничего бессмысленного. Генерация всех перестановок и проверка упорядоченности результата, там, конечно, была, но от победителя очень сильно отставала. Деталей уже не помню.

Вариации на тему богосорта — https://en.wikipedia.org/wiki/Bogosort

Как они там ловко припахали функцию Аккермана...