| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > нахождение независимых цепочек слов |
| Автор: motorway 6.11.2009, 01:14 |
| Есть несколько строк со словами (комбинациями символов), разделенными разделителями. Пример: a:b:c:d b:e:f g:h i:j g:k: z:w:f Подскажите, как оптимальным образом получить из этого независимые цепочки слов (напр., это синонимы, и нужно получить независимые цепочки синонимов), т.е. такие, про которые известно, что данные слова не встречаются в других цепочках. В данном случае мы должны получить: a:b:c:d:e:f:w:z g:h:k i:j Желательно без рекурсий. |
| Автор: Lipetsk 6.11.2009, 09:57 |
| как-то путано написали вам попросту нужно объединить слова имеющие одинаковые буквы берете исходное слово, каждую его букву ищите в результирующих словах если нашли, то объединяете такие результирующие слова в одно и добавляете буквы исходного слова если не нашли, то к результирующим словам добавляете новое слово из букв исходного выполняем тоже самое со следующим исходным словом как видите, рекурсии не наблюдается |
| Автор: motorway 6.11.2009, 17:16 |
| Поясню еще. Здесь под буквами имелись в виду некоторые слова различные, просто для сокращения записи написал. Вот еще пример: есть синонимы (степень "схожести" условная): автомобиль:машина:тачка тачка:самодвижущийся экипаж трамвай:рельсовый транспорт кэб:повозка повозка:карета метро:подземка Нужно объединить в строки независимые цепочки синонимов, то есть чтобы каждое слово в ней являлось синонимом других и не являлось синонимом для остальных слов из др. цепочек. В данном случае получим: автомобиль:машина:тачка:самодвижущийся экипаж трамвай:рельсовый транспорт кэб:повозка:карета метро:подземка Так вот, как это сделать оптимально? Добавлено через 3 минуты и 11 секунд В общем, это напоминает задачу о проезде на трамвае из одной точки в другую. Если пути, соединяющие эти точки, есть, то проехать можно, если нет - это независимые точки. Напр., связи слова метро с кэбом нет, в том числе через другие синонимы, поэтому они в разных строках в итоге получаются |
| Автор: Lipetsk 9.11.2009, 09:01 |
| сказанное мной ранее остается в силе и в этом случае |