[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

View post   
File: 9 KB, 246x251, 1315886953647s.jpg [View same] [iqdb] [saucenao] [google]
4728181 No.4728181 [Reply] [Original]

What is the shortest sequence that contains all permutations of the episodes of an n-episode series?

The permutations are allowed to overlap but must be continuous. For example, if there were 3 episodes, watching (1, 2, 3, 2, 1) would count as seeing orders (1, 2, 3) and (3, 2, 1) but not (2, 3, 1).

Prove your solution is optimal.

>> No.4728198

I seem to remember the obvious lower bound of n!+n-1 actually being achievable in all cases, but I don't have a proof at the ready.

>> No.4728197

http://garden.irmacs.sfu.ca/?q=op/smallest_universal_supersequence

>> No.4728200

I'm working on it.

>> No.4728201
File: 90 KB, 1000x1024, Kurisu Template.jpg [View same] [iqdb] [saucenao] [google]
4728201

I'm here to look at your /sci/ guide on maths, but seeing Kurisu is always interesting. At first I thought it was 14! but I reread it again and it clearly says to find a sequence. I don't know if my knowledge is sufficient.

Have some bigger template.

>> No.4728205

>>4728198
It would be great if we could see an example for n = 3.

>> No.4728207

>>4728197
My mistake, I misread the problem.

See http://math.stackexchange.com/questions/15510/what-is-the-shortest-string-that-contains-all-permutat
ions-of-an-alphabet

>> No.4728209

hurr durr

import itertools

def costToAdd(a, b):
for i in range(1, len(b)):
if a.endswith(b[:-i]):
return i
return len(b)

def stringContainingAllPermutationsOf(s):
perms = set(''.join(tpl) for tpl in itertools.permutations(s))
perms.remove(s)
a = s
while perms:
cost, next = min((costToAdd(a, x), x) for x in perms)
perms.remove(next)
a += next[-cost:]
return a

>> No.4728211

>>4728205
Huh, trying it makes it quite obvious that it isn't possible for n=3. Looks like I misremembered then.

>> No.4728217

>>4728205
1, 2, 3, 1, 2, 1, 3, 2, 1 is known to be optimal for n=3.

>> No.4728219

>>4728198
Now that I look at it I don't believe this is possible. It would have to start with a sequence of n - 1 elements, which would contain zero permutations, and each element added would add a new permutation.
If each element adds a new permutation, then since a permutation of n elements contains each element exactly once, each next element would have to be distinct from n-1 elements before it. By calling the first two episodes of a three episode series 1 and 2, this sequence would be:
1-2-3-1-2-3-1-2-...
Which does not contain all permutations. By "cheating" and watching a different as the permutation "1-2-3" is about to repeated gives:
1-2-3-1-2-1-3-2-1
This sequence contains every permutation, but is one element longer than the lower bound predicted by anon.
I'm still wrapping my head around it later, this seems like a good exercise.

>> No.4728234

The answer was <span class="math">\sum_{i=1}^n n![/spoiler] I believe. Proving it is another story, of course.

>> No.4728235

The optimal sequence is a palindrome.

1

1 - 2 - 1

1 - 2 - 3 - 1-2-1-3-2-1

1-2-3-4-1-2-3-1-4-2-3-1-2-4-3-1-2-1-3-4-2-1-3-2-4-1-3-2-1-4-3-2-1

>> No.4728237

>>4728235
Prove it. Even if you do prove that there is a palindrome sequence of optimal length, that doesn't mean there aren't also optimal sequences that are not palindromes.

>> No.4728240

1, 3, 9, 33, ...
I have an algorithm.
It's hard to explain though.
Let me get my thoughts together.

>> No.4728247

>>4728240
Probably what is described in the stackexchange link.
Anyway, the hard part is proving that that is in fact optimal

>> No.4728256

This is fucking with my mind. I want to figure it out.

>> No.4728258

First thought: n!+n-1 is a loose lower bound.

You must start by watching n to watch one permutation, and each additional episode adds at most one permutation.

Second thought: for n=2, this is achievable, but for n=3, the lower bound is 8, but there is no shorter sequence than 9.

>> No.4728273

Fuck this.

I'll just be a stripper.

>> No.4728283

<span class="math">n^2-n+1[/spoiler] episodes

If <span class="math">n=14[/spoiler], he will have to watch 183 episodes

>> No.4728292

>>4728283
Please make you sure you understand the problem before you imply all the other /sci/bros are stupid. You're feeble mind could not even begin to compute this answer.

>> No.4728300

>>4728292
>You're feeble mind could not even begin to compute this answer.

>> No.4728327
File: 662 KB, 1280x720, FuturamaTheorem.png [View same] [iqdb] [saucenao] [google]
4728327

Does anybody have enough of a background in permutation group theory, to tackle this problem in a group theory way? Pic related somewhat, it's from Futurama.

>> No.4728363

There is no point in watching the original 14 Haruhi episodes in every possible order.

Watching the first seven Endless Eight episodes in every possible order, before the last one once, on the other hand...

Well, really, you should do the whole 15,532 times, but if you can't quite spend the entire year doing it, 5,914 is the next best thing.

>> No.4728395

>>4728363
Really, you could be satisfied with watching the first one once, 2-7 in every possible order, and the last once, for a nice round 875 episodes.

Good way to spend a month.

>> No.4728407

http://oeis.org/A001930

>A001930

>> No.4729828

Don't be so easily convinced sum-of-factorials is optimal. It's only been tested up to fairly small n (something like 5 or 6), and at that point, the structure of the solutions is already changing; n=5 has two solutions that begin with 12345 for example. It's likely a good search algorithm could find a counterexample.

>> No.4729989

(n^2 - n)/2
91

>> No.4729996

2 because those are all the episodes I watched.