Member 12676879 Ответов: 1

Определение возможности заказа

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

Для бывших :
Человека 1 : В7, В8, В1, В9
Лицо2 : В8, В9, В2
Person3 : В2, В10

** Теперь наша роль состоит в том, чтобы определить, возможны ли все вышеперечисленные заказы**

Для бывших :
Персона 1 : W7, W8
Персона 2 : W8, W9, W10
Person3 : В10, В7

Теперь вышеуказанный заказ невозможен, потому что в соответствии с person1 - W7 идет перед W8. Акк Лицо2 : В8 доходит до В10. Это означает, что W7 предшествует W10. Но это противоречит Person3, который говорит, что W7 идет после W10


Чего я хочу ?

Мне не нужен код, но некоторая помощь относительно того, как подойти к этому вопросу

Что я уже пробовал:

Я много думал об этом. Но, честно говоря, не смог придумать четкого решения!

Я подумал, что мы могли бы вести список для каждого слова слов, которые идут после него и перед ним. Но поддерживать и обновлять такой список слишком тяжело !

1 Ответов

Рейтинг:
2

CPallini

Рассмотрим последовательность, например
W7,W8,W1,W9
Любой предмет имеет предыдущие пункты так же как следующие предметы.
Например W8 имеет

  • предыдущие пункты {W7}
  • следующие предметы {W1,W9}

Пожалуйста, обратите внимание, либо предшествующий вещи или следующие предметы может быть, пустой набор.

Теперь вы можете сравнить две последовательности (скажем, последовательность A и B): для каждого элемента последовательности A у вас может быть два случая:
  1. Вы не находите один и тот же предмет в последовательности B
  2. Вы находите один и тот же предмет в последовательности B


В случае 1 несоответствия нет, и вы можете перейти к следующему пункту последовательности A.

В случае 2 вы должны убедиться, что любой предмет в предыдущие пункты последовательности A не может быть найден в следующие предметы последовательности B (и наоборот: любой предмет в следующие предметы последовательности A не может быть найден в предыдущие пункты последовательности BЕсли это не так, то существует несоответствие, и эти две последовательности несовместимый.

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

Я думаю, что это не умный алгоритм, однако он может работать.

Maciej Los

Отличное объяснение!
А5!

CPallini

Надеюсь, это сработает.
Спасибо!