Hello
Randomness in selection and diversity in selection are two things. For instance, when you're planning lunch menu and don't want to have the same menu in a row or in a short period of time, you need to control the menu selection probability based upon the selection history.
I have played about with this and come to something like the following script.
Have fun.
H
--APPLESCRIPT
property qq : {} -- selection history, stored in right-to-left order (left end is the latest)
set aa to "abcde"'s characters
diverse_selection(aa, {memory:0.8, penalty:0.7})
on diverse_selection(aa, opts)
(*
list aa : source list of entities
record opts : {memory: a, penalty: b}
(real) a : memory coefficient in [0, 1); default a = 0.7
(real) b : penalty coefficient in [0, 1); default b = 0.6
(property qq : selection history, stored in right-to-left order (left end is the latest))
*)
(*
Given
entities P = {i : i = 1..m},
last-k selection history Q = {q_j : j = 1..k, k <= n, q_j in P}, the greater j denotes the older;
entity i's next selection weight w_i is calculated by
w_i = 1 - c * (∑ (a ^ j) : for all j such that q_j = i) / ak
where
ak = ∑ (a ^ j) : j = 1..k
= a * (1 - a ^ k) / (1 - a)
a is memory coefficient in [0, 1)
b is penalty coefficient in [0, 1)
c = b * bx
bx = (∑ (a ^ j) : j = 1..m) / a ^ m
= a * (1 - a ^ m) / (1 - a) / a ^ m
and its selection probability s_i is calculated by
s_i = w_i / (∑ w_j : for all j in P and w_j > 0), if w_i > 0;
= 0, otherwise
*)
script o
property pp : aa -- entities
property m : count my pp -- number of entities
property n : m * 3 -- max length of history
property op : opts & {memory:0.7, penalty:0.6}
property a : op's memory -- memory coefficient : [0, 1)
property b : op's penalty -- penalty coefficient : [0, 1)
property bx : a * (1 - a ^ m) / (1 - a) / (a ^ m) -- penalty supremum (not-inclusive) to guarantee at least one selection
property c : b * bx -- penalty : [0, bx)
property cc : {} -- penalty weight for entities considering history
property ww : {} -- selection weight for entities considering history
if a < 0 or a ≥ 1 then error "memory coefficient must be in [0, 1) but given: " & a number 8000
if b < 0 or b ≥ 1 then error "penalty coefficient must be in [0, 1) but given: " & b number 8000
if (count my qq) > n then set qq to my qq's items 1 thru n
set k to count my qq
repeat m times
set my cc's end to 0
set my ww's end to 0
end repeat
set ak to a * (1 - a ^ k) / (1 - a) -- an (penalty weight normaliser) = ∑ (a ^ j) : j = 1..k
repeat with j from 1 to k
set i to my qq's item j
set my cc's item i to (my cc's item i) + (a ^ j) / ak -- cc[i] = ∑ (a ^ j) / ak : i = qq[j]
end repeat
repeat with i from 1 to count my ww
set my ww's item i to 1 - c * (my cc's item i)
end repeat
set wm to 0
repeat with w in my ww
set w to w's contents
if w > 0 then set wm to wm + w -- wm (selection weight normaliser) = ∑ w : w > 0
end repeat
if wm = 0 then error "internal error: penalty is likely too large." number 8001
set r to random number -- [0, 1]
set s to 0 -- selected index
set t to 0 -- current threashold [0, 1]
repeat with i from 1 to count my ww
set w to my ww's item i
if w > 0 then set t to t + w / wm
if r ≤ t then
set s to i
exit repeat
end if
end repeat
if s = 0 then set s to -1
set p to my pp's item s
set my qq's beginning to s
return {p, s, qq, {a:a, b:b, c:c, bx:bx, ww:ww, cc:cc, wm:wm, r:r}} -- for test
return p
end script
tell o to run
end diverse_selection
--END OF APPLESCRIPT
