🚀 go-pugleaf

This post is a bit of a follow-up to a thread I started three or
four weeks under a similar title.  It may interest/amuse you to see
how much/little progress has been made. ;)

The Problem:

Given a set of n objects, what is the shortest sequence that contains
all n! permutations by decimation.  By decimation, we mean that
a sequence matches a permutation by deleting characters we don't need.
For example, for n=3...

abacaba
ab*c*** 	abc
a**c*b*		acb
*bac***		bac
*b*ca**		bca
***cab*		cab
***c*ba 	cba
 
What we know so far:  

n	string			length
1	a			1 
2	aba			3
3	abcabca			7
4	abcdabcadcba		12
5	abcdeabcdaebcadbcea	19

We also know that n(n-1)+1 is an upper bound, and a lower bound
is also O(n^2).  Due to the combinatorial nature of the problem,
it is becoming infeasible to find solutions by testing each
possible string.  GA (Genetic Algorithm) has been suggested as
one way of conducting searches for large n.  Some work has already
been done to find the number of strings of given length which
contain 0 or 1 permutations.  Generalisation of this analytic
approach is looking difficult - given n objects and a string of
length l, how many possible strings are there containing p
permutations?

-- 
Nigel Stewart - Postgraduate Student - RMIT, Melbourne, Australia.
nts@minyos.its.rmit.edu.au.NOSPAM - http://minyos.its.rmit.edu.au/~nts/
------------------------------------------------------------------------------
It is not enough to succeed.  Others must fail.
-- 
Nigel Stewart - Postgraduate Student - RMIT, Melbourne, Australia.
nts@minyos.its.rmit.edu.au.NOSPAM - http://minyos.its.rmit.edu.au/~nts/
------------------------------------------------------------------------------
It is not enough to succeed.  Others must fail.