[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Re: [QUIZ] B & E (#72

Ross Bamford

3/30/2006 7:38:00 AM

On Thu, 2006-03-30 at 16:17 +0900, Timothy Bennett wrote:
> Hi, I wanted to discuss this problem from a more mathematical
> perspective. Anyone that's interested, please comment on this, I'm
> curious what others' thoughts are.
>

(I'm not a mathematician (by any stretch of the word) so I may be
utterly wrong in all of this).

I think this problem is basically the shortest common superstring
problem:

http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK5/N...

Which is basically how my solution (and I think yours too) approached
it. The upshot is that it's easy to find a common superstring, and even
a reasonably short common superstring, but very difficult to find the
_shortest_ or determine how long it would be (it's NP complete I
think).

That said, while working on it my limited mathematical knowledge kept
taunting me that there was a much easier way given that we were dealing
with numbers only, but I couldn't find it and gave up after a bit - I'd
love to see something like that done.

--
Ross Bamford - rosco@roscopeco.REMOVE.co.uk
1 Answer

Timothy Bennett

3/30/2006 3:21:00 PM

0

On Mar 29, 2006, at 11:37 PM, Ross Bamford wrote:
>
> I think this problem is basically the shortest common superstring
> problem:
>
> http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK5/N...
>
> Which is basically how my solution (and I think yours too) approached
> it. The upshot is that it's easy to find a common superstring, and
> even
> a reasonably short common superstring, but very difficult to find the
> _shortest_ or determine how long it would be (it's NP complete I
> think).

I definitely need to study more math and algorithms. Yes, this does
seem to be a variation on the shortest common superstring, and the
sources I'm finding say that it is NP-complete. Unfortunately, the
existence of the stop digits seems to complicate matters somewhat.
The most thorough discussion I've found online (so far, haven't
looked very long yet) is a PDF discussing, of all things, the Pokemon
trading card game: http://home.earthlink.net/~mstamp1/paper...

Nothing I've found so far discusses how one might predict the length
of the shortest common superstring, though. I feel, that for our
rather narrow problem domain, that it should be possible. Especially
since the substrings in the more traditional superstring problems are
random to some degree, while we know what all of our strings are.
Hm, I'll have to think on this more.

Tim