5
$\begingroup$

From list like:

{1, 2, 3, 4, 5, 6, 20, 21, 22, 23, 24, 25, 26, 27, 28, 100, 101, 102, 103, 104}

I need to pick position of number that is greatest in continuous array segment that I point in. e.g. I pointing to number 22, so some function must return 28 and it's position. Because 28 is greatest in range 20-28. Please help.

$\endgroup$
  • $\begingroup$ How to you define the segments? $\endgroup$ – MarcoB Jun 7 '16 at 21:54
  • $\begingroup$ Yes, you are right. This is right question. I have no idea in which direction to define some things, because I don't know all elegant ways and tools for solution in mathematica. But in this case segment can be defined as range in list, in which neighbouring elements does not differ more than 1.0. HM.. in Phylosophy and mathematics we can describe everything. But I only looking for elegant way in Mathematica of doing this. :) $\endgroup$ – Dragutin Jun 7 '16 at 22:01
  • 1
    $\begingroup$ Are the lists large? Are you doing searches many times against the same target? $\endgroup$ – ciao Jun 7 '16 at 23:36
  • $\begingroup$ List is about 2000-3000 elements, 10-20 'segments'. Task is intensive repetitive on different lists. $\endgroup$ – Dragutin Jun 8 '16 at 13:32
  • $\begingroup$ Thank you very much for replies, that are very helpful for me. But now, I have next similar problem. The case is as original one, but in case if I chose number that is not from some 'continuous' range, but is 'beetween0 two ranges, eg. number 10, is between ranges 1-6 and 20-28. In that case function I'm looking for must return smallest number from range that is greater than selected number. In this case function will return 20. In case, if I choose number within the range, then the function will return as usual, greatest number within this range. $\endgroup$ – Dragutin Jun 13 '16 at 19:37
6
$\begingroup$
 maxNumAndPos[l_,n_]:=Module[{g=RelationGraph[#2-#1==1&,l],num},
                 {num=Max@VertexOutComponent[g,n],VertexIndex[g,num]}]

Usage:

maxNumAndPos[list, 20]

{28, 15}


Explanation

Get the unconnetcted graph's vertices whose degree differ 1 each other.

g=RelationGraph[#2-#1==1&,list,VertexLabels->"Name"]

http://o8aucf9ny.bkt.clouddn.com/2016-06-09-07-59-58.png

Then get the max out component of vertex and its index

Max@VertexOutComponent[g, 20]

28

VertexIndex[g, 28]

15

$\endgroup$
8
$\begingroup$

EDIT : Added Position of endOfSeq

Split the list where ever the difference is greater than one. Select the sublist containing the pointer. Take the last element of the selected sublist.

list = {1, 2, 3, 4, 5, 6, 20, 21, 22, 23, 24, 25, 26, 27, 28, 100, 101, 102, 
   103, 104};

endOfSeq[pointer_] := Module[{val =
    Select[Split[list, #2 - #1 == 1 &], 
      MemberQ[#, pointer] &][[1, -1]]},
  {val, Position[list, val][[1]]}]

endOfSeq[22]

(*  {28, {15}}  *)
$\endgroup$
4
$\begingroup$

Here's a method if the questions in my comment question are affirmative:

p2[l_, arg_] := Module[{a, p, m, vi},
  a = Unitize[Append[Differences[l], 2] - 1];
  p = Pick[Range@Length@l, a, 1];
  m = l[[p]];
  vi = Length[p] + 1 - Reverse[Accumulate@Reverse@a];
  If[arg === True, 
   AssociationThread[l -> Transpose[{m[[vi]], p[[vi]]}]], 
   With[{pp = Pick[vi, l, arg]}, Join[m[[pp]], p[[pp]]]]]];

Usage:

For a single-shot query (say if target list is changing often or between calls):

result=p2[list,key]

where list, key are your list and the element to search. If element not present, returns empty list, else returns two element list of high value and corresponding position.

For multiple calls anticipated against some static list:

(* do *once* per static list *)
myFn=p2[list,True]; 

(* use returned object for repeated searches on that list *)
result=myFn[key]

Returns same two element list of high and position for valid key, else Missing["KeyAbsent", ...] for an invalid element.

Using

list = Flatten[Range @@@ Partition[Sort@RandomInteger[{1, 50000}, 100], 2]];

to generate test data, this seems to be quite quick for single-shot use, and can build the lookup function quite quickly, which is then of course orders of magnitude faster for multiple searches on a static list.

If your lists are tiny and/or only searched a few times, not worth the complexity, but if not, might save you some processing time.

Update: For the second part in you comment, here's a q-n-d helper function to do that:

p2h[l_, arg_] := 
  Module[{i}, If[MemberQ[l, arg], p2[l, arg], i = Pick[Range@Length@l, UnitStep[l - arg], 1];
                 If[i == {}, {}, p2[l, l[[i[[1]]]]]]]];

This calls the original function (one-shots) for existing elements, or crafts the appropriate call to the original function for "between" elements.

N.b: This does not take advantage of pre-calculation in the original function, but from your comments it appears lists are not static, so probably irrelevant. The ranges are considered unbounded on left (so calling with any value less that the minimum of the target returns the first maximum) and bounded on the right (so calling with a value greater than any in the list returns the empty list - there is no "...smallest number from range that is greater than selected number").

There's probably a more efficient way to tie these together, don't have time right now. In the future, keep in mind it's best to state the whole problem at once, if possible, versus trickle-changes.

$\endgroup$
3
$\begingroup$

I propose a method based on my answers to these related questions:

Here are two reusable functions that you may apply:

convert[a_List] :=
  {##, Accumulate[#2 - # + 1]} & @@
    { a[[ Prepend[# + 1, 1] ]], a[[ Append[#, -1] ]] } & @
      SparseArray[Differences @ a, Automatic, 1]["AdjacencyLists"]

Needs["Combinatorica`"] // Quiet

find[{i_List, m_List, p_List}] @ val_?NumberQ :=
  {m, p}[[ All, ⌊ BinarySearch[i, val] ⌋ ]]

convert converts your list into interval form and includes a list of positions:

dat = {1, 2, 3, 4, 5, 6, 20, 21, 22, 23, 24,
       25, 26, 27, 28, 100, 101, 102, 103, 104};

new = convert @ dat
{{1, 20, 100}, {6, 28, 104}, {6, 15, 20}}

find takes this data and a value and find the end of that segment and its position:

find[new] @ 22
{28, 15}

Notes:

  • convert is very fast, and the new format contains the information needed to reconstruct the original so it can replace it if desired.

  • find is based on the fairly slow BinarySearch function in the Combinatorica package but faster implementations are available as described in the second post referenced above.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.