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>
- Reply-to: drmajorbob at bigfoot.com
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"
{"AD", "CD", "DA", "DC"}
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
> DAD->D
> ABC->DC
> CBA->CD
> BAD->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
> ABAAD=BABAD=BBABD=BBAD so you may have to use it both
> 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
- References:
- String substitution system
- From: Hauke Reddmann <fc3a501@uni-hamburg.de>
- String substitution system