Re: Set of strings reducing problem

*To*: mathgroup at smc.vnet.net*Subject*: [mg58576] Re: [mg58560] Set of strings reducing problem*From*: Curtis Osterhoudt <gardyloo at mail.wsu.edu>*Date*: Fri, 8 Jul 2005 00:46:07 -0400 (EDT)*References*: <200507070935.FAA29410@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

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 "1111M111" + "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. C.O. 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: > >L={"11111111", > "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 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!!!!! > >Edson > >edsferr at uol.com.br > > > > -- PGP Key ID: 0x235FDED1 Please avoid sending me Word or PowerPoint attachments. http://www.gnu.org/philosophy/no-word-attachments.html

**References**:**Set of strings reducing problem***From:*"Edson Ferreira" <edsferr@uol.com.br>