Как построить цикл при множественном переборе элементов?

Question

[weranda]

Приветствую

Задача
На основе первого слова нужно перестроить предложение таким образом, чтобы первая буква каждого следующего слова совпадала с предыдущей буквой предыдущего слова, а все остальные слова, которые не подходят под это правило должны идти за отсортированным по заданному выше алгоритму.

Дана строка:
a = 'pol xxx nog yyy len'

Имея в качестве первого слова pol, предложение по идее должно превратиться в: 'pol len nog xxx yyy'.

До конца не могу понять как это реализовать. Первые этапы вроде понятны:
1. преобразуем строку в список
2. запускаем цикл for ... in с поиском совпадений по условиям
3. найденные совпадения добавляем в новую строку

Вот в этом месте начинаются сложности. Ну прошлись мы циклом по списку, ну добавили подходящие по условию элементы в строку, но при одном проходе цикла строка принимает незаконченный вид: 'pol len'.

4. Можно удалить найденные совпадения из списка и добавить их к новой строке, тогда строка примет следующий вид: 'pol len xxx nog yyy'. Но последовательность слов в этой сроке не является логически завершенной, строка должна иметь такой вид: 'pol len nog xxx yyy'.

5. Чтобы строка приобрела законченный вид в данном примере, можно добавить второй цикл или применить цикл со счетчиком типа while и задать счетчику какое-то значение.

На этом этапе тоже сложности с пониманием. Если предложение заранее не известно, то нельзя же задать количество итераций на глаз. Можно установить количество итераций равное количеству элементов списка, но подозреваю, что это неразумно и при большом количестве предложений весь процесс может затянуться.

Поведайте правильный или правильные пути решения этой задачи.

Answer 1

[Hakito]

Смотрите в сторону динамического программирования, алгоритмы со строками. Скорее всего нужно завести какую-то структуру, хранящую пары ключ-значение. Ключ - какая-то буква, значение - список сов начинающихся с этой буквы. Дальше строите матрицу, например которая определяет, какие слова могут идти одно за другим. Это можно будет рассматривать как ориентированный граф. А там уже поиск максимально длинного пути в глубину

Answer 2

[Антон Федорян]

Недолго думая решение в лоб (неоптимизированное):

a = 'len asd sas nas sda orr' # исходная строка
x = a.split(' ') # формируем из нее массив
r.append(x[0]) # берем первый элемент с которого начнем
del x[0] # удаляем чтобы не мешал
while (len(x) > 0): # пока исходный массив не пустой
	z = False # проверка на то, что слово начинается с последней буквы предыдущего слова
	for i in x:
		if (i[0] == r[-1][-1]): # если начинается, то добавляем в массив
			r.append(i)
			del x[x.index(i)]
			z = True
			break
	if (not z): # если слово не найдено, то дописываем оставшиеся
		r.extend(x)
		x = []

r
>>> ['len', 'nas', 'sas', 'sda', 'asd', 'orr']

Answer 3

[tsarevfs]

word_list = input_string.split(' ') 
while <в word_list есть слово начинающееся с нужной буквы>:
   добавить это слово в конец результата
   убрать добавленное слово из word_list

отсортировать оставшиеся в word_list слова
добавить их в ответ

Возможно проще для поиска слов использовать dict такого вида {'x' : 'xxx', 'y' : 'yyy'}. Тогда искать нужное слово будет просто ( if last_letter in first_letter2word: ). Из него так же можно удалять уже добавленные слова.

Answer 4

[Александр]

Перечитал вопрос у удалил свой предыдущий коммент.

Режем исходную строку на два списка.
В первом - первое слово строки. Во втором - все остальные слова.

Пишем функцию, которая проходится по второму списку в поисках подходящего слова.
Если слово нашлось - извлекаем из второго списка и добавляем в первый, после чего выполняем проход ещё раз.
Если не нашлось - склеиваем первый список со вторым и переводим в строку.

Answer 5

[Владимир Куц]

Сама программа:

str1 = 'pol xxx nog yyy len'
mass = [x for x in str1.split(' ')]
res = []
res.append(mass.pop(0))
out = filter(lambda x: x[0]==res[-1][-1], mass)
while len(out)!=0:
     res.append(out[0])
     mass.pop(mass.index(out[0]))
     out = filter(lambda x: x[0]==res[-1][-1], mass)
res += mass
print res

результаты:

>>> str1 = 'pol xxx nog yyy len'
>>> mass = [x for x in str1.split(' ')]
>>> res = []
>>> res.append(mass.pop(0))
>>> out = filter(lambda x: x[0]==res[-1][-1], mass)
>>> while len(out)!=0:
...     res.append(out[0])
...     mass.pop(mass.index(out[0]))
...     out = filter(lambda x: x[0]==res[-1][-1], mass)
... 
'len'
'nog'
>>> res
['pol', 'len', 'nog']
>>> mass
['xxx', 'yyy']
>>> res += mass
>>> res
['pol', 'len', 'nog', 'xxx', 'yyy']