Tackling the Minimal Superpermutation Problem

2014-08-22 § 5 Comments

What’s the shortest string that contains every possible permutation of ABCD somewhere inside it? As it happens, it’s 33 letters long: ABCDABCADBCABDCABACDBACBDACBADCBA. A string like this is called a minimal superpermutation.

So what’s the shortest string that contains every possible permutation of ABCDE? It was recently shown that 153 letters is the shortest possible, and that there are eight different superpermutations of this length.

Okay, what about ABCDEF? The answer is that nobody knows. Until this week the shortest known superpermutation of ABCDEF was 873 letters long:

ABCDEFABCDEAFBCDEABFCDEABCFDEABCDFEABCDAEFBCDAEBFCDAEBCFDAEBCDFAEB
CDAFEBCDABEFCDABECFDABECDFABECDAFBECDABFECDABCEFDABCEDFABCEDAFBCED
ABFCEDABCFEDABCADEFBCADEBFCADEBCFADEBCAFDEBCADFEBCADBEFCADBECFADBE
CAFDBECADFBECADBFECADBCEFADBCEAFDBCEADFBCEADBFCEADBCFEADBCAEFDBCAE
DFBCAEDBFCAEDBCFAEDBCAFEDBCABDEFCABDECFABDECAFBDECABFDECABDFECABDC
EFABDCEAFBDCEABFDCEABDFCEABDCFEABDCAEFBDCAEBFDCAEBDFCAEBDCFAEBDCAF
EBDCABEFDCABEDFCABEDCFABEDCAFBEDCABFEDCABACDEFBACDEBFACDEBAFCDEBAC
FDEBACDFEBACDBEFACDBEAFCDBEACFDBEACDFBEACDBFEACDBAEFCDBAECFDBAECDF
BAECDBFAECDBAFECDBACEFDBACEDFBACEDBFACEDBAFCEDBACFEDBACBDEFACBDEAF
CBDEACFBDEACBFDEACBDFEACBDAEFCBDAECFBDAECBFDAECBDFAECBDAFECBDACEFB
DACEBFDACEBDFACEBDAFCEBDACFEBDACBEFDACBEDFACBEDAFCBEDACFBEDACBFEDA
CBADEFCBADECFBADECBFADECBAFDECBADFECBADCEFBADCEBFADCEBAFDCEBADFCEB
ADCFEBADCBEFADCBEAFDCBEADFCBEADCFBEADCBFEADCBAEFDCBAEDFCBAEDCFBAED
CBFAEDCBAFEDCBA

and it was thought that might be the shortest possible.

But we now know it isn’t, because I found a shorter one:

ABCDEFABCDEAFBCDEABFCDEABCFDEACBFDEACFBDEACFDBEACFDEBACFDEABCDFEAB
CDAEFBCDAEBFCDAEBCFDAEBCDFAEBCDAFEBCDABEFCDABECFDABECDFABECDAFBECD
ABFECDABCEFDABCEDFABCEDAFBCEDABFCEDABCFEDACBFEDCABFDECAFBDCEAFBDCA
EFBDCAFEBDCAFBEDCAFBDECAFDBECADFBECADBFECADBEFCADBECFADBECAFDEBCAD
FEBCADEFBCADEBFCADEBCFADEBCAFDECBAFDECABFDCEABFDCAEBFDCABEFDCBAEFD
BCAEDFBCAEDBFCAEDBCFAEDBCAFEDBCAEFDBACEFDBAECFBDAECFBADECFBAEDCFBA
ECDFBACEDFBACDEFBACDFEBACDFBEACDFBAECFDBAEFCDBAFECDBAFCEDBAFCDEBAF
CDBEAFCDBAEFDCBEAFDCBEFADCBEFDACBEFDCABFEDCBAFEDCBFAECDBFACEDBFACD
EBFACDBEFACDBFEACDBFAECBDFEACBDFECABDFCEABDFCAEBDFCABEDFCBAEDFCBEA
DFCBEDAFCBEDFACBEDFCABDEFCBADEFCBDAEFCBDEAFCBDEFACBDEFCABDFECBADFE
CBDAFECBDFAECBFDAECBFADECBFAEDCBFEADCFBEADCFEBADCEFBADCEBFADCEBAFD
CEBADFCEBADCFEABDCFAEBDCFABEDCFABDECFABDCEFABDCFEADBCEFADBCEAFDBCE
ADFBCEADBFCEADBCFEADCBFEDACFBEDACFEBDACEFBDACEBFDACEBDFACEBDAFCEBD
ACFEDBACFEDABC

I’ve uploaded a short note about it to the arxiv.

I hate the Pumping Lemma

2013-08-18 § 34 Comments

I hate the Pumping Lemma for regular languages. It’s a complicated way to express an idea that is fundamentally very simple, and it isn’t even a very good way to prove that a language is not regular.

Here it is, in all its awful majesty: for every regular language L, there exists a positive whole number p such that every string w∈L that has p characters or more can be broken down into three substrings xyz, where y is not the empty string and the total length of xy is at most p, and for every natural number i the string xyiz is also in L.
« Read the rest of this entry »

“Venn diagram” partitioning

2013-07-10 § Leave a comment

Paddy3118 wrote about partitioning elements in the same way a Venn diagram does. So, if we have sets AB and C, the partitions are

Image

« Read the rest of this entry »

Linear Logic without Units

2013-05-10 § Leave a comment

My PhD thesis (2007) was available for several years from my web site at the University of Manchester, but since that site was taken down it’s been unavailable. Today’s announcement is that I’ve finally got round to uploading it to GitHub.

« Read the rest of this entry »

Puzzles like Adrift

2013-04-19 § 3 Comments

Quite a few people were surprised by my description of Adrift as a “new game” – even though it was very new at the time – because they had seen similar games or puzzles before.

You can read some of the history on Wikipedia: similar puzzles were posed as early as the 19th century, and more recently Big Duck Games released a nice version called Flow Free for Android and iOS.

This game was the subject of a programming competition at Oxford University last year. The competition was won by Thomas Ahle, with this rather nice program.

Adrift puzzles are a little bit different, though: they’re on an unusual grid – the surface of half a cube, i.e. three square grids connected at the edges – and also there are rocks, squares you’re not allowed to use.

John H Conway and the invention of the filing cabinet

2012-10-27 § Leave a comment

Conway is incredibly untidy. The tables in his room at the Department of Pure Mathematics and Mathematical Statistics in Cambridge are heaped high with papers, books, unanswered letters, notes, models, charts, tables, diagrams, dead cups of coffee, and the most amazing assortment of bric-a-brac, which has overflowed most of the floor and all of the chairs, so that it is hard to take more than a pace or two into the room and impossible to sit down. If you can reach the blackboard there is a wide range of coloured chalk, but no space to write. His room in college is in a similar state. In spite of his excellent memory he often fails to find the piece of paper with the important result that he discovered some days before, and which is recorded nowhere else. Even Conway came to see that this was not a desirable state of affairs, and he set to work designing and drawing plans for a device which might induce some order amongst the chaos. He was about to take his idea to someone to get it implemented, when he realised that just what he wanted was standing, empty, in the corner of his room. Conway had invented the filing cabinet!

Richard K Guy on John H Conway, in Mathematical People

I originally posted this to Posterous on 27 October, 2012. Posterous is closing down, so I have migrated it here on 13 March, 2013.

The Prisoner’s Dilemma

2012-07-23 § 23 Comments

The Prisoners’ Dilemma

The Prisoner’s Dilemma is a game, but a game that seems to bear lessons for the conduct of human affairs more generally, and it has attracted a great deal of attention from men not noted for their frivolity. It was discovered in 1950 at the RAND corporation, a military think-tank established after World War II by the United States Air Force to conduct a “program of study and research on the broad subject of intercontinental warfare”.

photo: DenisNata / Shutterstock.com

So it is a serious game, but a simple one for all that. It requires two players, let’s say you and me. There is only one move. Each of us must make a choice, to “cooperate” or “defect”, without knowing what the other has chosen. Perhaps each of us takes, from a chess board, one black and one white pawn, and as we face each other I put my hands behind my back and proffer a closed fist containing the pawn I have chosen. You make your choice, too, in the same way. Together we open our hands, and reveal what we have chosen. The black pawn represents the black heart of the defector, the white the innocence of the cooperator.

Now, the reckoning. Should we each reveal a white pawn, we have cooperated and each of us wins £20: a fair and happy outcome. If we both are blackhearts with black pawns in our hands, we win nothing. But wickedness is not without its rewards in this game, for if I hold black and you white then I win £40 – and you, looking sadly at the white pawn in your hand, must pay £10 for your naivety. « Read the rest of this entry »

Where Am I?

You are currently browsing the chatter category at Bosker Blog.

Follow

Get every new post delivered to your Inbox.

Join 777 other followers