zhut
Авг. 8, 2013 12:29:43
Помогите решить следующую задачу.
Дан большой текст более 1000 слов, необходимо из слов этого текста составить палиндром как можно большей длины, каждое слово в палиндроме должно встречаться только 1 раз. Слова из текста я извлек в массив, а как из них составить палиндром ума не приложу. Всё упирается в кучу циклов, считать которые никакого времени не хватит
Буду благодарен за любые идеи в помощи решения этой задачи.
Singularity
Авг. 8, 2013 15:10:11
Покажите код.
zhut
Авг. 8, 2013 16:32:39
Я пока не могу понять алгоритм, был бы алгоритм, а с кодом я думаю справится смог бы.
Я думаю, что нужно будет создать 2 списка, в котором слова будут образовывать строки, левую и правую часть палиндрома. А вот как заполнить эти списки, не знаю, простым перебором всех возможных комбинаций нереально, вот и хочу спросить, может кто знает какой нибудь алгоритм по которому выбираются слова из которых можно составить палиндром.
Singularity
Авг. 8, 2013 16:57:42
from collections import deque
l = ['adc','arc','cda','rtt','ttr','gfdgd']
res = deque(list())
for x in l:
for y in l:
if x == y[::-1]:
res.appendleft(x)
res.append(y)
print [ x for x in res]
Это в лоб.
Можно оптимизировать количество разворачиваний строк
sergeek
Авг. 8, 2013 20:53:52
полным перебором тут и из 20-ти слов не вычислить
sergeek
Авг. 8, 2013 21:18:32
есть входной файл с ответом?
py.user.next
Авг. 8, 2013 22:04:58
нужно строить по словам от концов последовательности слов к её центру
опять олимпиадная задачка, походу (бессмысленная и отнимающая время)
FishHook
Авг. 9, 2013 06:48:58
Singularity
Это в лоб.
Можно оптимизировать количество разворачиваний строк
Не работает
from collections import deque
l = ['лазер','боре','хер','обрезал']
res = deque(list())
for x in l:
for y in l:
if x == y[::-1]:
res.appendleft(x)
res.append(y)
print [ x for x in res]
zhut
Авг. 9, 2013 09:48:14
В лоб решение у меня такое
# -*- coding: utf-8 -*-
f=open('file')
string=f.read().split('\n') # Слова уже все извлек в файл 1 строка одно слово
s1=[]
s2=[]
for i in string:
for x in string:
if i == x[::-1] and i!=x and i not in s1 and i not in s2 and x not in s1 and x not in s2:
s1.append(i)
s2.append(x)
print s1
print s2[::-1]
Но это малая часть палиндрома получается.
zhut
Авг. 9, 2013 09:51:54
sergeek
есть входной файл с ответом?
Файла нет с ответом, просто задание, палиндром должен быть как можно длиннее