MathGroup Archive 2005

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

Search the Archive

Re: Set of strings reducing problem

  • To: mathgroup at smc.vnet.net
  • Subject: [mg58581] Re: Set of strings reducing problem
  • From: David Bailey <dave at Remove_Thisdbailey.co.uk>
  • Date: Fri, 8 Jul 2005 00:46:12 -0400 (EDT)
  • References: <daitu8$t2v$1@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

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
> 
Hello,

Although you could stick with a string-based formulation, I would 
convert your strings into lists of integers, converting back to strings 
at the end if desired. You could do this with
Map[f,Characters[string]]

where f would be defined:

f["1"]=1;
f["2"]=2;
f["M"]=3;
etc.

Now you can encode your rules as a set of definitions for another 
function g:

SetAttributes[g, Listable];

g[1,1]=1;
g[2,2]=2;
g[1,2]=3;
etc.

Because g gas Listable attribute, it will operate on two lists applying 
your rule element by element.

Given a list of lists L of this type it would be possible to combine 
them in every possible way using g with code such as:

Flatten[Outer[gg,L]]/.gg ->g]//Union

Note the use of gg, an undefined function, to let us flatten the 
structure without flattening the inermost lists (there are obviously 
other ways to achieve this).

You could use FixedPoint to repeat this process until no further change 
took place.

David Bailey
http://www.dbaileyconsultancy.co.uk


  • Prev by Date: Re: Don't understand behaviour of Solve[]
  • Next by Date: Re: Set of strings reducing problem
  • Previous by thread: Re: Set of strings reducing problem
  • Next by thread: Re: Set of strings reducing problem