Re: a special type of strings!
- To: mathgroup at smc.vnet.net
- Subject: [mg78760] Re: a special type of strings!
- From: Jean-Marc Gulliet <jeanmarc.gulliet at gmail.com>
- Date: Sun, 8 Jul 2007 06:20:54 -0400 (EDT)
- Organization: The Open University, Milton Keynes, UK
- References: <f6npb1$6r1$1@smc.vnet.net>
mumat wrote:
> Hi Everyone,
>
> I have an alphabet A= {a,b,c,d,e,f,g,h}. letters in A are grouped as
> follows:
>
> group1: G1={a}
> group2:G2={b,c},
> group3:G3={d,e,f},
> group4: G4={g,h}.
>
> In other words, we have {{a},{b,c},{d,e,f},{g,h}} as an ordered
> partition of A.
>
> We say the string \alpha=s_1,s_2,s_3,...,s_n to be NORMAL
>
> if and only if
>
> for every i,j: ( if s_i is in Gj then, (s_(i+1) is in Gj or s_(i+1)
> is in G(j-1) ) OR (s_i is in G1).
>
>
> For instance the following three sequences are normal:
>
> Seq1: d,b,a,g,e,f,c,a,e
> Seq2: a,d,b,a,b,e,c,a,h.
> Seq3: g,g,h,d,f,d,b,c.
>
> I need to write a code to determine weather a given sequence is
> Normal:
>
> NormalQ[seq_]:=....
My understanding of your algorithm (of course I might be wrong) is that
sequence #2 is not normal since the fifth element, 'b', is in G2 but the
following element 'e' belongs neither to G2 nor to G1. The following
implementation of your algorithm reflects that. I have not extensively
tested the code below but it should help you started anyway.
In[1]:= G[1] = {a};
G[2] = {b, c};
G[3] = {d, e, f};
G[4] = {g, h};
In[5]:= NormalQ[seq_] := Module[{lseq = Length[seq],
currentCharInGroupQ, currentCharInGroupOneQ,
nextCharInGroupQ,
nextCharInPrevGroupQ, normalCharList},
currentCharInGroupQ[ichr_, jgrp_] :=
MemberQ[G[jgrp], seq[[ichr]]];
currentCharInGroupOneQ[ichr_] := MemberQ[G[1], seq[[ichr]]];
nextCharInGroupQ[ichr_ /; ichr < lseq, jgrp_] :=
MemberQ[G[jgrp], seq[[ichr + 1]]];
nextCharInGroupQ[ichr_, jgrp_] := True;
nextCharInPrevGroupQ[ichr_ /; ichr < lseq,
jgrp_ /; jgrp > 1] :=
MemberQ[G[jgrp - 1], seq[[ichr + 1]]];
normalCharList = Table[False, {lseq}];
For[i = 1, i <= lseq, i++,
If[currentCharInGroupOneQ[i], normalCharList[[i]] = True,
For[j = 2, j <= 4, j++, If[currentCharInGroupQ[i, j] &&
(nextCharInGroupQ[i, j] ||
nextCharInPrevGroupQ[i, j]),
normalCharList[[i]] = True]; ]; ]; ];
Count[normalCharList, False] == 0]
In[6]:= seq1 = {d, b, a, g, e, f, c, a, e};
seq2 = {a, d, b, a, b, e, c, a, h}; seq3 = {g, g, h, d, f, d, b, c};
In[8]:= NormalQ /@ {seq1, seq2, seq3}
Out[8]= {True, False, True}
Regards,
Jean-Marc
> and also generating all normal sequences of a particular length k:
> AllNormalSequences[k].
>
>
> Any help would be greately appreciated.
>
> best regards,
>
> chekad sarami