MathGroup Archive 2005

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

Search the Archive

Re: Set of strings reducing problem

Hi, Edson,

   I guess I have a basic question on your transformations. You give six
rules for how to "add" the differing characters; are these the only
combinations possible? For example, will the combination of strings of
     + "11112111"
ever be encountered? In addition, when you say that the strings will
differ from each other by only one character, does this mean in _one_
given position? For example, a transpose of characters as in
         "21111111"  vs. "11111112"    might be seen as two strings 
with only one differing character, or two strings of _two_ differing
characters (one at either end).
      From your statement of applying transformation rules repeatedly
until nothing changes, my guess is that, yes, you've given the complete
set of transformation rules. In this case, what happens if I try to
"decompose" (someone more familiar with string manipulations, and,
perhaps, crytanalysis or group theory, may be better suited to ask these
questions) the operations? Can I, for example, do something like

        1 + X = D
==>1 + D = 1+(1+X)
                   =(1+1) +X
                   =1 + X  <--- Here I've assumed that because you want
strings differing by characters, that (1+1) -> 1.
In other words, is the "addition" associative? I think the answer to
this hinges on the answer as to the "only one character" problem.

                        Interesting problem! I'm sorry I can't help
(yet) on the implementation.

Edson Ferreira wrote:

>Dear Mathematica Users,
>I have a problem that I haven't got any clue to solve with Mathematica.
>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 
>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 bellow:
>"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"
>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.
>Thanks in advance for any help!!!!!
>edsferr at

PGP Key ID: 0x235FDED1
Please avoid sending me Word or PowerPoint attachments.

  • Prev by Date: Re: Can't assign value to symbols
  • Next by Date: Re: Problem with multiple function calling from a novice...
  • Previous by thread: Set of strings reducing problem
  • Next by thread: Re: Set of strings reducing problem