/ sultan problem.
/ Assume we are choosing three elements

/ get the first one that's higher than the first i
/ and hasn't yet been chosen
/ or if none then the last element
/ UNUSED
gethigher:{[i; seq]
  i: i | chosen / if chosen is larger than the cutoff, then choose that
  m: |/ seq[!i]
  rest: i _ seq
  ii: & m < rest
  if[0=#ii; :*|seq]
  chosen:: (*ii) + i
  :rest[*ii]
}

/ get the first one that's higher than the first i
/ and hasn't yet been chosen
/ or if none then the last element
/ Let's say that the threshes are 20 40 60.
/ Let's say that the first one higher than the first 20 is index 24.
/ The next higher than the first 20 is index 27
/ So, we will look next for something greater than 40 and greater
/ than anything in the first 40.
/ If we don't find anything, we'll return seq[24]
/ If we do, then we'll find seq of whatever
gethighernew:{[trip; seq]
  k: 0
  best: -1
  chosen: 0
  while[k < (#trip) 
	i: trip[k]
	i: i | chosen / max of chosen location and i
  	m: |/ seq[!i] / take max of first i
  	rest: i _ seq / everything remaining
  	ii: & m < rest
  	if[(0=#ii) & (0 = chosen); :&/seq] / best was at the beginning
  	if[(0=#ii) & (0 < chosen); :seq[chosen]] / we found a good one in m
  	chosen: (*ii) + i / otherwise, we keep going till the very end
	k+: 1
   ]
  if[0 < chosen; :seq[chosen]]
  :&/seq
}

/ choosing three elements
gentrips:{[N]
  x: ,/ (,/(!N) ,/:\: (!N)) ,/:\: (!N)
  ii: & ((x[;0]) < (x[;1])) & ((x[;1]) < (x[;2]))
  :x[ii]
}



gentripssingle:{[N] :,:' !N}

genhex:{[N]
  x: ,/ (,/(!N) ,/:\: (!N)) ,/:\: (!N)
  x: ,/ x ,/:\: x
  ii: & sorted'x
  :x[ii]
}

sorted:{[list] (< list) ~ (!#list)}

/ gentrips: genhex

testsuccess:{[N;trip]
  numsuccess: 0
  do[numtests
	seq: N _draw - N
	/ flag: (N-1) = |/gethigher[;seq]'trip
	flag: (N-1) = gethighernew[trip;seq]
	/ if[flag & (4 < &/trip) ; !-11]
	numsuccess+: flag
  ]
  :numsuccess % numtests
}

/ DATA

N: 1000 / number of "daughters"
numtests: 10000000 / number of tests per triple
numtests: 10000 / number of tests per triple

/ EXECUTE
n: _gtime _t
v: ((n[1] ! 101 ) _draw N)
trips: ,/ (,/(140 + !3) ,/:\: (315+!3)) ,/:\: (647+!5)
/ trips:  gentrips[N] / that is for full search
/ trips: (9 30 61; 14 28 57; 14 22 38)
/ trips: (9 30 61; 14 28 57; 14 22 38)
trips:(6 25 49; 10 42 60; 12 39 57; 5 26 52; 12 45 77; 14 41 69; 18 54 71; 19 39 67; 14 22 38)
trips: 10 * trips


x: testsuccess[N]'trips
max: |/x
ii: & x > (max - 0.12)
` 0: ,("Number of daughters: "), $N
` 0: ,("max fraction is: "),$max
(trips[ii],'x[ii])
z: (trips[ii],'x[ii])
jj: > x[ii]
z[jj][!(50 & #ii)]