#1
  1. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2003
    Posts
    3
    Rep Power
    0

    Talking 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.
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2001
    Location
    Dublin
    Posts
    413
    Rep Power
    14
    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 find-the-minimum type routine - with no need to keep more than one of the ww strings in memory at a time.
  4. #3
  5. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2003
    Posts
    3
    Rep Power
    0
    i have found the solution the shortest covering string problem.
    it is np
    Last edited by Vigilant; August 27th, 2003 at 02:45 AM.
  6. #4
  7. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2003
    Posts
    3
    Rep Power
    0
    i have found the solution to the shortest covering string problem

IMN logo majestic logo threadwatch logo seochat tools logo