Сжатие текста

@Андрей Рощупкин · Регистрация: 01.03.2016

Студворк — интернет-сервис помощи студентам

Добрейшего вечера всем)
Задача: сшить N-ое количество строк так, чтобы в выходной строке минимальной длины можно было найти эти строки.
Например из строк:
wombat
batman
batch
rabat
bat
должна получится rabatchwombatman
На вход подаются число N и N слов, каждое в отдельной строке
Реализация важна не обязательно на питоне

@eaa · 17.02.2020, 23:48

Ограничения?

@Андрей Рощупкин · 18.02.2020, 09:59 **[ТС]**

Ограничений нет)

Рыжий Лис · 18.02.2020, 10:41

Сообщение от Андрей Рощупкин

должна получится rabatchwombatman

Не обязательно:

Code
1
2
3
4
5
6
7
8
wombatmanrabatch
wombatchrabatman
wombatmanrabatch
wombatchrabatman
rabatmanwombatch
rabatchwombatman
rabatmanwombatch
rabatchwombatman

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import re
import itertools
 
t = '''\
wombat
batman
batch
rabat
bat'''
result = []
for ls in itertools.permutations(t.split('\n')):
    word = ':'.join(ls)
    print(word, end=' ')
    while True:
        word2 = re.sub(r'(\w*):\1', r':\1', word)
        if word2 == word:
            break
        word = word2
    print(word2)
    result.append(word2.replace(':', ''))
result.sort(key=len)
for i in result:
    print(i)

@Андрей Рощупкин · 18.02.2020, 11:20 **[ТС]**

Очень долго работает, когда слов больше 7
И работает не совсем правильно, некоторые слова обрезает(

Рыжий Лис · 18.02.2020, 12:18

Конечно, долго. Сложность всех перестановок O(N!) (факториал N).

Хоть бы показали примеры, где слова неправильно обрезаются...

@Андрей Рощупкин · 18.02.2020, 18:31 **[ТС]**

odd
bad
time
meet
dad
lamb
kangaroo

Самый короткий ответ по вашей программе lambadtimeetkangarodad
Слово kangaroo обрезалось

Рыжий Лис · 18.02.2020, 19:00

Вроде, пофиксил:

Python
1
2
3
4
5
6
7
8
9
10
11
def z(s):
    #print(s)
    while True:
        s2 = re.sub(r'(\w):\1', r'\1:', s)
        #print(s2)
        if s2 == s:
            return s2.replace(':', '')
        s = s2
 
assert z('odd:dad') == 'oddad'
assert z('kangaroo:odd') == 'kangaroodd'

Добавлено через 2 минуты
Блин, не работает:

Python
1
z('kangaro:oodd')

Добавлено через 10 минут
Так работает:

Python
1
2
3
4
5
6
7
8
def z(s):
    while True:
        s2 = re.sub(r'(\w+):\1', r'\1', s)
        if s2 == s:
            return s2.replace(':', '')
        s = s2
assert z('odd:dad') == 'oddad'
assert z('kangaro:oodd') == 'kangaroodd'

Оказывается, после склейки двух слов нужно было считать, что получается одно слово.

Code
1
2
3
4
5
6
7
8
9
10
11
12
timeetlambadadkangaroodd
timeetlambadkangarooddad
timeetkangarooddadlambad
timeetkangarooddlambadad
lambadtimeetkangarooddad
lambadadtimeetkangaroodd
lambadadkangarooddtimeet
lambadkangarooddadtimeet
kangarooddtimeetlambadad
kangarooddadtimeetlambad
kangarooddadlambadtimeet
kangarooddlambadadtimeet

@Андрей Рощупкин · 18.02.2020, 19:19 **[ТС]**

Просто твой код не совсем подходит, мне нужно обработать 1000 (на самом деле 797) слов)
И такой программой это будет очень сложно сделать

Рыжий Лис · 18.02.2020, 19:24

На самом деле это похоже на NP-задачу. Если тебе нужно самое оптимальное решение - то нужно решать её только полным перебором O(N!). А вот если тебе нужно любое решение, близкое к оптимальному (но могут найтись решения, которые лучше. Или не найтись, если очень слишком повезёт) - нужно брать другие методы.

Как вариант, могу предложить взять генетические алгоритмы для поиска решения.

@Андрей Рощупкин · 18.02.2020, 19:30 **[ТС]**

сейчас работаю над решением в лоб тройным вложеным циклом)

Рыжий Лис · 18.02.2020, 19:32

Спойлер: не поможет. Всего комбинаций перестановок слов: 797! (факториал 797). Среди них есть то самое решение, которое даст самую минимальную строку.

В любом случае, у вас теперь есть правильно работающая функция для сжатия строки.

@eaa · 19.02.2020, 10:18

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# префиксы
('odd', ['odd', 'od', 'o'])
('bad', ['bad', 'ba', 'b'])
('time', ['time', 'tim', 'ti', 't'])
('meet', ['meet', 'mee', 'me', 'm'])
('dad', ['dad', 'da', 'd'])
('lamb', ['lamb', 'lam', 'la', 'l'])
('kangaroo', ['kangaroo', 'kangaro', 'kangar', 'kanga', 'kang', 'kan', 'ka', 'k'])
 
# суффиксы
('odd', ['odd', 'dd', 'd'])
('bad', ['bad', 'ad', 'd'])
('time', ['time', 'ime', 'me', 'e'])
('meet', ['meet', 'eet', 'et', 't'])
('dad', ['dad', 'ad', 'd'])
('lamb', ['lamb', 'amb', 'mb', 'b'])
('kangaroo', ['kangaroo', 'angaroo', 'ngaroo', 'garoo', 'aroo', 'roo', 'oo', 'o'])
 
# префиксы совпадающие с суффиксами
odd [('o', 'kangaroo')]
bad [('b', 'lamb')]
time [('t', 'meet')]
meet [('me', 'time')]
dad [('d', 'odd'), ('d', 'bad')]
lamb []
kangaroo []
 
# суффиксы совпадающие с префиксами
odd [('d', 'dad')]
bad [('d', 'dad')]
time [('me', 'meet')]
meet [('t', 'time')]
dad []
lamb [('b', 'bad')]
kangaroo [('o', 'odd')]

Для быстрого поиска наверное можно построить суффиксные и префиксные массивы.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@Андрей Рощупкин 2 / 2 / 0 Регистрация: 01.03.2016 Сообщений: 155

	Сжатие текста 17.02.2020, 23:37. Показов 2440. Ответов 12 Метки нет (Все метки) Добрейшего вечера всем) Задача: сшить N-ое количество строк так, чтобы в выходной строке минимальной длины можно было найти эти строки. Например из строк: wombat batman batch rabat bat должна получится rabatchwombatman На вход подаются число N и N слов, каждое в отдельной строке Реализация важна не обязательно на питоне 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	17.02.2020, 23:48
	Ограничения? 0

@Андрей Рощупкин 2 / 2 / 0 Регистрация: 01.03.2016 Сообщений: 155
	18.02.2020, 09:59 [ТС]
	Ограничений нет) 0

@Андрей Рощупкин 2 / 2 / 0 Регистрация: 01.03.2016 Сообщений: 155
	18.02.2020, 11:20 [ТС]
	Очень долго работает, когда слов больше 7 И работает не совсем правильно, некоторые слова обрезает( 0

Рыжий Лис Просто Лис 5973 / 3735 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	18.02.2020, 12:18
	Конечно, долго. Сложность всех перестановок O(N!) (факториал N). Хоть бы показали примеры, где слова неправильно обрезаются... 0

@Андрей Рощупкин 2 / 2 / 0 Регистрация: 01.03.2016 Сообщений: 155
	18.02.2020, 18:31 [ТС]
	odd bad time meet dad lamb kangaroo Самый короткий ответ по вашей программе lambadtimeetkangarodad Слово kangaroo обрезалось 0

@Андрей Рощупкин 2 / 2 / 0 Регистрация: 01.03.2016 Сообщений: 155
	18.02.2020, 19:19 [ТС]
	Просто твой код не совсем подходит, мне нужно обработать 1000 (на самом деле 797) слов) И такой программой это будет очень сложно сделать 0

Рыжий Лис Просто Лис 5973 / 3735 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	18.02.2020, 19:24
	На самом деле это похоже на NP-задачу. Если тебе нужно самое оптимальное решение - то нужно решать её только полным перебором O(N!). А вот если тебе нужно любое решение, близкое к оптимальному (но могут найтись решения, которые лучше. Или не найтись, если очень слишком повезёт) - нужно брать другие методы. Как вариант, могу предложить взять генетические алгоритмы для поиска решения. 0

@Андрей Рощупкин 2 / 2 / 0 Регистрация: 01.03.2016 Сообщений: 155
	18.02.2020, 19:30 [ТС]
	сейчас работаю над решением в лоб тройным вложеным циклом) 0

Рыжий Лис Просто Лис 5973 / 3735 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	18.02.2020, 19:32
	Спойлер: не поможет. Всего комбинаций перестановок слов: 797! (факториал 797). Среди них есть то самое решение, которое даст самую минимальную строку. В любом случае, у вас теперь есть правильно работающая функция для сжатия строки. 0