How to build a loop with multiple iteration of elements?

Question

Algorithms

Greetings
Task
Based on the first word, you need to rebuild the sentence in such a way that the first letter of each next word matches the previous letter of the previous word, and all other words that do not fit this rule should follow the sorted one according to the above algorithm.
Given a string:
a = 'pol xxx nog yyy len'
With pol as the first word, the sentence should in theory become: 'pol len nog xxx yyy'.
Until the end I can not understand how to implement it. The first stages seem to be clear:
1. convert the string into a list
2. run a loop for ... inwith the search for matches according to the conditions
3. add the found matches to a new line
This is where the difficulties begin. Well, we cycled through the list, added elements that matched the condition to the string, but with one pass of the cycle, the string takes on an unfinished form: 'pol len'.
4. You can remove the found matches from the list and add them to a new line, then the line will take the following form: 'pol len xxx nog yyy'. But the sequence of words in this period is not logically complete, the line should look like this: 'pol len nog xxx yyy'.
5. To complete the line in this example, you can add a second loop or use a loop with a while counter and set the counter to some value.
At this stage, too, difficulties with understanding. If the sentence is not known in advance, then it is impossible to set the number of iterations by eye. It is possible to set the number of iterations equal to the number of list elements, but I suspect that this is unreasonable and with a large number of sentences the whole process can be delayed.
Tell the correct or correct ways of solving this problem.

Answer 1

Look towards dynamic programming, algorithms with strings. Most likely, you need to create some kind of structure that stores key-value pairs. The key is some letter, the value is a list of owls starting with that letter. Next, build a matrix, for example, which determines which words can go one after another. This can be viewed as a directed graph. And there is already a search for the longest path in depth

Answer 2

Without thinking twice, a head-on solution (non-optimized):

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

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

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

It might be easier to search for words using a dict like this {'x' : 'xxx', 'y' : 'yyy'}. Then it will be easy to search for the desired word ( if last_letter in first_letter2word: ). You can also delete already added words from it.

Answer 4

I re-read the question and deleted my previous comment.
We cut the original string into two lists.
In the first, the first word of the string. In the second - all other words.
We write a function that goes through the second list in search of a suitable word.
If the word is found, we extract it from the second list and add it to the first one, after which we perform the pass again.
If not found, we glue the first list with the second and translate it into a string.

Answer 5

The program itself:

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

results:

>>> 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']