Re: String substitution system

• To: mathgroup at smc.vnet.net
• Subject: [mg97218] Re: [mg97176] String substitution system
• From: DrMajorBob <btreat1 at austin.rr.com>
• Date: Sun, 8 Mar 2009 05:52:40 -0500 (EST)
• References: <200903070738.CAA16935@smc.vnet.net>

```Possibly this does the job?

Clear[cycle, twoStep, legalize, fixedPt, minimums]
cycle[s_String] :=
Table[StringDrop[s, n] <> StringTake[s, n], {n, 1, StringLength@s}]
twoStep[s_String] := Union@Flatten[legalize /@ cycle@s]
legal = {CC -> C, DD -> D, CA -> C, AC -> C, DB -> D, BD -> D,
CDC -> C, DCD -> D, CBC -> C, DAD -> D, ABC -> DC, CBA -> CD,
BAD -> CD, DAB -> DC, BAB -> ABA} /.
Rule[x_Symbol, y_Symbol] :> Rule[ToString@x, ToString@y];
legalize[s_String] := Union[{s}, StringReplaceList[s, legal]]
fixedPt[s_List] := FixedPoint[Union@Flatten[twoStep /@ #] &, s]
fixedPt[s_String] := fixedPt@{s}
minimums[s_String] := Module[{f = fixedPt@s, lengths},
lengths = StringLength /@ f;
Pick[f, lengths, Min@lengths]
]

minimums@"DAB"

minimums@"CBBA"

{"BBC", "BCB", "CBB"}

Answers don't appear to be unique, as you can see.

Bobby

On Sat, 07 Mar 2009 01:38:57 -0600, Hauke Reddmann
<fc3a501 at uni-hamburg.de> wrote:

> Another question that is probably too trivial for you :-)
>
> I want to generate all words A,B,C,D,AA,AB,...,DD,AAA,...
> until, eh, 6-7 letters should suffice, and put them in a list.
> The following string replacements are legal:
> CC->C
> DD->D
> CA->C
> AC->C
> DB->D
> BD->D
> CDC->C
> DCD->D
> CBC->C
> ABC->DC
> CBA->CD
> DAB->DC
> BAB->ABA
> Note that everything but the last one shortens the word
> and thus strings containing these substrings may be simply
> dropped if you generate the words ordered by length, but the last
> one is a bit tricky - BABBC=ABABC=AABAC=AABC and
> ways and repeatedly.
> Now I'm an old FORTRAN chap and being nearly 50 years old,
> I probably won't learn the Kamasutra of recursive function
> calls anymore :-) But surely you'll have a three-liner
> for this problem?
> P.S. Actually the strings are cyclic too - CBBA=ACBB=CBB.
> P.P.S. Remember, poor University, version 5.2 ;-)

--
DrMajorBob at bigfoot.com

```

• Prev by Date: Re: When a string does not match itself
• Next by Date: Re: A newbee to Mathematica
• Previous by thread: String substitution system
• Next by thread: Re: String substitution system