Late Summer Challenge - Superpermutation in Prolog

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:

1 Like

These are the links I posted as comments to the StackOverflow question. I will add more as I find ones of value.

1 Like

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.

1 Like

2 posts were split to a new topic: How to make a nice table in a post?