Алгоритм Минимизация списка воспроизведения без изменения воспроизведения

Question

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

Примеры

[a, b, b, c] -> [a, b, b, c] Cannot be reduced. 
[a, b, b, a, b, b] -> [a, b, b]. 
[b, b, b, b, b] -> [b]. 
[b, b, b, b, a] -> [b, b, b, b, a] Cannot be reduced. 

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

Это кажется немного грубой силой, должно быть доступно более простое / быстрое решение.

Answer 1

Для начала вам не нужно проверять все подсписки - только те, длина которых равна коэффициентам длины полного списка.

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

/^(.+?)\1+$/

Какой вариант в Удивительное регулярное выражение Abigail для поиска простых чисел .

Answer 2

Для каждого n <= N (где N - длина списка), если n - это коэффициент N.Если это так, то проверьте, генерирует ли повторный подсписок первых n символов исходный список.Если это так, то вы нашли потенциальный ответ (ответ самый короткий).Это должно привести вас к менее чем O(N^2), но в том же порядке эффективности, что и грубая сила в худшем случае.

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

Answer 3

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

f(x) {
  i = 1;
  while (i <= size(x) / 2) {
    if (size(x) % i != 0) { i++; continue;}
    b = true;
    for (j = 0; j + i < x.size(); j++) {
      if (x[i] != x[j]) {
        b = false;
        break;
      }
    }
    if (b) return i;
    i = max(i + 1, j / i * i / 2); // skip some values of i if j is large enough
  }
  return -1;
}

По сути, вышеприведенное выполняет наивный алгоритм, но пропускает некоторые периодичности, которые, как известно, невозможны из-за более ранних "промахов". Например, если вы попробуете период 5 и увидите «aaaabaaaabaaaabaaaabab», вы можете спокойно пропустить 6, 7, ..., 10, поскольку мы увидели 4 повторения цикла из 5, а затем сбой.

В конечном итоге вы выполняете линейный объем работы плюс объем работы, который является линейным по сигме (n), сумме делителей n, которая ограничена O (n lg lg n).

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

Answer 4

Кодируйте каждый элемент набора простым числом.

Пример:

a -> 2
b -> 3
c -> 5

и т. Д.

Теперь вам нужно сохранить еще два списка.

Первый список для простых чисел, второй для их показателей.

Идея такова;когда вы наткнетесь на элемент, запишите его простое число и сколько раз подряд он появится.

Для [a, b, b, c] вы получите:

[2, 3, 3, 5]

Что можно записать как:

[2, 3^2, 5]

или, точнее:

[2^1, 3^2, 5^1]

, и вы поддерживаете два списка:

[2,3,5]  // primes in succession - list [p]
[1,2,1]  // exponents - list [e]

Теперь вы перебираете эти два списка от конца до серединыпроверяя, совпадает ли первый элемент [p] ^ [e] с последним элементом;если это так, то второй с последним, последним и т. д. Если все они одинаковы, ваш список можно уменьшить.

В этом примере вы проверяете, если 2^1*5^1 == 3^2*3^2;и поскольку это не так, его нельзя уменьшить.

Давайте попробуем [a, b, b, a, b, b]:

Это кодируется как

[2^1, 3^2, 2^1, 3^2]

или

[2, 3, 2, 3]  // primes
[1, 2, 1, 2]  // exponents

Теперь мы проверяем, если 2^1 * 3^2 == 3^2 * 2^1 (первое простое число, первый показатель степени умножено на последнее простое число, последний показатель степени, а затем сравнивается со вторым числом относительно следующего за последним)

Так как это имеет место, оно сводимо.*

Давайте попробуем [b, b, b, b, b]:

Это может быть закодировано как

[3^5]

или

[3]  // primes
[5]  // exponents

Это особый случай: если вы 'у нас есть списки из 1 элемента, тогда ваш исходный список можно привести.

Давайте попробуем [b, b, b, b, a]:

Это может быть закодировано как

[3^4, 2^1]

или,

[3, 2]  // primes
[4, 1]  // exponents

Мы проверяем, если 3^4 == 2^1, а поскольку это не так, ваш список не сводится.

Давайте попробуем [a, b, a, b, a, b]:

Это может быть закодировано как

[2^1, 3^1, 2^1, 3^1, 2^1, 3^1]

или

[2, 3, 2, 3, 2, 3]
[1, 1, 1, 1, 1, 1]

Попытка описанной выше процедуры работает, потому что 2^1 * 3^1 == 3^1 * 2^1 == 2^1 * 3^1

Итак, алгоритм будет выглядеть примерно так:

---

Кодировать все числа в простые числа.

ИтерацияПросмотрите список, составьте два списка и заполните их, как описано

Теперь, когда у вас есть два списка, p и e, оба из которых имеют длину n, сделайте следующее:

var start = p[0]^e[0] * p[n-1]^e[n-1]
var reducible = true;

for (int i = 0; i < n/2, ++i) :
   if ( (p[i]^e[i] * p[n-i]^e[n-i]) != start ) :
       reducible = false;
       break;

---

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

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