Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
1998
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 1998

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

Search the Archive

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



  • Prev by Date: Please help: InverseLaplaceTransform
  • Next by Date: Display and HTMLSave
  • Prev by thread: Re: Pattern matching more than once
  • Next by thread: Re: Pattern matching more than once