Re: Re: Pattern matching more than once
- To: mathgroup@smc.vnet.net
- Subject: [mg12170] Re: [mg12108] Re: Pattern matching more than once
- From: "Jürgen Tischer" <jtischer@pitagoras.univalle.edu.co>
- Date: Fri, 1 May 1998 03:08:24 -0400
Nice, Robby, this Distribute. I hope you like this melange:
SpliceChains[li1_,li2_]:=
Union[Flatten/@Distribute[Transpose[Split[#,!MemberQ[Intersection[li1,li2],#
1]&]&/@ {li1,li2}],List,List]]
Jürgen
-----Original Message-----
From: villegas@wolfram.com <villegas@wolfram.com> To:
mathgroup@smc.vnet.net
Subject: [mg12170] [mg12108] Re: Pattern matching more than once
>
>> 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
>