Какой нужен алгоритм, чтобы построить цепочку из нескольких слов? Например, шапка авто окно овал луза

Question

В цепочке каждая последняя буква текущего слова должна совпадать с первой буквой следующего. Необходимо использовать двунаправленный список. Пробовал использовать перебор всех слов, но он работает долго и после 12 слов виснет. Сейчас пробую считать первые и последние буквы всех слов, чтобы предсказать, можно ли вообще составить цепочку. Но далее не понятно, как выбирать слова.

Answer 1

Признак такого предложения это - сумма первых букв и сумма последних букв должны совпадать, а допустимое расхождение 2 непристроенных символа. пишешь первую проверку. Если возможно, то далее цыкл: условие выхода в массиве осталось 0 слов. Перебираешь слова, в случе если использовав слово "x" первым и количество букв оставшихся слов совпадает(с учетом, что для последней буквы слова х должна быть пара и конец предложения может остаться непарным) - добавляешь слово в предложение и убираешь его из анализируемого массива. Если после анализа последнего слова возможность не найдена - выводишь, что невозможно. Если цыкл отработал и не вывел отрицательного результата выводи переменную, в которую сбрасывал слова. Количество цыклов для N слов = N*(N+1)/2 (для PC это небольшое количество)

//синтаксис не везде правильный, но алгоритм понятен и решает задачу
//arr - массив слов

function possible(arr){
 n=count(arr);
 for (i=0; i<n;i++){
  sum[substr(arr[i],0,1)]+=1;//ключ массива=первый символ 
  sum[substr(arr[i],-1)]-=1;//ключ массива=последний символ
 }
 k=0;
 foreach ($arr as $key => $value){
  if($value!=0)k++;
  if(k>2) return false;
 }
 return true;
}

possible(arr);
while(count(arr)==0){
 foreach ($arr as $key => $value)
  arr_bofer=$arr;
  unset(arr_bofer[$key]);
  success=false;
  if(possible(arr_bofer)){
     str.=arr_bofer[$key].' '; 
     unset(arr_bofer[$key]);//уменьшаем массив в случае успешной проверки
     success=true;//
     break;
  }
  if(success==false){//если цыкл прошел, но не нашел варианта
     print('невозможно');
  }
}
print(str);//вывод предложения
}

Answer 2

Это задача о нахождении эйлерова пути в графе.
Вот здесь есть разбор задачи с домино - это практически то же самое (за исключением направленности)

БЛОГ НА HUSL

Какой нужен алгоритм, чтобы построить цепочку из нескольких слов? Например, шапка авто окно овал луза

Ответы (2 шт):