Для программистов в наших рядах
Jul. 1st, 2009 04:42 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
irene221bИнтересная алгоритмическая проблемка.
Есть набор строк (одной длины, но это вроде бы неважно). Есть два параметера: Х - максимальное число позволенных do-not-care симоволов, и N - максимальное число строк в результате. Нужно разбить исходный набор в соответствии с этими параметерами, ну или установить, что это невозможно.
Например:
1 2 3 1 2 3 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 3 3 3 7 8 9
При Х = 3 результат такой: 1 2 3 ? ? ? 7 8 9, но при Х = 2 это уже не годится, нужно выдать:
1 2 3 ? ? 3 7 8 9
1 2 3 4 5 6 7 8 9
Строки запихнуты в ternary tree, которое позволяет поиск всех строк на опредленном расстоянии от данной строки, а так же поиск всех строк, удовлетворяющих шаблонам с do-not-care.
Но можно запихнуть и в какую-нибудь другую структуру.
Есть набор строк (одной длины, но это вроде бы неважно). Есть два параметера: Х - максимальное число позволенных do-not-care симоволов, и N - максимальное число строк в результате. Нужно разбить исходный набор в соответствии с этими параметерами, ну или установить, что это невозможно.
Например:
1 2 3 1 2 3 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 3 3 3 7 8 9
При Х = 3 результат такой: 1 2 3 ? ? ? 7 8 9, но при Х = 2 это уже не годится, нужно выдать:
1 2 3 ? ? 3 7 8 9
1 2 3 4 5 6 7 8 9
Строки запихнуты в ternary tree, которое позволяет поиск всех строк на опредленном расстоянии от данной строки, а так же поиск всех строк, удовлетворяющих шаблонам с do-not-care.
Но можно запихнуть и в какую-нибудь другую структуру.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2009-07-01 04:32 pm (UTC)Давай сложим эти строки в двумерный массив символов, после чего пройдемся по всем столбцам этого массива. Для каждого столбца вернем True, если все символы в нем равны, а иначе False. Если количество False столбцов больше чем X - решения нет. Если не больше, то все хорошо, можно строить ответ.
Проходим по любой строке, если для текущей позиции у нас насчитано True - выписываем символ из этой позиции, а если нет - пишем '?'.
Virtual keyboard is in another tab. :-)
Date: 2009-07-01 04:42 pm (UTC)true true true false false false true true true.
And yet there is a solution for X = 2.
no subject
Date: 2009-07-01 04:45 pm (UTC)no subject
Date: 2009-07-01 05:27 pm (UTC)1 2 3 ? ? 3 7 8 9
1 2 3 4 5 6 7 8 9
Если все можно было бы запихнуть в одну строку, и только сказать да или нет, то мне вообще никакая структура не нужна была бы, можно было бы строить результат даже по мере получения строк по одной.
no subject
Date: 2009-07-01 07:07 pm (UTC)Ушел думать..
no subject
Date: 2009-07-01 08:39 pm (UTC)Количество строк - до сотни, размер примерно 16 байт.
no subject
Date: 2009-07-01 07:13 pm (UTC)Алгоритм не быстрый и прожорливый
Date: 2009-07-02 07:46 am (UTC)no subject
Date: 2009-07-03 06:00 am (UTC)no subject
Date: 2009-07-03 02:20 pm (UTC)no subject
Date: 2009-07-03 06:14 am (UTC)Если б лампу мне дал Ападдин,
Я б велел, чтоб отвез меня джин
На ковре-самолёте
Не к какой-нибудь тёте,
А к Ирэн 221
Не нужны мне ни А и ни Б,
Пусть сидят себе там на трубе.
С днем рожденья поздравлю
И, конечно, оставлю
Благодарность счастливой судьбе.
Заявляю открыто пред всеми я
Ни к чему мне скандал и в Богемии.
Нет, не Адлер мой Бог,
Да и я не Шерлок,
Извините, коль вдруг не по теме я
Некий старый смешной господин,
Но ценитель ликеров и вин,
Нынче выпьет мускату
За прекрасную дату,
За Ирен 221
Спасибо. :-)
Date: 2009-07-03 02:22 pm (UTC)Извините за, гхм, ударение. ;-)
Re: Спасибо. :-)
Date: 2009-07-03 08:41 pm (UTC)Нет, Не Адлер Ирэн,
Что взяла меня в плен...
да и 221b обязывают...
Re: Спасибо. :-)
Date: 2009-07-03 10:13 pm (UTC)А 221 отлично срифмовалось как раз.
Re: Спасибо. :-)
Date: 2009-07-03 10:46 pm (UTC)Твой Ватсон...
no subject
Date: 2009-07-03 11:19 am (UTC)Алгоритм по идее однопроходный относительно движения по тернарному траю (TST), но распараллеливающийся на набор отслеживаемых путей движения по нему. Основной принцип: отслеживаем все валидные пары (n,x) таких что 1<=n<=N, 0<=x<=X, по мере продвижения вглубь TST по всем возможным путям.
Начинаем с корня TST, отслеживаем пока что единственный путь, начатый из корня, множество пар инициализируем парой (1,0).
Крутим циклы "времени" продвижения по TST (т.е. по входным данным), затем по всем текущим узлам TST на всех отслеживаемых путях продвижения.
На каждом шаге смотрим кол-во ветвлений текущего узла на текущем пути TST - обозначим m.
Пока m==1 просто продвигаемся дальше. Как только встречается ветвление m>1, так для каждой пары (n,x) множества делаем ее замену двумя парами (n,x+1) и (n+m-1,x), но добавляя при этом только валидные пары с n<=N и x<=X. Заменяем отслеживание текущего пути в TST на мониторинг m дальнейших вариантов.
Цикл заканчивается либо когда множество пар оказалось пустым (решения нет), либо когда все входные данные успешо проанализированны. Тогда из множества берется любая лучшая пара, т.е. та у которой минимально сначала n затем x. Где-то параллельно (видимо, как-то ассоциированно с отслеживаемыми путями и парами) должны еще строиться возможные шаблоны результата, чтобы потом у наилучшей пары взять ее ассоциированный шаблон.