Алгоритм Минимизируйте плейлист без изменения воспроизведения

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

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

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

Answer 2

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

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

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

Что представляет собой вариант на Abigail's awesome Perl regex to find prime numbers.

Answer 3

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

Ex:

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] 

Trying вышеописанную процедуру работает, потому что 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, не должно быть слишком сложно увидеть, как уменьшить исходный список до его основной формы.

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

Answer 4

Вот какой простой код, который должен работать в близком к линейном времени (в худшем случае 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).

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