4 ms·

Can someone motivate the problem for me? Why isn't the answer just 14! ?

defrost 3y ago
If you watch the 3 episode series Example in the order 1 2 3 you have seen all the series episodes in one order. If you watch the episode sequence 1 2 3 1 you have now seen the series in two orders by watching a sequence of 4 episodes.
jfoutz 3y ago
overlaps. I wanna say it's a de Bruijn sequence. > 2! is > 1, 2 then > 2, 1 but you can skip an episode, and hit all permutations with > 1, 2, 1
anonymoushn 3y ago
The question is what's the shortest sequence that contains every permutation as a substring. If each episode after the 14th got you a new permutation, you would need 13+14!, but that's not possible. For example with 3 episodes, you could begin 12312, then any episode you choose from that position does not contribute a permutation. I think the shortest sequence goes 123121321.
quickthrower2 3y ago
> If a television series has just three episodes, there are six possible orders in which to view them: 123, 132, 213, 231, 312 and 321. You could string these six sequences together to give a list of 18 episodes that includes every ordering, but there’s a much more efficient way to do it: 123121321.
- tromp 3y ago
  And with 7 substrings of length 3, it's provably minimal, since making every 3-substring a permutation of 123 forces every element after the first 2. Assuming without loss of generality that it starts with 1 2, it is forced to start with 1 2 3 1 2 3 but there already repeats the same permutation. So one substring must be wasted (in the article this is phrased as having to traverse one higher cost edge in the corresponding graph).
- fsckboy 3y ago
  that ...,1,2,1,.. in the middle bothers me, nobody wants to watch three in a row that does not include all three, i'd rather have a duplicate triplet, or at least include the case as another potential bound, or classes of orderings where perhaps some numbers of elements have these defects while others don't.
abetusk 3y ago
The article doesn't do a good job of explaining the constraint. The sequence being generated is called a superpermutation [0]. From the Wikipedia article: """ ...a superpermutation on n symbols is a string that contains each permutation of n symbols as a substring. """ In other words, construct a big long string made up of the N symbols where every permutation of the N symbols appears in it. Since there's the possibility of overlaps, you can do better than the naive method of just pasting all N! permutations together. Note that this sounds very similar to a De Brujn sequence [1] but is different since a De Bruijn sequence ask for every possible sequence of N symbols (of length M, say), not every possible permutation. So a De Bruijn sequence would have 000, 001, 002, ... 200, 201, ... , 222 in it whereas a superpermutation would exclude (or at least not count) some of those sequences as they're not permutations (012, 021, 102, 120, 201, 210). [0] https://en.wikipedia.org/wiki/Superpermutation https://en.wikipedia.org/wiki/Superpermutation [1] https://en.wikipedia.org/wiki/De_Bruijn_sequence https://en.wikipedia.org/wiki/De_Bruijn_sequence EDIT: links (de bruijn)
- beardyw 3y ago
  Ah, thanks. I was going to bring that up, but hadn't spotted the difference.
- bumby 3y ago
  Is a superpermuation just a more efficient annotation or is it more helpful in solving an optimization problem? They talk about the travelling salesman problem in the article but they don't exactly explain if knowing the superpermutation helps solve it faster.
  - abetusk 3y ago
    I'm no expert but here are my opinions: One goal is to find an 'efficient' annotation of a superposition. That is, "what is the minimum superpermutation string length of of N symbols", which itself is a sort of optimization problem. We can presumably get bounds on the minimum and maximum it can be and maybe the 'optimal' shortest superpermutation has enough variation that the bounds aren't/can't be exact. As to what "practical" applications superpermutations have, nothing comes to mind but considering how many applications de Bruijn sequences show up, I'd be surprised if they didn't start cropping up from time to time in the future. As to the travelling salesman/Hamiltonian path/cycle problem, my impression is that they used a clever construction of a Hamiltonian cycle on a hyper-cube/Cayley graph/high-dimensional-high-degree graph to show lower/upper bounds on the number of superpermutations. In other words, the implication is the other way. They construct a Hamiltonian cycle on a specially crafted graph to show lower/upper bounds rather than use superpermutations to say anything about Hamiltonian cycles. To get a flavor for how this works, I'll copy pasta the de Bruijn "construction" section of Wikipedia [0]: """ The de Bruijn sequences can be constructed by taking a Hamiltonian path of an n-dimensional de Bruijn graph over k symbols (or equivalently, an Eulerian cycle of an (n − 1)-dimensional de Bruijn graph). """ With a de Bruijn graph [1] being a specialized graph construction. [0] https://en.wikipedia.org/wiki/De_Bruijn_sequence#Construction https://en.wikipedia.org/wiki/De_Bruijn_sequence#Constructio... [1] https://en.wikipedia.org/wiki/De_Bruijn_graph https://en.wikipedia.org/wiki/De_Bruijn_graph
plant-ian 3y ago
I think they mean if say there were episodes a, b and c the orders to watch would be abc, bac, cba, acb, cab, bca. Now if you watched abcba you'd experience both orders abc and cba but only watch 5 episodes in a row instead of 6. So what is the minimum number of episodes to watch in a row to experience all six different orders?
psyklic 3y ago
You can interleave the orderings. If there are two episodes (1 and 2), we only have to watch three episodes in a row: 121. Then, we've watched all permutations -- 12 and 21. The "14!" solution (where we watch 14x14! episodes) means there is no interleaving -- we just watch each permutation in turn. In our 2-episode example, we'd have to watch one extra episode (for a total of 2x2! = 4), e.g. in the order 1221.

If you watch the 3 episode series Example in the order 1 2 3 you have seen all the series episodes in one order. If you watch the episode sequence 1 2 3 1 you have now seen the series in two orders by watching a sequence of 4 episodes.

jfoutz 3y ago

overlaps. I wanna say it's a de Bruijn sequence. > 2! is > 1, 2 then > 2, 1 but you can skip an episode, and hit all permutations with > 1, 2, 1

anonymoushn 3y ago

The question is what's the shortest sequence that contains every permutation as a substring. If each episode after the 14th got you a new permutation, you would need 13+14!, but that's not possible. For example with 3 episodes, you could begin 12312, then any episode you choose from that position does not contribute a permutation. I think the shortest sequence goes 123121321.

quickthrower2 3y ago

> If a television series has just three episodes, there are six possible orders in which to view them: 123, 132, 213, 231, 312 and 321. You could string these six sequences together to give a list of 18 episodes that includes every ordering, but there’s a much more efficient way to do it: 123121321.

tromp 3y ago
And with 7 substrings of length 3, it's provably minimal, since making every 3-substring a permutation of 123 forces every element after the first 2. Assuming without loss of generality that it starts with 1 2, it is forced to start with 1 2 3 1 2 3 but there already repeats the same permutation. So one substring must be wasted (in the article this is phrased as having to traverse one higher cost edge in the corresponding graph).
fsckboy 3y ago
that ...,1,2,1,.. in the middle bothers me, nobody wants to watch three in a row that does not include all three, i'd rather have a duplicate triplet, or at least include the case as another potential bound, or classes of orderings where perhaps some numbers of elements have these defects while others don't.

abetusk 3y ago

The article doesn't do a good job of explaining the constraint. The sequence being generated is called a superpermutation [0]. From the Wikipedia article: """ ...a superpermutation on n symbols is a string that contains each permutation of n symbols as a substring. """ In other words, construct a big long string made up of the N symbols where every permutation of the N symbols appears in it. Since there's the possibility of overlaps, you can do better than the naive method of just pasting all N! permutations together. Note that this sounds very similar to a De Brujn sequence [1] but is different since a De Bruijn sequence ask for every possible sequence of N symbols (of length M, say), not every possible permutation. So a De Bruijn sequence would have 000, 001, 002, ... 200, 201, ... , 222 in it whereas a superpermutation would exclude (or at least not count) some of those sequences as they're not permutations (012, 021, 102, 120, 201, 210). [0] https://en.wikipedia.org/wiki/Superpermutation https://en.wikipedia.org/wiki/Superpermutation [1] https://en.wikipedia.org/wiki/De_Bruijn_sequence https://en.wikipedia.org/wiki/De_Bruijn_sequence EDIT: links (de bruijn)

beardyw 3y ago
Ah, thanks. I was going to bring that up, but hadn't spotted the difference.
bumby 3y ago
Is a superpermuation just a more efficient annotation or is it more helpful in solving an optimization problem? They talk about the travelling salesman problem in the article but they don't exactly explain if knowing the superpermutation helps solve it faster.
- abetusk 3y ago
  I'm no expert but here are my opinions: One goal is to find an 'efficient' annotation of a superposition. That is, "what is the minimum superpermutation string length of of N symbols", which itself is a sort of optimization problem. We can presumably get bounds on the minimum and maximum it can be and maybe the 'optimal' shortest superpermutation has enough variation that the bounds aren't/can't be exact. As to what "practical" applications superpermutations have, nothing comes to mind but considering how many applications de Bruijn sequences show up, I'd be surprised if they didn't start cropping up from time to time in the future. As to the travelling salesman/Hamiltonian path/cycle problem, my impression is that they used a clever construction of a Hamiltonian cycle on a hyper-cube/Cayley graph/high-dimensional-high-degree graph to show lower/upper bounds on the number of superpermutations. In other words, the implication is the other way. They construct a Hamiltonian cycle on a specially crafted graph to show lower/upper bounds rather than use superpermutations to say anything about Hamiltonian cycles. To get a flavor for how this works, I'll copy pasta the de Bruijn "construction" section of Wikipedia [0]: """ The de Bruijn sequences can be constructed by taking a Hamiltonian path of an n-dimensional de Bruijn graph over k symbols (or equivalently, an Eulerian cycle of an (n − 1)-dimensional de Bruijn graph). """ With a de Bruijn graph [1] being a specialized graph construction. [0] https://en.wikipedia.org/wiki/De_Bruijn_sequence#Construction https://en.wikipedia.org/wiki/De_Bruijn_sequence#Constructio... [1] https://en.wikipedia.org/wiki/De_Bruijn_graph https://en.wikipedia.org/wiki/De_Bruijn_graph

plant-ian 3y ago

I think they mean if say there were episodes a, b and c the orders to watch would be abc, bac, cba, acb, cab, bca. Now if you watched abcba you'd experience both orders abc and cba but only watch 5 episodes in a row instead of 6. So what is the minimum number of episodes to watch in a row to experience all six different orders?

psyklic 3y ago

You can interleave the orderings. If there are two episodes (1 and 2), we only have to watch three episodes in a row: 121. Then, we've watched all permutations -- 12 and 21. The "14!" solution (where we watch 14x14! episodes) means there is no interleaving -- we just watch each permutation in turn. In our 2-episode example, we'd have to watch one extra episode (for a total of 2x2! = 4), e.g. in the order 1221.