Skip to main content
added 95 characters in body
Source Link
Roman
  • 50k
  • 2
  • 57
  • 132

Find the required list: a slow method that uses very powerful operators, in the hope of teaching something to someone:

Find the required list:

Find the required list: a slow method that uses very powerful operators, in the hope of teaching something to someone:

added 2799 characters in body
Source Link
Roman
  • 50k
  • 2
  • 57
  • 132

commented version of the code

SequencePosition finds all sublists of LL that match the pattern of $\{e, \ldots, f\ge 2e\}$, where the dots stand for zero or more other numbers (a BlankNullSequence ___). The option Overlaps -> All instructs to return all matches: long ones and short ones, even if they overlap:

SequencePosition[LL, {e_, ___, f_} /; f >= 2 e, Overlaps -> All]

{{2, 20}, {2, 19}, {2, 17}, {2, 15}, {2, 14}, {2, 11}, {2, 10}, {2, 6}, {3, 20}, {3, 19}, {3, 18}, {3, 17}, {3, 16}, {3, 15}, {3, 14}, {3, 13}, {3, 12}, {3, 11}, {3, 10}, {3, 9}, {3, 8}, {3, 7}, {3, 6}, {3, 5}, {3, 4}, {4, 20}, {4, 19}, {4, 18}, {4, 17}, {4, 16}, {4, 15}, {4, 14}, {4, 13}, {4, 11}, {4, 10}, {4, 8}, {4, 7}, {4, 6}, {5, 20}, {5, 19}, {5, 18}, {5, 17}, {5, 16}, {5, 15}, {5, 14}, {5, 13}, {5, 12}, {5, 11}, {5, 10}, {5, 9}, {5, 8}, {5, 7}, {5, 6}, {7, 20}, {7, 19}, {7, 17}, {7, 14}, {7, 11}, {7, 10}, {8, 20}, {8, 19}, {8, 17}, {8, 15}, {8, 14}, {8, 13}, {8, 11}, {8, 10}, {9, 20}, {9, 19}, {9, 18}, {9, 17}, {9, 16}, {9, 15}, {9, 14}, {9, 13}, {9, 12}, {9, 11}, {9, 10}, {12, 20}, {12, 19}, {12, 18}, {12, 17}, {12, 16}, {12, 15}, {12, 14}, {12, 13}, {13, 20}, {13, 19}, {13, 18}, {13, 17}, {13, 15}, {13, 14}, {15, 19}, {15, 17}, {16, 20}, {16, 19}, {16, 18}, {16, 17}, {18, 20}, {18, 19}}

Each one of these matches is returned as a pair of indices, giving the start and end position of the match in the original list LL.

We GroupBy these matches by start position (First) and keep only the end positions (Last); then for each of the found groups we calculate the minimum (Min) of these end positions, which gives us the nearest-to-the-right end position satisfying the pattern constraint:

GroupBy[%, First -> Last, Min]

<|2 -> 6, 3 -> 4, 4 -> 6, 5 -> 6, 7 -> 10, 8 -> 10, 9 -> 10, 12 -> 13, 13 -> 14, 15 -> 17, 16 -> 17, 18 -> 19|>

This output is in the form of an Association. To continue, we Lookup each start position (Range[Length[LL]]) in this association to find the smallest end position. If none is found, return {}:

Lookup[%, Range[Length[LL]], {}]

{{}, 6, 4, 6, 6, {}, 10, 10, 10, {}, {}, 13, 14, {}, 17, 17, {}, 19, {}, {}}


commented version of the code

SequencePosition finds all sublists of LL that match the pattern of $\{e, \ldots, f\ge 2e\}$, where the dots stand for zero or more other numbers (a BlankNullSequence ___). The option Overlaps -> All instructs to return all matches: long ones and short ones, even if they overlap:

SequencePosition[LL, {e_, ___, f_} /; f >= 2 e, Overlaps -> All]

{{2, 20}, {2, 19}, {2, 17}, {2, 15}, {2, 14}, {2, 11}, {2, 10}, {2, 6}, {3, 20}, {3, 19}, {3, 18}, {3, 17}, {3, 16}, {3, 15}, {3, 14}, {3, 13}, {3, 12}, {3, 11}, {3, 10}, {3, 9}, {3, 8}, {3, 7}, {3, 6}, {3, 5}, {3, 4}, {4, 20}, {4, 19}, {4, 18}, {4, 17}, {4, 16}, {4, 15}, {4, 14}, {4, 13}, {4, 11}, {4, 10}, {4, 8}, {4, 7}, {4, 6}, {5, 20}, {5, 19}, {5, 18}, {5, 17}, {5, 16}, {5, 15}, {5, 14}, {5, 13}, {5, 12}, {5, 11}, {5, 10}, {5, 9}, {5, 8}, {5, 7}, {5, 6}, {7, 20}, {7, 19}, {7, 17}, {7, 14}, {7, 11}, {7, 10}, {8, 20}, {8, 19}, {8, 17}, {8, 15}, {8, 14}, {8, 13}, {8, 11}, {8, 10}, {9, 20}, {9, 19}, {9, 18}, {9, 17}, {9, 16}, {9, 15}, {9, 14}, {9, 13}, {9, 12}, {9, 11}, {9, 10}, {12, 20}, {12, 19}, {12, 18}, {12, 17}, {12, 16}, {12, 15}, {12, 14}, {12, 13}, {13, 20}, {13, 19}, {13, 18}, {13, 17}, {13, 15}, {13, 14}, {15, 19}, {15, 17}, {16, 20}, {16, 19}, {16, 18}, {16, 17}, {18, 20}, {18, 19}}

Each one of these matches is returned as a pair of indices, giving the start and end position of the match in the original list LL.

We GroupBy these matches by start position (First) and keep only the end positions (Last); then for each of the found groups we calculate the minimum (Min) of these end positions, which gives us the nearest-to-the-right end position satisfying the pattern constraint:

GroupBy[%, First -> Last, Min]

<|2 -> 6, 3 -> 4, 4 -> 6, 5 -> 6, 7 -> 10, 8 -> 10, 9 -> 10, 12 -> 13, 13 -> 14, 15 -> 17, 16 -> 17, 18 -> 19|>

This output is in the form of an Association. To continue, we Lookup each start position (Range[Length[LL]]) in this association to find the smallest end position. If none is found, return {}:

Lookup[%, Range[Length[LL]], {}]

{{}, 6, 4, 6, 6, {}, 10, 10, 10, {}, {}, 13, 14, {}, 17, 17, {}, 19, {}, {}}

deleted 2 characters in body
Source Link
Roman
  • 50k
  • 2
  • 57
  • 132

Using @MarcoB's example,

SeedRandom[1234];
LL = RandomReal[{-100, 100}, 20]
(*    {75.3217, 4.39285, -82.7553, -24.4174, -97.6711,
       85.4532, 8.75135, -4.13367, -50.9302, 51.9792,
       96.9986, -56.591, -8.19656, 76.9458, 16.7709,
       -47.2054, 83.912, -15.233, 97.4581, 17.5885}    *)

Find the required list:

Lookup[GroupBy[SequencePosition[LL, {e_, ___, f_} /; f >= 2 e, Overlaps -> All],
               First -> Last, Min], Range[Length[LL]], {}]
 
(*    {{}, 6, 4, 6, 6, {}, 10, 10, 10, {}, {}, 13, 14, {}, 17, 17, {}, 19, {}, {}}    *)

If only there was a FirstSequencePosition command, this would be a lot simpler.

Using @MarcoB's example,

SeedRandom[1234];
LL = RandomReal[{-100, 100}, 20]
(*    {75.3217, 4.39285, -82.7553, -24.4174, -97.6711,
       85.4532, 8.75135, -4.13367, -50.9302, 51.9792,
       96.9986, -56.591, -8.19656, 76.9458, 16.7709,
       -47.2054, 83.912, -15.233, 97.4581, 17.5885}    *)

Find the required list:

Lookup[GroupBy[SequencePosition[LL, {e_, ___, f_} /; f >= 2 e, Overlaps -> All],
               First -> Last, Min], Range[Length[LL]], {}]
 
(*    {{}, 6, 4, 6, 6, {}, 10, 10, 10, {}, {}, 13, 14, {}, 17, 17, {}, 19, {}, {}}    *)

If only there was a FirstSequencePosition command, this would be a lot simpler.

Using @MarcoB's example,

SeedRandom[1234];
LL = RandomReal[{-100, 100}, 20]
(*    {75.3217, 4.39285, -82.7553, -24.4174, -97.6711,
       85.4532, 8.75135, -4.13367, -50.9302, 51.9792,
       96.9986, -56.591, -8.19656, 76.9458, 16.7709,
       -47.2054, 83.912, -15.233, 97.4581, 17.5885}    *)

Find the required list:

Lookup[GroupBy[SequencePosition[LL, {e_, ___, f_} /; f >= 2 e, Overlaps -> All],
               First -> Last, Min], Range[Length[LL]], {}]
(*    {{}, 6, 4, 6, 6, {}, 10, 10, 10, {}, {}, 13, 14, {}, 17, 17, {}, 19, {}, {}}    *)

If only there was a FirstSequencePosition command, this would be a lot simpler.

Source Link
Roman
  • 50k
  • 2
  • 57
  • 132
Loading