Orchestrate Illusions (Superpermuter)
August 10, 2014 4:19 PM Subscribe
The Minimal Superpermutation Problem - Imagine that there is a TV series that you want to watch. The series consists of n episodes, with each episode on a single DVD. Unfortunately, however, the DVDs have become mixed up and the order of the episodes is in no way marked (and furthermore, the episodes of the TV show are not connected by any continuous storyline – there is no way to determine the order of the episodes just from watching them). Suppose that you want to watch the episodes of the TV series, consecutively, in the correct order. The question is: how many episodes must you watch in order to do this?
There's relatively written about these but one of the most interesting places you can read about them is in Magical Mathematics (that's a link to a very enjoyable interview about the book with Perci Diaconis, coauthor with Ron Graham).
There's relatively written about these but one of the most interesting places you can read about them is in Magical Mathematics (that's a link to a very enjoyable interview about the book with Perci Diaconis, coauthor with Ron Graham).
Okay, I've read about the problem further. (Again, not a mathy sort, so if this is completely obvious, apologies). The problem presupposes that there is some kind of "correct" order, right? But wouldn't it be impossible to ever reconstruct this order from a random jumble of numbers? And who would you ever be able to prove it?
posted by jokeefe at 4:45 PM on August 10, 2014 [1 favorite]
posted by jokeefe at 4:45 PM on August 10, 2014 [1 favorite]
One could as well ask how Kryptonite could weaken Superman. It's just a premise, the arguably interesting part is exploring the consequences of that premise.
A more common way to present a permutation problem would be that we have a combination lock, with a certain set of numbers on the dial, if we were really unlucky what would be the maximum number of combinations we would have to try before the lock opened.
posted by idiopath at 4:46 PM on August 10, 2014 [1 favorite]
A more common way to present a permutation problem would be that we have a combination lock, with a certain set of numbers on the dial, if we were really unlucky what would be the maximum number of combinations we would have to try before the lock opened.
posted by idiopath at 4:46 PM on August 10, 2014 [1 favorite]
Though, on reflection that's not an identical problem (unless the combination needed to use every number on the dial).
posted by idiopath at 4:56 PM on August 10, 2014 [1 favorite]
posted by idiopath at 4:56 PM on August 10, 2014 [1 favorite]
Let me see if I understand the problem. You watch episodes in every possible order a bunch of times. You will probably see many episodes many times. But somewhere in this string of watching there comes a series, say during viewings 300 thru (300+n), where you have watched the whole series in order, right?
In which case it's a little easier than the combination lock (for the viewer if not for the mathematician). Because in the case of the lock, you really have to enter the first number first, not just somewhere in a string of numbers.
I have absolutely nothing to add in the way of solving the problem, btw.
posted by selfmedicating at 4:56 PM on August 10, 2014 [1 favorite]
In which case it's a little easier than the combination lock (for the viewer if not for the mathematician). Because in the case of the lock, you really have to enter the first number first, not just somewhere in a string of numbers.
I have absolutely nothing to add in the way of solving the problem, btw.
posted by selfmedicating at 4:56 PM on August 10, 2014 [1 favorite]
Reminds me of this story by Jon Carroll, where he put a "books on tape" version of Dostoevsky's The Brothers Karamazov on his iPod, not realizing it was in shuffle mode.
posted by CheeseDigestsAll at 4:58 PM on August 10, 2014 [13 favorites]
posted by CheeseDigestsAll at 4:58 PM on August 10, 2014 [13 favorites]
Fascinating. What's not made clear in the article is what the practical application of this might be, if any.
posted by ob1quixote at 5:05 PM on August 10, 2014 [1 favorite]
posted by ob1quixote at 5:05 PM on August 10, 2014 [1 favorite]
Which is not to say it needs a practical application. That's just the first thing my engineer's mind thought of.
posted by ob1quixote at 5:06 PM on August 10, 2014 [1 favorite]
posted by ob1quixote at 5:06 PM on August 10, 2014 [1 favorite]
But somewhere in this string of watching there comes a series, say during viewings 300 thru (300+n), where you have watched the whole series in order, right?
And that number must be some huge (inhuman and infinite) multiple of the number of episodes, right? Like the monkeys typing Shakespeare.
Couldn't a computer do this? Or is the point to figure it out with human brains?
posted by jokeefe at 5:07 PM on August 10, 2014
And that number must be some huge (inhuman and infinite) multiple of the number of episodes, right? Like the monkeys typing Shakespeare.
Couldn't a computer do this? Or is the point to figure it out with human brains?
posted by jokeefe at 5:07 PM on August 10, 2014
But somewhere in this string of watching there comes a series, say during viewings 300 thru (300+n), where you have watched the whole series in order, right?
AND YOU WILL NEVER KNOW WHICH SET OF VIEWINGS IT WAS. HA HA.
posted by jokeefe at 5:09 PM on August 10, 2014 [4 favorites]
AND YOU WILL NEVER KNOW WHICH SET OF VIEWINGS IT WAS. HA HA.
posted by jokeefe at 5:09 PM on August 10, 2014 [4 favorites]
Fascinating. What's not made clear in the article is what the practical application of this might be, if any.
posted by ob1quixote at 1:05 AM on August 11
I've had to work out things like this to test the likelihood of random events occurring in a particular order in a computer game, and at which point they become so vanishingly small they'll never occur without you forcing it to occasionally.
So there's that at least.
posted by dng at 5:09 PM on August 10, 2014 [3 favorites]
posted by ob1quixote at 1:05 AM on August 11
I've had to work out things like this to test the likelihood of random events occurring in a particular order in a computer game, and at which point they become so vanishingly small they'll never occur without you forcing it to occasionally.
So there's that at least.
posted by dng at 5:09 PM on August 10, 2014 [3 favorites]
Well, the minimum number is the number of episodes. There's some chance you will guess right the very first try. The average number is higher than that, but not as high as watching every episode in every possible combination. What he's asking is the minimum number to guarantee you achieved the goal, without necessarily even knowing when you're done.
It's a neat solution, and smaller than I would have thought. How long a number string do you need to guarantee it contains somewhere in it every American's SSN?
posted by ctmf at 5:17 PM on August 10, 2014 [1 favorite]
It's a neat solution, and smaller than I would have thought. How long a number string do you need to guarantee it contains somewhere in it every American's SSN?
posted by ctmf at 5:17 PM on August 10, 2014 [1 favorite]
Wasn't Firefly shown like this when it first aired on Fox, almost in shuffle mode?
Jon Carroll is a gem.
posted by Jubal Kessler at 5:26 PM on August 10, 2014 [1 favorite]
Jon Carroll is a gem.
posted by Jubal Kessler at 5:26 PM on August 10, 2014 [1 favorite]
Did you mean to post this to FanFare? {/}
posted by benito.strauss at 5:36 PM on August 10, 2014
posted by benito.strauss at 5:36 PM on August 10, 2014
How long a number string do you need to guarantee it contains somewhere in it every American's SSN?
That problem is solved by a De Bruijn sequence on the set of digits {0,1,2,3,4,5,6,7,8,9}. Such a sequence would have length 10^9 and would contain every 9-digit string, including every valid SSN. (There are constraints on SSNs so not every 9-digit string is a SSN, but I have no idea what those constraints are). Constructing De Bruijn sequences is much easier than constructing minimal superpermutations.
The Uses section of the De Bruijn sequences article might give a hint about possible applications of this sort of thing.
posted by Wolfdog at 5:36 PM on August 10, 2014 [2 favorites]
That problem is solved by a De Bruijn sequence on the set of digits {0,1,2,3,4,5,6,7,8,9}. Such a sequence would have length 10^9 and would contain every 9-digit string, including every valid SSN. (There are constraints on SSNs so not every 9-digit string is a SSN, but I have no idea what those constraints are). Constructing De Bruijn sequences is much easier than constructing minimal superpermutations.
The Uses section of the De Bruijn sequences article might give a hint about possible applications of this sort of thing.
posted by Wolfdog at 5:36 PM on August 10, 2014 [2 favorites]
Hrm. This looks only slightly more difficult than trying to find the actual intended order of airing for the American Gothic DVDs.
posted by adipocere at 5:46 PM on August 10, 2014 [1 favorite]
posted by adipocere at 5:46 PM on August 10, 2014 [1 favorite]
That's easy: one. Just redefine what "correct order" means.
posted by blue_beetle at 6:37 PM on August 10, 2014
posted by blue_beetle at 6:37 PM on August 10, 2014
I heard this on Fresh Air once, but the viewer was Questlove and the TV show was "Soul Train".
posted by hwestiii at 6:49 PM on August 10, 2014 [1 favorite]
posted by hwestiii at 6:49 PM on August 10, 2014 [1 favorite]
"Couldn't a computer do this? Or is the point to figure it out with human brains?"
pedantically, of course, a computer can calculate the number. But some human programmer has to understand the problem precisely enough to be able to ask for that calculation. And the hard part here is not the arithmetic, it's precisely delimiting the problem so that you know which arithmetic to calculate.
posted by idiopath at 7:05 PM on August 10, 2014 [2 favorites]
pedantically, of course, a computer can calculate the number. But some human programmer has to understand the problem precisely enough to be able to ask for that calculation. And the hard part here is not the arithmetic, it's precisely delimiting the problem so that you know which arithmetic to calculate.
posted by idiopath at 7:05 PM on August 10, 2014 [2 favorites]
What's not made clear in the article is what the practical application of this might be, if any.
Some combination locks continually test whether the last N digits are the passcode, so entering a minimal sequence is much faster than doing every possible 4-digit code one at a time.
posted by Rangi at 7:40 PM on August 10, 2014 [5 favorites]
Some combination locks continually test whether the last N digits are the passcode, so entering a minimal sequence is much faster than doing every possible 4-digit code one at a time.
posted by Rangi at 7:40 PM on August 10, 2014 [5 favorites]
I would use delicate and highly scientific instrumentation to measure microchanges in the appearance of the primary cast members, to determine if they are older from one episode to the next.
I suspect that this will be difficult if Keanu Reeves or Sandra Bullock appear in any of the scenes, as they are evidently ageless.
posted by turbid dahlia at 7:55 PM on August 10, 2014 [1 favorite]
I suspect that this will be difficult if Keanu Reeves or Sandra Bullock appear in any of the scenes, as they are evidently ageless.
posted by turbid dahlia at 7:55 PM on August 10, 2014 [1 favorite]
Just watch one episode N times. I don't see why you have to use all that mathy stuff.
posted by mikurski at 8:06 PM on August 10, 2014
posted by mikurski at 8:06 PM on August 10, 2014
Look it up on tv tropes. Really, why make this so difficult =D Seriously though, this type of math is always intruiging to me.
posted by AngelWuff at 10:45 PM on August 10, 2014
posted by AngelWuff at 10:45 PM on August 10, 2014
Just spitballing, but protein sequencing.
posted by victory_laser at 11:04 PM on August 10, 2014 [1 favorite]
posted by victory_laser at 11:04 PM on August 10, 2014 [1 favorite]
Snarky answer #1: All of them!
Snarky answer #2: If you did watch them all in order, how would you know?
The "correct" answer (as described in the referenced article) depends on how you choose the next DVD:
If you put each dvd back in the pile after you watch it, or you otherwise randomly pick the next dvd to watch, there is no minimum number of episodes you must watch to guarantee that you will eventually watch them all in the correct order.
If you track which dvd is which, and are careful to never watch all of them in the same order twice, only then do you get the Minimal Superpermutation Problem.
posted by Jefffurry at 12:20 AM on August 11, 2014
Snarky answer #2: If you did watch them all in order, how would you know?
The "correct" answer (as described in the referenced article) depends on how you choose the next DVD:
If you put each dvd back in the pile after you watch it, or you otherwise randomly pick the next dvd to watch, there is no minimum number of episodes you must watch to guarantee that you will eventually watch them all in the correct order.
If you track which dvd is which, and are careful to never watch all of them in the same order twice, only then do you get the Minimal Superpermutation Problem.
posted by Jefffurry at 12:20 AM on August 11, 2014
Oh, the snarky answers have come out? \o/
The interesting question is: how many episodes must you watch to watch all possible fan-derived Machete Orders of this series in addition to this hypothetical correct one?
posted by Earthtopus at 12:26 AM on August 11, 2014
The interesting question is: how many episodes must you watch to watch all possible fan-derived Machete Orders of this series in addition to this hypothetical correct one?
posted by Earthtopus at 12:26 AM on August 11, 2014
Some combination locks continually test whether the last N digits are the passcode, so entering a minimal sequence is much faster than doing every possible 4-digit code one at a time.
It seems like this is a slightly different problem, since a number can be repeated in a passcode, eg. 0000 -- in the article (as far as I understand) each value appears in the "correct" pattern only once.
posted by bjrubble at 5:04 AM on August 11, 2014
It seems like this is a slightly different problem, since a number can be repeated in a passcode, eg. 0000 -- in the article (as far as I understand) each value appears in the "correct" pattern only once.
posted by bjrubble at 5:04 AM on August 11, 2014
The cartilage in ears and noses never stops growing, and earlobes elongate due to gravity sag. Build a sensitive image geometry estimator and sort on those values.
posted by StickyCarpet at 5:53 AM on August 11, 2014
posted by StickyCarpet at 5:53 AM on August 11, 2014
Well the number of permutations is n!, right? So to be absolutely certain you've seen the whole series in the right order, you'd have to watch each of those n! permutations, so the total number of episodes would be n!*n.
For the first series of Sherlock to keep it simple, there would be six possible orders of the three episodes, so you'd have to watch 18 episodes to be sure you'd gotten them in the right order.
Maybe I should actually read TFA, but unless I'm missing something, that's not a terribly complicated question, is it?
posted by Naberius at 6:22 AM on August 11, 2014
For the first series of Sherlock to keep it simple, there would be six possible orders of the three episodes, so you'd have to watch 18 episodes to be sure you'd gotten them in the right order.
Maybe I should actually read TFA, but unless I'm missing something, that's not a terribly complicated question, is it?
posted by Naberius at 6:22 AM on August 11, 2014
Naberius: no, it's less than that. Suppose there are two episodes, named A and B. You only have to watch three episodes (not n!*n=4) to make sure you have done the correct sequence: watch ABA. The last episodes in one sequence can count as the first episodes in the next.
posted by bleston hamilton station at 6:41 AM on August 11, 2014
posted by bleston hamilton station at 6:41 AM on August 11, 2014
Haaven't read the article yet (shame!), but I'm pretty sure the answer is Debrujin sequences. They come with a card trick.
posted by kaibutsu at 7:21 AM on August 11, 2014
posted by kaibutsu at 7:21 AM on August 11, 2014
wait, the answer isn't 1/e ? Dang.
(It's like the hat-check problem, or best-pick problem, in some ways..)
posted by k5.user at 8:25 AM on August 11, 2014
(It's like the hat-check problem, or best-pick problem, in some ways..)
posted by k5.user at 8:25 AM on August 11, 2014
« Older Martin Solveig - Defected In The House | "Does this bulletproof jacket make me look fat?"... Newer »
This thread has been archived and is closed to new comments
So.... why would you care about watching them in chronological order, then? I mean, in this case, there is no "correct" order. [/not a mathy person]
posted by jokeefe at 4:40 PM on August 10, 2014 [4 favorites]