This is already a post from comp.lang.prolog and
stackoverflow. But it seems it is reasonably challenging
and could be fun. So I am also crossposting here.
I want to watch 6 episodes of “friends” in all
possible permutations. How can I arrange the
episodes in one string so that the substrings
of length 6 cover all permutations? What are
the shortest such strings? What would be the
Prolog code for that?
See also:
These are the links I posted as comments to the StackOverflow question. I will add more as I find ones of value.
What Jan Burse did not note in the original question and why this is of interest is that while the specific case is to find the answer for 6 items in a set, the more general problem of finding the minimum of a superpermutation is an unanswered question in maths. What makes this of value to a Prolog community is that while the answers for the values 1,2,3,4, and 5 are known.
there is also a proof for a lower bound (4chan proof)
n! + (n − 1)! + (n − 2)! + n − 3.
and it is suspected (YouTube) (Site) (paper) that this is an upper bound
L₂(n) = n! + (n − 1)! + (n − 2)! + (n − 3)! + n − 3
and possibly even (YouTube) (link)
L₃(n) = n! + (n − 1)! + (n − 2)! + (n − 3)! + n − 4
and that amateur people in math and computer science can work on this by finding examples that are equal to or lower than the value predicted in the proof.
| n | 4chan lower bound | L₂(n) | Current Best Minimal Superpermutation Length | Known to be minimum | Current Best Minimal Superpermutation | |
|---|---|---|---|---|---|---|
| 1 | - | - | 1 | Yes | 1 | |
| 2 | - | - | 3 | Yes | 121 | |
| 3 | 9 | - | 9 | Yes | 123121321 | |
| 4 | 33 | 34 | 33 | Yes | 123412314231243121342132413214321 | |
| 5 | 152 | 154 | 153 | Yes | 123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321 | |
| 6 | 867 | 873 | 872 | No | 12345612345162345126345123645132645136245136425136452136451234651234156234152634 15236415234615234165234125634125364125346125341625341265341235641235461235416235 41263541236541326543126453162435162431562431652431625431624531642531462531426531 42563142536142531645231465231456231452631452361452316453216453126435126431526431 25643215642315462315426315423615423165423156421356421536241536214536215436215346 21354621345621346521346251346215364215634216534216354216345216342516342156432516 43256143256413256431265432165432615342613542613452613425613426513426153246513246 53124635124631524631254632154632514632541632546132546312456321456324156324516324 56132456312465321465324165324615326415326145326154326514362514365214356214352614 35216435214635214365124361524361254361245361243561243651423561423516423514623514 263514236514326541362541365241356241352641352461352416352413654213654123 | |
| 7 | 5884 | 5,908 | 5,906 | No | 5906 | link |
| 8 | 46,085 | 46,205 | 46,205 | No | 46,205 | |
| 9 | 408,246 | 408,966 | 408,966 | No | 408,966 |
EDIT 09/17/2019
In the StackOverflow discussion Jan B. asked
could be a nice example for tabling maybe?
While I don’t actively work on the problem, like many other problems I read up enough on it to have a working vocabulary so that when I read more about it I understand the problem, then I put the problem on the so called back burner of the brain.
When I think about this as a Hamilton path and the kernel/extensions structures it seems there could be a correspondence between the kernel/extensions and tabling.
Also when I recently watched this video about about neural networks, it seemed there was a similarity to simplifying a problem by reducing the given set to a more canonical form, but what and how they are related I don’t know.
Posting here not to start a discussion, but to give feedback for others who read this and say that yes I agree that looking at tabling to help solve the problem is a path I would put on my short list.
2 posts were split to a new topic: How to make a nice table in a post?