# 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)
- "Show descriptions and comparisons of algorithms used here, and select the "Best" algorithm as being the one generating shorter superpermutations." -- this seems to imply that each task implementation should handle some arbitrary number of algorithms and mark an algorithm producing the shortest result as the "Best". (Of course, Nigel Galloway seems to have stated that the task requires each implementation to provide an algorithm which consistently produces shortest possible results - but, currently, that's not what the task description explicitly asks for.) --Rdm (talk) 23:34, 21 August 2015 (UTC)

- The problem is NP Complete. The value of 872 for 6 is found by writing the problem as a TSP and using specialized TSP solvers. TSPs are NP Complete and very very very really hard to prove minimal solutions. Perhaps the ambiguity is with the tasks title, none of the algorithms used by D or Python produce minimal strings beyond 3. The C entry is new and produce results consistent with N. Johnson's algorithm (minimal to 5). I havn't checked if it is actually N. Johnson's algorithm. As above I don't understand the value of timing algorithms which do not do the same thing. Comparing C's value for 10 (4037913) and D's value (4_235_533) tell's me which algorithm is best. That D can do it in less than 9 secs mmm! --Nigel Galloway (talk) 13:46, 13 December 2014 (UTC)

- (Minimisation means making smaller - in this context smaller than just concatenating all permutations). --Paddy3118 (talk) 20:48, 13 December 2014 (UTC)
- Noun 1. minimisation - the act of reducing something to the least possible amount or degree. Perhaps the English word you are looking for is reduction.--Nigel Galloway (talk) 13:44, 14 December 2014 (UTC)

- (Minimisation means making smaller - in this context smaller than just concatenating all permutations). --Paddy3118 (talk) 20:48, 13 December 2014 (UTC)

## Problem with the translation from D to python

The code doesn't produce the correct strings, because `pos`

got passed into `r()`

by value, which is no good when `r()`

recursively calls itself and modifies `pos`

. The following is what should happen (conceptually, since `superperm.append()`

might get expensive depending on your Python setup. I don't have psycho module, so it actually runs faster than the current, very C-like Python entry.) I'm sure there's a better way to express the same algorithm without killing performance in Python, though.

<lang python>from string import ascii_uppercase, digits

try:

import psyco psyco.full()

except:

pass

N_MAX = 12

def r(n, superperm, count):

if not n: return False

c = superperm[-n] count[n] -= 1 if not count[n]: count[n] = n if not r(n - 1, superperm, count): return False

superperm.append(c) return True

def super_perm(n, chars = digits + ascii_uppercase):

assert len(chars) >= N_MAX

count = list(range(n+1)) superperm = [chars[i] for i in range(1,n+1)]

while r(n, superperm, count): pass return superperm

def main():

for n in xrange(N_MAX): superperm = super_perm(n) print "Super perm(%2d) len = %d" % (n, len(superperm)),

- print ':',
*.join(superperm),*

main()</lang>

## Phrasing needs improved

This sentence from the current task description does not make sense:

"For example, representing the characters as A..Z, using N=2 we choose to use the first three characters 'AB'."

There's two characters there, not three. Presumably the sentence author was thinking about the sequences 'ABA' or 'BAB' but that's not what got into the sentence, and even if it had, the sentence still would not make sense. --Rdm (talk) 05:15, 30 October 2015 (UTC)