Re: Set of strings reducing problem (Again!)
- To: mathgroup at smc.vnet.net
- Subject: [mg60505] Re: Set of strings reducing problem (Again!)
- From: "dkr" <dkrjeg at adelphia.net>
- Date: Sun, 18 Sep 2005 01:16:02 -0400 (EDT)
- References: <dgbf2b$fp6$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Edson,
Using your rules, the reduced set you end up with may depend on the
order in which you consider appropriately mismatched pairs. For
example, consider the list L of your example:
L=
{"1111","111X","1121","112X","11X1","11XX","1211","121X","1221","12X1","1X11",\
"1X1X","1X21","1XX1","2111","211X","2121","21X1","2211","2X11","X111","X11X",\
"X121","X1X1","X211","XX11"};
Your pattern matching algorithm generates a sequence of mismatched
pairs to operate on, and you end up with the reduced set of six
strings:
{"11TD","1U1D","1UU1","U11D","U1U1","UU11"}
But by taking a different sequence of appropriately mismatched pairs
and operating on them according to your rules, we can (see below) end
up with a different reduced set, also containing six strings:
{"T11D","1TU1","11UX","TU11","1U1X","U1U1"}
So the question is: do you care which reduced set your algorithm
finds, or do you want to find all the reduced sets, or is there
something else you are after?
list1=
{"1111","111X","1121","112X","11X1","11XX","1211","121X","1221","12X1","1X11",\
"1X1X","1X21","1XX1","2111","211X","2121","21X1","2211","2X11","X111","X11X",\
"X121","X1X1","X211","XX11"};
Replace the pair "1111" and "2111" with "M111", the pair "211X" and
"X11X" with "U11X", the pair "X121" and "X1X1" with "X1U1", and the
pair "X211" and "XX11" with "XU11".
Making these replacements yields the list:
list2=
{"M111","111X","1121","112X","11X1","11XX","1211","121X","1221","12X1","1X11",\
"1X1X","1X21","1XX1","U11X","2121","21X1","2211","2X11","X111","X1U1","XU11"}
Then in list2, replace the pair "M111" and "X111" with "T111", which
yields the list:
list3=
{"T111","111X","1121","112X","11X1","11XX","1211","121X","1221","12X1","1X11",\
"1X1X","1X21","1XX1","U11X","2121","21X1","2211","2X11","X1U1","XU11"}
Then in list3, replace the pair "111X" and "U11X" with "T11X", the
pair "2121" and "21X1" with "21U1", and the pair "2211" and "2X11" with
"2U11".
Making these replacements yields the list:
list4=
{"T111","T11X","1121","112X","11X1","11XX","1211","121X","1221","12X1","1X11",\
"1X1X","1X21","1XX1","21U1","2U11","X1U1","XU11"}
Then in list4, replace the pair "T111" and "T11X" with "T11D", the pair
"1121" and "1221" with "1M21", the pair "12X1" and "1XX1" with "1UX1",
and the pair "21U1" and "X1U1" with "U1U1".
Making these replacements yields the list:
list5=
{"T11D","1M21","112X","11X1","11XX","1211","121X","1UX1","1X11","1X1X","1X21",\
"U1U1","2U11","XU11"}
Then in list5, replace the pair "1M21" and "1X21" with "1T21", and the
pair "2U11" and "XU11" with "UU11".
Making these replacements yields the list:
list6=
{"T11D","1T21","112X","11X1","11XX","1211","121X","1UX1","1X11","1X1X","U1U1",\
"UU11"}
Then in list6, replace the pair "112X" and "11XX" with "11UX", and the
pair "1211" and "1X11" with "1U11".
Making these replacements yields the list:
list7=
{"T11D","1T21","11UX","11X1","1U11","121X","1UX1","1X1X","U1U1","UU11"}
In list7, replace the pair "11X1" and "1UX1" with "1TX1", which yields
the list
list8= {"T11D","1T21","11UX","1TX1","1U11","121X","1X1X","U1U1","UU11"}
In list8, replace the pair "1T21" and "1TX1" with "1TU1", and the pair
"1U11" and "UU11" with "TU11".
Making the replacement yields the final, irreducible list
{"T11D","1TU1","11UX","TU11","121X","1X1X","U1U1"}
dkr