Geek Answers Handbook

Algorithm Minimize playlist without changing playback

Im looking for an algorithm to shorten the list (playlist) of ordered but not unique elements. I was looking for set theory, but havent found anything suitable yet

Examples

[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.

The thought of getting all the existing sub-lists and counting each instance. If there is such a sublist where the countdown is when the length of the subword is equal to the original list, take the shortest sublist that matches these criteria.

It seems a little brute force, a simpler / faster solution should be available.

+5
source share
4 answers

- , , .

, , - :

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

Abigail awesome Perl regex .

+3

n <= N ( N - ), N N. , , N. , ( ). O(N^2), , .

, , , , 2 4 , , 4 . , , .

+2

.

:

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, , .

: - , , . , , , .

0

, ( 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).

* , , , , - .

0

More articles:


All Articles