Produce Random numbers from a list with exceptions

As for your first comment, I have provided AppleScript script for those who are not familiar with shell scripting.

As for your second comment, my script genenates schedules so as to minimise the days where lessons are assinged. If the total days of lessons is not divisible by the value of SLOTS, the residue will be assigned to a day with some of which slots left blank, which is logical consequence. If you want every assinged day has its full slots being filled, you need to specify number of days so that the total is divisible by SLOTS, that is 2 in the example case.

To try my script or not is up to the reader and basically is not my concern. I just asked the original poster because I thought s/he's wasting time. For me the problems have been already solved reasoably.

H

Hi Hiroto,

I'm at a bit of a loss here.

Some questions:

"my script generates schedules so as to minimise the days where lessons are assigned."

Do you mean 'to minimise the number of days on which each lesson is assigned'?

"If the total days of lessons is not divisible by the value of SLOTS, the residue will be assigned to a day with some of which slots left blank, which is logical consequence."

How does this apply to the described issue: Total days of lessons: 30, Slots: 2. 30/2 = 15, with no reminder.

Regarding the script (with the Applescript envelope):

I have pasted the script into the script editor and run it, leaving all listed parameters unchanged The result window reports the result as "" (including the quotation marks.

I reran the script with DAYS changed from DAYS = (1..7) to DAYS = (1..30)

The reported result was the same. ( "" )

Assuming there is output from the script, where is it sent/placed?

Is there any setup required before running the script?

AppleScript Editor v 2.5.1

AppleScript v 2.2.4

OS X v10.8.5

Regards,

Barry

I reread your second comment and noticed that you're dealing with a different problem from the one I've treated.

But I really don't understand why those specified numbers of days per lesson is to be treated as the minimum number of days. The original poster has never stated that they are the minimum numbers of days to be assinged. Neither have I assumed that. All of my spreadsheet solutions and scripting solution treat the specified numbers of days per lesson as the exact numbers of days to be assinged.

H

Hello Barry,

Firstly the script of mine puts the result in the clipboard and not in the result window. So to use it, you copy the source range in Numbers to the clipboard, run the script and paste the result (now in the clipboard) to the destination range in Numbers.

As for my statement:

"my script generates schedules so as to minimise the days where lessons are assigned."

it means to minimise the total days where any lesson is assinged. This is to assign as many lessons as possible to one day where any lesson is assigned.

As for my statement:

"If the total days of lessons is not divisible by the value of SLOTS, the residue will be assigned to a day with some of which slots left blank, which is logical consequence."

it is to explain why there's a day in each schedule where only one slot is assigned in my examples posted on Jan 5. (In the original problem where lesson number is 8, number of days per lesson is 5 and slots per day is 2, the total days of lesson is 8 * 5 = 40 and 40 mod 2 = 0, which means there's no day where only one slot is assigned.)

But as I wrote in another reply to SG, I have misunderstood his second comment and thus my statement above is not addressing his comment. (He seems to think it is required to fill all of the 60 (= 30 * 2) slots but I have not been treating such problem)

All the best,

Hiroto

Hi Hiroto,

Regarding the script, and results: I was aware that the script results were sent to the clipboard, but after running the script several times yesterday, then pasting to an empty table, I got nothing. Not certain what I did today that I hadn't done at least once yesterday (probably read and follow the directions), but today everything worked.

Everything, including setting a full schedule of 60 lessons (all slots filled) with each lesson repeated a specified number of times. All that's needed is to ensure that the total of the specified repetitions of each lesson is equal to the number of slots to fill.

Regarding minimising the number of days: I don't recall the OP specifying that any days were to be left without lessons. His response to SG, declaring his solution the 'winner' would argue against that interpretation, as SG's solution did include two lessons for every day.

Regarding unfilled slots: Understood. My initial impression was that this comment was referring to the original case, where empty slots occurred, but only in pairs on the same day.

Regarding the specified number of days for each lesson: Starting with the interpretation that every day should have two lessons forces the interpretation that the number of days specified (5 for each lesson) must have been a minimum. Again, the OP's response declaring a "winner" would argue against a different interpretation.

The OP's later request to regard the numbers as actual, rather than minimum (or maximum) suggests he may have initially meant them to be such. Unfortunately, there's been no response from the OP since then regarding the subsequent discussion regarding the consequences of setting absolute values Fortunately, as noted above, the consequences can be avoided with minimal effort.

Based on results, now that I've followed the instructions, I'd say you've achieved a full solution with this script. Congratulations!

Regards,

Barry

Randomness and diversity are two things. My algorithm is based upon randomness of selection which does not consider diversity. Original poster's descritption of the problem states randomness and not diversity.

H

Hi H,

Diversity of all sorts is de rigueur on university campuses here. It's simply assumed to be a requirement.

Hence the original idea of setting a minimum. While still selecting at random, that improves diversity.

Random selection without replacement generally also produces more diversity (i.e., fewer repeated lesson pairs).

Having exact targets, rather than a minimum, all the while ensuring diversity, appears to be a complex problem that chokes my humble script.

SG

Just a supplementary note in case my comment above is not clear enough.

E.g., if we generate 10 random integers in [0, 9] by (quasi) uniform random number generator, we'll get something like the following list of integers, which usually contains duplicates.

9, 2, 5, 2, 5, 3, 7, 2, 3, 4

This demonstates how uniformly random selection does not necessarily yield diverse result.

We can generate diverse list of 10 random integers in [0, 9] by controlling the selection probabilities based upon the selection history or by generating a random permutation of the list of 10 distinct integers in [0, 9], in which cases the probability density of selection of each number differs from that of uniformly distributed random number.

Whilst it is quite possible to generate diverse list, it is a different problem from the original as defined.

H

Here's revised script which added code to shuffle the slots of each day in order to randomise the order of lessons in a day if it matters.

Ruby script in shell:

#!/bin/bash export LC_ALL=en_GB.UTF-8 /usr/bin/ruby -w <<'EOF' - <(pbpaste) | pbcopy # # ARGF : TSV file of fields A B C1 [C2 ...] # A : lesson # B : number of days of lesson # C* : excluded day of lesson # # output : TSV text representing generated schedule D[i,j,k] where # D[i,j,k] denotes lesson assigned to slot j of day i in schedule k; # TSV fields represent tupple (k,j) and TSV record i represents D[i,j,k] # # * schedule is built to minimise the number of days with lessons assigned # * if it fails to generate k'th schedule, D[*,*,k] is left blank # # e.g., # Given input: # DAYS = (1..7), # SLOTS = 2, # SCHEDULES = 5, # TSV = # A B C1 C2 # ------------- # 1 3 5 7 # 2 3 1 3 # 3 3 4 # # output (e.g.): # TSV = # k=1 1 2 2 3 3 4 4 5 5 # j=1 2 1 2 1 2 1 2 1 2 # ------------------------------------- # 1 3 3 3 # 1 2 2 1 3 2 2 3 # 3 1 3 1 3 1 3 1 3 # 1 2 1 2 1 2 2 1 # 2 3 2 3 # 2 3 2 1 1 3 1 2 2 1 # 2 3 # # version : # v0.11 - added code to shuffle slots of each day # DAYS = (1..30) # days for schedule SLOTS = 2 # number of slots per day SCHEDULES = 5 # number of schedules to generate MAXTRIES = 16 # max number of trials for each schedule DEBUG = true # debug flag: true to print debug information to $stderr, false otherwise. def array2text(aa, opts = {}) # array aa : 2d array # hash opts : {:fs => fs, :rs => rs} # string fs : field separator # string rs : record separator fs, rs = {:fs => %[\t], :rs => %[\n]}.merge(opts).values_at(:fs, :rs) return aa.map {|a| a.join(fs) }.join(rs) + rs end def text2array(t, opts = {}) # string t : text representation of 2d array # hash opts : {:fs => fs, :rs => rs} # string fs : field separator # string rs : record separator fs, rs = {:fs => %[\t], :rs => %[\n]}.merge(opts).values_at(:fs, :rs) return t.split(rs).map {|a| a.split(fs, -1)} end def schedule(pp) # array pp : array of [lesson, number of days of lesson, [excluded days of lesson]] # return hash dd : scheduled table { day => [slots] } aa, bb, cc = pp.shuffle!.transpose b_total = bb.inject { |s, b| s + b } b_threshold = b_total / SLOTS rk = 0 while (rk += 1) <= MAXTRIES do dd = DAYS.inject({}) { |h, i| h[i] = []; h } b_assigned = 0 na = catch :not_assigned do while b_total > b_assigned do pp.each do |p| a, b, c = p b.times do ii = dd.keys.select { |d| dd[d].length > 0 } # assinged jj = ii.select { |d| dd[d].length < SLOTS } # assinged and with slot available if ii.length < b_threshold || jj.length == 0 kk = dd.keys.select { |d| ! c.include?(d) && dd[d].length < SLOTS && ! dd[d].include?(a) } else kk = jj.select { |d| ! c.include?(d) && ! dd[d].include?(a) } end throw :not_assigned, a if kk == [] dd[kk[rand(kk.length)]] << a b_assigned += 1 end end end nil end break unless na end if DEBUG $stderr.puts "tries => %d, na => %s\n" % [rk, na.inspect] if na $stderr.puts dd.inspect $stderr.puts array2text(dd.keys.sort.inject([]) { |r, d| r << dd[d].map { |e| '%s*' % e } }) end end dd = DAYS.inject({}) { |h, i| h[i] = []; h } if na dd end aa, bb, *cc = text2array(ARGF.read).transpose bb.map! { |i| i.to_i } cc = cc.transpose.map { |c| c.map { |e| e == "" ? nil : e.to_i }.compact } qq = [] SCHEDULES.times { qq << schedule([aa, bb, cc].transpose) } rr = qq.inject([]) do |q, dd| q << dd.keys.sort.inject([]) { |r, d| r << (e = dd[d].shuffle).fill('', e.size..SLOTS - 1) } end print array2text(rr.transpose) EOF

And AppleScript wrapper, which now prints debug information in result window whilst it puts generated schedules in the clipboard:

--APPLESCRIPT do shell script "/bin/bash -s <<'HUM' - export LC_ALL=en_GB.UTF-8 { /usr/bin/ruby -w <<'EOF' - <(pbpaste) | pbcopy # # ARGF : TSV file of fields A B C1 [C2 ...] # A : lesson # B : number of days of lesson # C* : excluded day of lesson # # output : TSV text representing generated schedule D[i,j,k] where # D[i,j,k] denotes lesson assigned to slot j of day i in schedule k; # TSV fields represent tupple (k,j) and TSV record i represents D[i,j,k] # # * schedule is built to minimise the number of days with lessons assigned # * if it fails to generate k'th schedule, D[*,*,k] is left blank # # e.g., # Given input: # DAYS = (1..7), # SLOTS = 2, # SCHEDULES = 5, # TSV = # A B C1 C2 # ------------- # 1 3 5 7 # 2 3 1 3 # 3 3 4 # # output (e.g.): # TSV = # k=1 1 2 2 3 3 4 4 5 5 # j=1 2 1 2 1 2 1 2 1 2 # ------------------------------------- # 1 3 3 3 # 1 2 2 1 3 2 2 3 # 3 1 3 1 3 1 3 1 3 # 1 2 1 2 1 2 2 1 # 2 3 2 3 # 2 3 2 1 1 3 1 2 2 1 # 2 3 # # version : # v0.11 - added code to shuffle slots of each day # DAYS = (1..30) # days for schedule SLOTS = 2 # number of slots per day SCHEDULES = 5 # number of schedules to generate MAXTRIES = 16 # max number of trials for each schedule DEBUG = true # debug flag: true to print debug information to $stderr, false otherwise. def array2text(aa, opts = {}) # array aa : 2d array # hash opts : {:fs => fs, :rs => rs} # string fs : field separator # string rs : record separator fs, rs = {:fs => %[\\t], :rs => %[\\n]}.merge(opts).values_at(:fs, :rs) return aa.map {|a| a.join(fs) }.join(rs) + rs end def text2array(t, opts = {}) # string t : text representation of 2d array # hash opts : {:fs => fs, :rs => rs} # string fs : field separator # string rs : record separator fs, rs = {:fs => %[\\t], :rs => %[\\n]}.merge(opts).values_at(:fs, :rs) return t.split(rs).map {|a| a.split(fs, -1)} end def schedule(pp) # array pp : array of [lesson, number of days of lesson, [excluded days of lesson]] # return hash dd : scheduled table { day => [slots] } aa, bb, cc = pp.shuffle!.transpose b_total = bb.inject { |s, b| s + b } b_threshold = b_total / SLOTS rk = 0 while (rk += 1) <= MAXTRIES do dd = DAYS.inject({}) { |h, i| h[i] = []; h } b_assigned = 0 na = catch :not_assigned do while b_total > b_assigned do pp.each do |p| a, b, c = p b.times do ii = dd.keys.select { |d| dd[d].length > 0 } # assinged jj = ii.select { |d| dd[d].length < SLOTS } # assinged and with slot available if ii.length < b_threshold || jj.length == 0 kk = dd.keys.select { |d| ! c.include?(d) && dd[d].length < SLOTS && ! dd[d].include?(a) } else kk = jj.select { |d| ! c.include?(d) && ! dd[d].include?(a) } end throw :not_assigned, a if kk == [] dd[kk[rand(kk.length)]] << a b_assigned += 1 end end end nil end break unless na end if DEBUG $stderr.puts \"tries => %d, na => %s\\n\" % [rk, na.inspect] if na $stderr.puts dd.inspect $stderr.puts array2text(dd.keys.sort.inject([]) { |r, d| r << dd[d].map { |e| '%s*' % e } }) end end dd = DAYS.inject({}) { |h, i| h[i] = []; h } if na dd end aa, bb, *cc = text2array(ARGF.read).transpose bb.map! { |i| i.to_i } cc = cc.transpose.map { |c| c.map { |e| e == \"\" ? nil : e.to_i }.compact } qq = [] SCHEDULES.times { qq << schedule([aa, bb, cc].transpose) } rr = qq.inject([]) do |q, dd| q << dd.keys.sort.inject([]) { |r, d| r << (e = dd[d].shuffle).fill('', e.size..SLOTS - 1) } end print array2text(rr.transpose) EOF } 2>&1 HUM" --END OF APPLESCRIPT

Regards,

H

Hiroto wrote:

E.g., if we generate 10 random integers in [0, 9] by (quasi) uniform random number generator, we'll get something like the following list of integers, which usually contains duplicates.

9, 2, 5, 2, 5, 3, 7, 2, 3, 4

This demonstates how uniformly random selection does not necessarily yield diverse result.

Whilst it is quite possible to generate diverse list, it is a different problem from the original as defined.

H

Hi H,

I'm not sure random selection and diversity are necessarily different problems. They're often interlinked. For example, suppose you want a random sample of likely voters, a common problem. Random selection via a random number generator might cause you to poll the same likely voter twice. Of course you don't want that! And you probably don't want repeating lesson pairs here.

I remember from studying probability that there is a distinction between random selection with replacement and random selection without replacement. Suppose you have a jar containing a mixture of white stones and black stones. Random selection with replacement would mean you select a stone, add it to your sample, then put it back in the jar and make another random selection from the jar. Random selection without replacement would mean you select a stone for your sample but do not put it back in the jar. Then you make a random selection from the remaining stones.

Random selection without replacement can indeed lead to more diversity. That's because, once selected, a value (in this case a pair of values) is no longer available for further (random) selection.

SG

"Random selection without replacement can indeed lead to more diversity. That's because, once selected, a value (in this case a pair of values) is no longer available for further (random) selection."

Controlling the repeats and going for the greatest diversity in the list was the thrust of my earlier approach to this—use a set that contained all possible combinations of two different values from a set of eight (28) , then add enough 'fixed choice' pairs (2) to fill the remaining days in the list.

Selecting pair from the list using RAND() to order the selection provided a set of pseudo random numbers choses from a set of 10^10 (or more) possible values, enough to provide a very low probability of having a repeated value in the list, without which, every pair on the list would be used exactly once.

The approach failed, though, if the repetition number was considered an 'exact' rather than a 'minimum' number of times for a particular lesson to be read.

Regards,

Barry