MathGroup Archive 2009

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

Search the Archive

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


  • 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