MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Set of strings reducing problem

  • To: mathgroup at
  • Subject: [mg58583] Re: Set of strings reducing problem
  • From: Bill Rowe <readnewsciv at>
  • Date: Fri, 8 Jul 2005 00:46:15 -0400 (EDT)
  • Sender: owner-wri-mathgroup at

On 7/7/05 at 5:35 AM, edsferr at (Edson Ferreira) wrote:

>I have a problem that I haven't got any clue to solve with

>Let's say a have a list of "n" equal length strings:

>   "11112111",
>   "1111X111",
>       ...
>       ...
>       ...
>   "21122211"}

>The characters used in strings are only "1", "X", "2", "U", "M",
>"D" and "T".

>What I want is a reduced set of strings (with all the resulting
>strings with the same length as all the original ones).

>The rule to "join" two strings is the following:

>If one string is different from the other by just one character
>then take the characters that are different and apply the rule

>"1" + "X" = "D"
>"1" + "2" = "M"
>"1" + "U" = "T"
>"X" + "2" = "U"
>"X" + "M" = "T"
>"2" + "D" = "T"

>For example, suppose I have these two elements in the list :
>"11112111" and "1111X111"

>The rule will transform these two strings into one : "1111U111"

The function below will add two strings per your rules above

addString[x_, y_] := 
  Block[{X, M, T, D, U}, 
   StringJoin @@ ToString /@ 
     ((ToExpression /@Characters[x] + ToExpression /@ Characters[y] /. 
       {D + 2 -> 2*T, M + X -> 2*T, X + 2 -> 2*U, U + 1 -> 2*T, 
        3 -> 2*M, X + 1 -> 2*D})/2)]
What I've done is use ToExpression to convert each string to a list of symbols and integers then use Mathematica's pattern matching to implement your rules. The final result is then converted back to a string. I've used Block to ensure the results are not affected by usage of X, M etc as variables elsewhere in the notebook.

>After all the possible transformations (always using two strings
>with only one different character and resulting another string) I
>will obtain a reduced set of strings.

>How can I do that with mathematica??

>I guess the first step is a function to identify is two strings are
>different by just one ccharacter. A loop then search in the set for
>any ocurrences of that and apply all possible transformations until
>we can't get any redution.

The following function will count the number of differences in two strings of equal length

noDifferent[x_, y_] := 
    MapThread[SameQ, {Characters[x], Characters[y]}], False]

I can generate a list of all pairs that differ by a single character as follows:

Union[Pick[Flatten[Outer[Sort@{#1, #2}& , L, L], 1], 
   (#1 == 1 & ) /@ Flatten[Outer[noDifferent, L, L]]]]

and finally doing


where list is the list of pairs that differ by one character will generate the reduced list you want.
To reply via email subtract one hundred and four

  • Prev by Date: Re: Set of strings reducing problem
  • Next by Date: GroebnerBasis (was Re: Documentation)
  • Previous by thread: Re: Set of strings reducing problem
  • Next by thread: Re: Set of strings reducing problem