Talk:Superpermutation minimisation

N. Johnston's algorithm

Hi Paddy3118,

The referenced work by N. Johnston proposes an algorithm which produces strings of length sum over k=1 to n of k!. None of the Python or D solutions produce such a good result. Would it be better if the task was to implement N. Johnston's algorithm, outputting the first 5 results, and noting that after 5 shorter strings probably exist? I am surprised that you have placed so much emphasis on timings here, given that you are so quick to complain when someone who thinks a timing says something about a solution does so. (Given that I don't think these timings mean much).--Nigel Galloway (talk) 12:21, 12 December 2014 (UTC)

Hi Nigel, I decided to write the task as a means of comparing heuristics. I needed several heuristics and a weighting scheme to compare them.

N. Johnston's paper wasn't one of my early references, (indeed I have lost the reference that gave me s_perm0 - my first algorithm). Maybe either I or someone else will add that algorithm to the Python entry in the future? --Paddy3118 (talk) 15:06, 12 December 2014 (UTC)

Ambiguous

Task, as currently specified, is ambiguous. That the underlying problem may or may not be NP Complete is a part of this. --Rdm (talk) 04:51, 13 December 2014 (UTC)

Please expand. Ambiguous in what way? --Paddy3118 (talk) 06:24, 13 December 2014 (UTC)