4 ms·

Apologies if this sounds dumb. But isn't P(n) = n! In this case, n=14 (episodes), which translates to factorial(14) = 87178291200. Which covers every possible a

• krackers 8y ago
  That's the number of permutations. But we are allowing overlaps by a shifted window so the number can be lower. It's easier to explain with an example - in the article there's a nice diagram.
• aaaaaaaaaab 8y ago
  n - 1 + n! <= P(n) < n * n! The lower bound is achieved when the permutations overlap perfectly, e.g. when n = 2: 1, 2, 1 The upper bound is simply the concatenation of all permutations. You can get lower than this by exploiting the fact that some permutations' suffixes are other permutations' prefixes.
• FabHK 8y ago
  Yes, so there are n! = 87,178,291,200 different permutations of those 14 sequences. You want to watch the 14 episodes in every possible order, ie in each of those permutations. You could just watch all of those permutations consecutively, for n x n! episodes in sequence, which would be 1,220,496,076,800 episodes (or, well, 14 episodes per permutation). However, you can do much better, exploiting overlap, using only 93,884,313,611 episodes, which is really quite remarkable, because it is just 1.08 episodes per permutation. Example with 3 (from the article): 3! = 6 permutations Bad way to watch all: concatenate all permutations A) 123 132 213 231 312 321 (= 3*6 = 18 episodes, or 3 episodes per permutation) Good way to watch all permutations: B) 123121321 (= 9 episodes, or 1.5 episodes per permutation) Note that each of the permutations above in A is contained in the string at B).
  • 0xFFFE 8y ago
    Ah, I see it now. Thank you for explaining it.