Re: Pattern matching more than once
- To: mathgroup@smc.vnet.net
- Subject: [mg12108] Re: Pattern matching more than once
- From: villegas@wolfram.com
- Date: Sat, 25 Apr 1998 01:30:38 -0400
- Organization: Deja News - The Leader in Internet Discussion
- References: <6hjqaa$2kj@smc.vnet.net>
> Input: Two lists, from some universal set
> Output: Many "spliced" lists obtained from the input.
>
> e.g. {{a,b,c},{d,e,f}} --> {{a,b,c},{d,e,f}} (no common element)
>
> {{a,b,c},{d,b,f}} --> {{a,b,c},{d,b,f},{a,b,f},{d,b,c}}
>
> {{a,b,c,d,e},{f,b,g,d,h}} -->
> {{a,b,c,d,e},{a,b,c,d,h},{a,b,g,d,e},{a,b,g,d,h},
> {f,b,c,d,e},{f,b,c,d,h},{f,b,g,d,e},{f,b,g,d,h}}
The common elements act as separators to split each list into several
sublists that don't contain the common elements. For instance, if X,
Y, and Z are the common elements, then
{a, b, X, c, Y, d, e, Z, f} ===>
{{a, b}, {c}, {d, e}, {f}}
If there are n common elements, each of the two lists, call them S and
T, falls apart into (n + 1) sublists:
S = {S0, S1, S2, ..., Sn}
T = {T0, T1, T2, ..., Tn}
Now you can form any spliced list you want: take either S0 or T0,
followed by either S1 or T1, followed by either S2 or T2, ..., followed
by either Sn or Tn. For instance,
{S0, T1, T2, S3, T4, ..., T(n-1), Sn}
Forming all possible combinations like this is just the Cartesian
product of the sets:
{S0, T0} x {S1, T1} x {S2, T2} x ... x {Sn, Tn}
In Mathematica, the most direct way to do a Cartesian product of lists
is with Distribute. A small example:
In[37]:= Distribute[{{S0, T0}, {S1, T1}, {S2, T2}}, List, List]
Out[37]=
{{S0, S1, S2}, {S0, S1, T2}, {S0, T1, S2}, {S0, T1, T2}, {T0, S1, S2},
{T0, S1, T2}, {T0, T1, S2}, {T0, T1, T2}}
The only thing left to do with this result is to re-insert the common
elements.
Here is one way to implement the Cartesian product idea.
Interleave[subLists_, commonElements_] /;
(Length[commonElements] == Length[subLists] - 1)
:=
Drop[
Join @@ MapThread[Sequence,
{subLists, List /@ Append[commonElements, Null]}]
-1
]
SpliceChains[chain1_, chain2_] :=
Module[{commonElements, commonPos1, commonPos2, subChains1,
subChains2},
commonElements = Intersection[chain1, chain2];
commonPos1 =
Flatten @
Position[chain1, Alternatives @@ commonElements, {1},
Heads -> False];
commonPos2 =
Flatten @
Position[chain2, Alternatives @@ commonElements, {1},
Heads -> False];
subChains1 = Apply[
Take[chain1, {#1 + 1, #2 - 1}] &,
Partition[Join[{0}, commonPos1, {0}], 2, 1],
{1}
];
subChains2 = Apply[
Take[chain2, {#1 + 1, #2 - 1}] &,
Partition[Join[{0}, commonPos2, {0}], 2, 1],
{1}
];
Distribute[Transpose[{subChains1, subChains2}], List, List,
List,
Interleave[{##}, commonElements] &
]
]
Here are a few small examples:
In[4]:= SpliceChains[{1, 2, x, 5, 6}, {3, x, 7, 8}]
Out[4]= {{1, 2, x, 5, 6}, {1, 2, x, 7, 8}, {3, x, 5, 6}, {3, x, 7, 8}}
In[5]:= SpliceChains[{1, 2, x, 5, 6}, {x, 7, 8}]
Out[5]= {{1, 2, x, 5, 6}, {1, 2, x, 7, 8}, {x, 5, 6}, {x, 7, 8}}
In[6]:= SpliceChains[{x, 5, 6}, {3, x}]
Out[6]= {{x, 5, 6}, {x}, {3, x, 5, 6}, {3, x}}
In[7]:= SpliceChains[{x, y}, {x, y}]
Out[7]= {{x, y}, {x, y}, {x, y}, {x, y}, {x, y}, {x, y}, {x, y}, {x, y}}
In[8]:= SpliceChains[{1, 2, x, 6, 7, y, 11, 12, z, 16, 17},
{3, 4, x, 8, 9, y, 13, 14, z, 18, 19}]
Out[8]= {{1, 2, x, 6, 7, y, 11, 12, z, 16, 17},
{1, 2, x, 6, 7, y, 11, 12, z, 18, 19},
{1, 2, x, 6, 7, y, 13, 14, z, 16, 17},
{1, 2, x, 6, 7, y, 13, 14, z, 18, 19},
{1, 2, x, 8, 9, y, 11, 12, z, 16, 17},
{1, 2, x, 8, 9, y, 11, 12, z, 18, 19},
{1, 2, x, 8, 9, y, 13, 14, z, 16, 17},
{1, 2, x, 8, 9, y, 13, 14, z, 18, 19},
{3, 4, x, 6, 7, y, 11, 12, z, 16, 17},
{3, 4, x, 6, 7, y, 11, 12, z, 18, 19},
{3, 4, x, 6, 7, y, 13, 14, z, 16, 17},
{3, 4, x, 6, 7, y, 13, 14, z, 18, 19},
{3, 4, x, 8, 9, y, 11, 12, z, 16, 17},
{3, 4, x, 8, 9, y, 11, 12, z, 18, 19},
{3, 4, x, 8, 9, y, 13, 14, z, 16, 17},
{3, 4, x, 8, 9, y, 13, 14, z, 18, 19}}
Outer can be used instead of Distribute, but there are a couple slight
complications such as making sure it doesn't delve beyond level 1 in
lists, and flattening to the correct level at the end.
Robby Villegas
-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/ Now offering spam-free web-based newsreading