Python-сообщество

Помогите решить следующую задачу.
Дан большой текст более 1000 слов, необходимо из слов этого текста составить палиндром как можно большей длины, каждое слово в палиндроме должно встречаться только 1 раз. Слова из текста я извлек в массив, а как из них составить палиндром ума не приложу. Всё упирается в кучу циклов, считать которые никакого времени не хватит
Буду благодарен за любые идеи в помощи решения этой задачи.

Покажите код.

Я пока не могу понять алгоритм, был бы алгоритм, а с кодом я думаю справится смог бы.
Я думаю, что нужно будет создать 2 списка, в котором слова будут образовывать строки, левую и правую часть палиндрома. А вот как заполнить эти списки, не знаю, простым перебором всех возможных комбинаций нереально, вот и хочу спросить, может кто знает какой нибудь алгоритм по которому выбираются слова из которых можно составить палиндром.

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] 

Отредактировано Singularity (Авг. 8, 2013 17:00:33)

полным перебором тут и из 20-ти слов не вычислить

есть входной файл с ответом?

нужно строить по словам от концов последовательности слов к её центру
опять олимпиадная задачка, походу (бессмысленная и отнимающая время)

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]

[]

В лоб решение у меня такое

# -*- 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:49:00)

sergeek
есть входной файл с ответом?