?

Log in

No account? Create an account

Программистская задачка - Общество дровосеков Бердичева по изучению Мишны

Nov. 22nd, 2010

02:34 pm - Программистская задачка

Previous Entry Share Next Entry



Дан массив уникальных строк одинаковой длины. Требуется для каждой строки найти набор пар (позиция, значение), уникально идентифицирующих строку в массиве, минимизируя сумму мощностей наборов. Например, для массива
"корова", "ворона", "корона"
наборами будут
(4, 'в'), (0, 'в'), [(0, 'к'), (4, 'н')];
для массива "aabb", "abab", "abba", "baab", "baba", "bbaa" ими будут наборы, описывающие, скажем, положение букв 'a' в каждой строке, и т.п.

Я пока не придумал, как это делать эффективно.

Comments:

[User Picture]
From:fenikso
Date:November 22nd, 2010 10:44 pm (UTC)
(Link)
Чем-то немного похоже на perfect hash, но это мне может только казаться.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 22nd, 2010 10:50 pm (UTC)
(Link)
Я тоже подумал, как бы к этому делу perfect hash прикрутить, но похоже лишь отдаленно, т.к. в моем случае ищутся независимые наборы позиций.
(Reply) (Parent) (Thread)
[User Picture]
From:besisland
Date:November 23rd, 2010 01:16 am (UTC)
(Link)
Взять все пары. Подсчитать частоты. Такое начало уже неэффективно?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 23rd, 2010 01:32 am (UTC)
(Link)
Пары символов в строках, надо понимать? И что делать, если не нашлось ни одной уникальной?

В худшем случае строк из символов из k-символьного алфавита длиной n может быть kn (или почти столько), и ответом будут (почти для всех строк) сами эти строки.
(Reply) (Parent) (Thread)
[User Picture]
From:scolar
Date:November 23rd, 2010 02:36 am (UTC)
(Link)
Я бы попробовал плясать в сторону расстояния редактирования.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 23rd, 2010 03:47 am (UTC)
(Link)
Надо подумать. Возьмем те же aabb. В матрице расстояний будут числа от 2 до 4 (как мы знаем, ответ 2). Если к каждой строке приписать уникальную букву, все элементы матрицы увеличатся на 1, а ответ станет 1. Надо думать дальше.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:November 23rd, 2010 02:45 am (UTC)
(Link)
Все придумано до нас. Это небось Radix tree, которое употребляется для поиска маршрутов. Или не оно?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 23rd, 2010 03:00 am (UTC)
(Link)
Проверяем:
aabb
bab
ba
baab
ba
baa


Как из этого следует, что для всех строк достаточно двух символов?
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:November 23rd, 2010 03:06 am (UTC)
(Link)
Э, каких двух символов?
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:November 23rd, 2010 03:10 am (UTC)
(Link)
Каждая строка уникально определяется расположением букв 'a' в ней, которых две в каждой строке.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:November 23rd, 2010 03:28 am (UTC)
(Link)
Так задача не в том, чтобы как можно дешевле различить строчки?
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:November 23rd, 2010 03:32 am (UTC)
(Link)
В том-то и дело, что нет. Была бы задача просто различить, я бы gperf запустил.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:November 23rd, 2010 03:35 am (UTC)
(Link)
А каков тогда в этой задаче э-э-э "физический смысл"?
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:November 23rd, 2010 03:48 am (UTC)

Ничего не ответила рыбка, только хвостиком махнула

(Link)
- Павел Андреич, Вы шпион?
- Видишь ли, Юра...
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:December 1st, 2010 11:41 pm (UTC)
(Link)
Докладываю: эта задача оказалась эквивалентна MAX-SAT.

(Reply) (Parent) (Thread)