Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
August 26th, 2003, 10:37 AM
 Vigilant
Junior Member

Join Date: Aug 2003
Posts: 3
Time spent in forums: < 1 sec
Reputation Power: 0
Shortest Covering String Problem

shortest Covering String problem
Input: Finite alphabet SIGMA of t symbols;
collection C={SIGMA1,SIGMA2,...,SIGMAn} of subsets of SIGMA
Output: Find a string w, (sequence of symbols) over SIGMA such that |w| is minimum
and for each 1< =i< =n, all of the symbols in SIGMAi appear
in a consecutive block of |SIGMAi| symbols in the string w.

Last edited by Vigilant : August 27th, 2003 at 03:48 AM.

#2
August 26th, 2003, 12:28 PM
 epl
Contributing User

Join Date: Mar 2001
Location: Dublin
Posts: 413
Time spent in forums: 2 h 18 m 18 sec
Reputation Power: 13
with no concern about efficiency i would do the following:

generate all strings ww such that each is based on a concatenation of each of the SIGMAi's, with all possible orders of the individual elements / characters within each SIGMAi covered.

AC ABEG BCDEFG BCDFG CDFG ADFG ABDEG ABDG D

then go to the next permutation for SIGMA1

CA ABEG BCDEFG BCDFG CDFG ADFG ABDEG ABDG D
then
AC ABEG BCDEFG BCDFG CDFG ADFG ABDEG ABDG D
AC ABGE BCDEFG BCDFG CDFG ADFG ABDEG ABDG D
AC AEBG BCDEFG BCDFG CDFG ADFG ABDEG ABDG D
AC AEGB BCDEFG BCDFG CDFG ADFG ABDEG ABDG D

etc.

then clear each ww string by removing all but one of any sequence of consecutive characters. given a permutations routine you will be able to work through the possibilities as you would in any find-the-minimum type routine - with no need to keep more than one of the ww strings in memory at a time.

#3
August 26th, 2003, 07:02 PM
 Vigilant
Junior Member

Join Date: Aug 2003
Posts: 3
Time spent in forums: < 1 sec
Reputation Power: 0
i have found the solution the shortest covering string problem.
it is np

Last edited by Vigilant : August 27th, 2003 at 03:45 AM.

#4
August 27th, 2003, 03:37 AM
 Vigilant
Junior Member

Join Date: Aug 2003
Posts: 3
Time spent in forums: < 1 sec
Reputation Power: 0
i have found the solution to the shortest covering string problem

 Viewing: Dev Shed Forums > Programming Languages - More > Software Design > Shortest Covering String Problem