| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Минимальное количество инверсий |
| Автор: hter 25.12.2013, 17:32 |
| Даются две последовательности. Надо найти количество минимальных инверсий, которых надо сделать, что б совпали последовательности. Например: a = 2 3 1 5 4 и b = 5 2 4 1 3. Тут надо три инверсии, что бы a совпало с b Пока я понял, что потребуется столько же инверсий для перевода a^-1*b в тождественную(1,2,3,4,5). Ну и нашел точки разрыва. А что дальше делать не понимаю. И не могу найти где бы по русски было нормально написано. |
| Автор: Akina 25.12.2013, 17:41 |
| Что ты подразумеваешь под словом "инверсия"? Но в принципе тебе нужен алгоритм вроде расстояния Левенштейна. |
| Автор: hter 25.12.2013, 18:55 |
| расстояния Левенштейна, там можно удалять, вставлять и менять по одному символу. под инверсией: 2 3 1 5 4 иверсией будет: 4 5 1 3 2 соответственно: 5 2 (4 1 3) (5 2 3 1) 4 (1 3 2) 5 4 2 3 1 5 4 |
| Автор: Akina 25.12.2013, 20:47 | ||
Я говорю "вроде". Различие - только в перечне трансформаций. А подход к поиску абсолютно такой же - просто недоступны некоторые стандартные оптимизации процесса, основанные именно на перечне модификаций. |
| Автор: hter 26.12.2013, 09:57 |
| Спасибо, очень помогли |
