August 26th, 2003, 09:37 AM

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 02:48 AM.
August 26th, 2003, 11:28 AM

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.
ie start with
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 findtheminimum type routine  with no need to keep more than one of the ww strings in memory at a time.
August 26th, 2003, 06:02 PM

i have found the solution the shortest covering string problem.
it is np
Last edited by Vigilant; August 27th, 2003 at 02:45 AM.
August 27th, 2003, 02:37 AM

i have found the solution to the shortest covering string problem