Вставлять (смешивать) элементы в массив на основе произвольных правил

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

Рассмотрим приложение, которое поддерживает набор телешоу и эпизодов для этих шоу. Пользователю разрешено ранжировать шоу (рейтинг, а не рейтинг, поэтому от 0 до n-1, где 0 — наивысший рейтинг).

Приложение предназначено для представления списка эпизодов на основе рейтинга шоу. В любой момент времени есть 0, 1 или 2 эпизода, которые приложение будет отображать в списке для каждого шоу (т. е. если пользователь посмотрел все эпизоды TheFooShow, в списке не будет ни одного эпизода; если у него есть 10 непросмотренных эпизодов TheBarShow, в списке появятся два). Эти эпизоды будут считаться primary и secondary.

Порядок эпизодов в списке должен максимально соответствовать некоторым правилам:

  • Основной выпуск шоу в списке должен стоять перед любыми выпусками шоу с более низким рейтингом.
  • Второстепенный эпизод шоу никогда не должен появляться перед основным эпизодом того же шоу.
  • По возможности никакие два эпизода шоу не должны находиться в пределах 4 позиций друг от друга.
  • Второстепенный эпизод шоу может появиться до того, как основной эпизод шоу будет оценен на семь или более позиций хуже.
  • и т.д

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

Примерный набор может быть (не строго следуя приведенным выше правилам): [0, 1, 3, 0', 3', 4, 5, 10, 4', 11, 11', 23]

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

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

Мне бы по существу хотелось такую ​​функцию, как:

- (int, int)indexesForEpisodesFromShow:(TVShow)aShow currentList:(List)aList

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

Мое текущее решение довольно примитивно и, как я уже сказал, работает только в определенных ситуациях. Я пробовал другие более сложные решения (читай: больше операторов if), но они, как правило, становятся очень хрупкими, и когда я добавляю дополнительную сложность для обработки крайних случаев, тесты начинают противоречить другим тестам.

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


arrays sorting algorithm ranking
person farski    schedule 10.12.2013    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Я думаю, все, что вам нужно, это функция для сравнения двух эпизодов.

Сначала сделаем некоторое предположение:

  • an object of episode has two properties:
    1. Show: The show object that a episode belongs to
    2. IsPrime: является ли эпизод первичным
  • and a show object has one property:
    1. Rank: The show's rank

А затем давайте создадим функцию, которая имеет два объекта эпизода в качестве входных параметров и возвращает:

  • -1: первый эпизод должен располагаться перед вторым эпизодом.
  • 0 : Два эпизода можно расположить в любом порядке.

  • 1 : Первый эпизод должен располагаться после второго эпизода.

    CompareEpisode(e1, e2)
{
  if(e1.IsPrime)
  {
    if(e2.IsPrime)
      return CompareSame(e1, e2);
    else
      return CompareDiff(e1, e2);
  }
  else
  {
    if(e2.IsPrime)
      return -CompareDiff(e2, e1);
    else
      return CompareSame(e1, e2);
  }
}

CompareSame(e1, e2)
{
  if(e1.Show.Rank < e2.Show.Rank)
    return -1;
  else if(e1.Show.Rank == e2.Show.Rank)
    return 0;
  else
    return 1;
}

CompareDiff(p, s)
{
  if(p.Show == s.Show)
    return -1;
  else
  {
    if(p.Show.Rank < s.Show.Rank + 7)
      return -1;
    else if(p.Show.Rank == s.Show.Rank + 7)
      return 0;
    else
      return 1;
  }
}

И теперь вы можете итераторировать список, сравнивать каждый элемент в списке с вставляемым эпизодом, используя CompareEpisode, находить первый элемент, чтобы CompareEpisode возвращал 0 или 1, вы можете вставить новый эпизод перед найденным элементом.

И если есть некоторые элементы, из-за которых CompareEpisode возвращает 0, у вас есть несколько позиций-кандидатов, вы можете выбрать одну, чтобы соответствовать правилу «поместить эпизоды из одного шоу как можно дальше».

person Yong Tiger    schedule 10.12.2013
comment
Это звучит как хороший подход. Я попробую и отчитаюсь. - person farski; 10.12.2013
comment
В коде ошибка, в else ветке внешнего if в CompareEpisode первый возврат должен быть return -CompareDiff(e2, e1);. - person Yong Tiger; 11.12.2013
comment
Проблема, с которой я столкнулся при таком подходе, заключается в соблюдении правил, связанных с соблюдением минимального расстояния между похожими эпизодами. Например, если я вставляю второстепенный эпизод для шоу, просматривая список, я передаю его и основной эпизод этому и возвращаю 1, но затем, когда я перехожу к следующему эпизоду, мне все еще нужно сделать осмотритесь в эпизодах, отличных от того, что было передано, чтобы увидеть, встречаю ли я этот мин. требование расстояния - person farski; 13.12.2013