Longest and Shortest won't work in ReplaceList?

Wjx just a moment. 2 answers, 0 views
list-manipulation pattern-matching design-patterns

I'm trying to make a pattern that's easy to preceive by human but hard to write out by Mathematica when I came across this problem. (Check the original problem here)

Let's check this simple case:

I've got a list {5,1,2,1,2,1,2,1,2,4,3,3,3,3,3,3,10} and I would like to find out all the recurrence period and the sequence before and after them. So, if you have a brief match with your brain, you can know there are two possible matchs:{5,1,2,1,2,1,2,1,2,4,3,3,3,3,3,3,10} and {5,1,2,1,2,1,2,1,2,4,3,3,3,3,3,3,10}.

It's okay if I only want to find out one of them, using the following code will work as desired:

Replace[{5, 1, 2, 1, 2, 1, 2, 1, 2, 4, 3, 3, 3, 3, 3, 3, 10}, 
{Shortest[pre___, 3], Longest[Repeated[Shortest[rep__, 1], {2, Infinity}]], Shortest[inc___, 2]}
:> {{pre}, {rep}, {inc}}]

(*{{5}, {1, 2}, {4, 3, 3, 3, 3, 3, 3, 10}}*)

But If I want to find out all of them, it's not quite direct as the following code which simply change Replace to ReplaceList will not work:

r1=
ReplaceList[{5, 1, 2, 1, 2, 1, 2, 1, 2, 4, 3, 3, 3, 3, 3, 3, 10}, 
{Shortest[pre___, 3], Longest[Repeated[Shortest[rep__, 1], {2, Infinity}]], Shortest[inc___, 2]}
:> {{pre}, {rep}, {inc}}]

The result is incredibly long and included all the possible match and ignored all the Shortest or Longest:

r2 = ReplaceList[{5, 1, 2, 1, 2, 1, 2, 1, 2, 4, 3, 3, 3, 3, 3, 3, 10},
{pre___, Repeated[rep__, {2, Infinity}], inc___} :> {{pre}, {rep}, {inc}}]

Sort@r1==Sort@r2

(*True*)

This is, of course, not the desired result, but how can I set the pattern-matcher to do this work? And are there any reason that ReplaceList will ignore all these Shortest and Longest? Any help or any other approach other than my way is appreciated. But of course, the final goal is to solve this using ReplaceList or similar functions.

2 Answers


Mr.Wizard 08/01/2016.

To me this is an interesting problem, however I think the question is a misguided one.

Briefly: Longest and Shortest only change the order in which an expression is searched for a match. They are not filters that eliminate potential matches.

As noted in the documentation:

If no explicit Shortest or Longest is given, ordinary expression patterns are normally effectively assumed to be Shortest[p], while string patterns are assumed to be Longest[p].

If several Shortest objects occur in the same expression, those that appear first are given higher priority to match shortest sequences.

If several Longest objects occur in the same expression, those that appear first are given higher priority to match longest sequences.

Realize then that all patterns already have a length priority as established by their type and position.

For example this always gives the same output:

Replace[{1, 2, 3, Pi, 4.4, 1/5}, {a__Integer, b__?NumericQ} :> {{a}, {b}}]
{{1}, {2, 3, π, 4.4, 1/5}}

This pattern is the same as {Shortest[a__Integer], Shortest[b__?NumericQ]}. The priorities determine the order in which different alignments are tried and the first match is returned. This process is always the same therefore the result is always the same. Using a different length priority results in a different search order and (possibly) a different match but it is always deterministic.

So what happens when we use ReplaceList? The same priorities are respected but now the pattern engine keeps looking for matches rather than stopping with the first one found, and all matches are returned in the order searched. Compare these outputs:

expr = {1, 2, 3, Pi, 4.4, 1/5};

ReplaceList[expr, {a__Integer, b__?NumericQ} :> {{a}, {b}}]

ReplaceList[expr, {Longest[a__Integer], b__?NumericQ} :> {{a}, {b}}]
{{{1}, {2, 3, π, 4.4, 1/5}}, {{1, 2}, {3, π, 4.4, 1/5}}, {{1, 2, 3}, {π, 4.4, 1/5}}}

{{{1, 2, 3}, {π, 4.4, 1/5}}, {{1, 2}, {3, π, 4.4, 1/5}}, {{1}, {2, 3, π, 4.4, 1/5}}}

Note that Longest is not ignored; it changes the search order, as it always does.

While the order is different the set of matches is the same; it has to be because the same input expression and the same patterns are used in each case. All that changes is the order in which the alignments are checked.

To illustrate this in different way without ReplaceList we can use a failed condition to echo back matching alignments.

expr /. {a__Integer, b__?NumericQ} /; Print[{a}, " ", {b}] -> Null;

{1} {2,3,π,4.4,1/5}

{1,2} {3,π,4.4,1/5}

{1,2,3} {π,4.4,1/5}

expr /. {Longest[a__Integer], b__?NumericQ} /; Print[{a}, " ", {b}] -> Null;

{1,2,3} {π,4.4,1/5}

{1,2} {3,π,4.4,1/5}

{1} {2,3,π,4.4,1/5}


Edmund 07/05/2016.

As a workaround, you can use Select to filter down the results of ReplaceList to the set you want by using MatchQ and SequencePosition.

v = {5, 1, 2, 1, 2, 1, 2, 1, 2, 4, 3, 3, 3, 3, 3, 3, 10};
rl = ReplaceList[v, {Shortest[pre___, 3], 
    Longest[Repeated[Shortest[rep__, 1], {2, Infinity}]], 
    Shortest[inc___, 2]} :> {{pre}, {rep}, {inc}}];

Then

Select[
 Not[MatchQ[#[[2]], {Repeated[x__, {2, Infinity}]}]] &&
 Max@Flatten@SequencePosition[#[[1]], #[[2]]] != Length@#[[1]] && 
 Min@Flatten@SequencePosition[#[[3]], #[[2]]] != 1 &
]@rl

(*
{{{5}, {1, 2}, {4, 3, 3, 3, 3, 3, 3, 10}}, 
 {{5, 1}, {2, 1}, {2, 4, 3, 3, 3, 3, 3, 3, 10}},
 {{5, 1, 2, 1, 2, 1, 2, 1, 2, 4}, {3}, {10}}}
*)

The ReplaceList cases of interest are those with no repeated sequences in rep__, have pre___ that does not end in rep__'s pattern, and have inc___ that does not begin in rep__'s pattern. Note that a third possible match has been found that was not initially considered by eye.

Hope this helps.


HighResolutionMusic.com - Download Hi-Res Songs

1 BLACKPINK

Kiss And Make Up flac

BLACKPINK. 2018. Writer: Soke;Kny Factory;Billboard;Chelcee Grimes;Teddy Park;Marc Vincent;Dua Lipa.
2 Martin Garrix

Waiting For Tomorrow flac

Martin Garrix. 2018. Writer: Pierce Fulton;Mike Shinoda;Martijn Garritsen;Brad Delson.
3 John Legend

Written In The Stars flac

John Legend. 2018. Writer: Kiana Brown;Santoy;Kevin White;Mike Woods;MZMC;The Heavy Group;Rice N' Peas.
4 Alan Walker

Diamond Heart flac

Alan Walker. 2018. Writer: Alan Walker;Sophia Somajo;Mood Melodies;James Njie;Thomas Troelsen;Kristoffer Haugan;Edvard Normann;Anders Froen;Gunnar Greve;Yann Bargain;Victor Verpillat;Fredrik Borch Olsen.
5 Bradley Cooper

Shallow flac

Bradley Cooper. 2018. Writer: Andrew Wyatt;Anthony Rossomando;Mark Ronson;Lady Gaga.
6 Martin Garrix

Access flac

Martin Garrix. 2018. Writer: Martin Garrix.
7 Cardi B

Taki Taki flac

Cardi B. 2018. Writer: Bava;Juan Vasquez;Vicente Saavedra;Jordan Thorpe;DJ Snake;Ozuna;Cardi B;Selena Gomez.
8 Martin Garrix

Yottabyte flac

Martin Garrix. 2018. Writer: Martin Garrix.
9 Post Malone

Sunflower flac

Post Malone. 2018. Writer: Louis Bell;Billy Walsh;Carter Lang;Swae Lee;Post Malone.
10 Lady Gaga

I'll Never Love Again flac

Lady Gaga. 2018. Writer: Benjamin Rice;Lady Gaga.
11 Bradley Cooper

Always Remember Us This Way flac

Bradley Cooper. 2018. Writer: Lady Gaga;Dave Cobb.
12 Mako

Rise flac

Mako. 2018. Writer: Riot Music Team;Mako;Justin Tranter.
13 Dyro

Latency flac

Dyro. 2018. Writer: Martin Garrix;Dyro.
14 Avril Lavigne

Head Above Water flac

Avril Lavigne. 2018. Writer: Stephan Moccio;Travis Clark;Avril Lavigne.
15 Sia

I'm Still Here flac

Sia. 2018. Writer: Sia.
16 Halsey

Without Me flac

Halsey. 2018. Writer: Halsey;Delacey;Louis Bell;Amy Allen;Justin Timberlake;Timbaland;Scott Storch.
17 Deep Chills

Run Free flac

Deep Chills. 2018.
18 Julia Michaels

There's No Way flac

Julia Michaels. 2018. Writer: Ian Kirkpatrick;Justin Tranter;Julia Michaels;Lauv.
19 Rita Ora

Let You Love Me flac

Rita Ora. 2018. Writer: Rita Ora.
20 Zara Larsson

Ruin My Life flac

Zara Larsson. 2018. Writer: Delacey;Michael Pollack;Stefan Johnson;Jordan Johnson;Sermstyle;Jackson Foote.

Language

Popular Tags