Randomizing elements of a string

[andrewbarbour]

I have a list of individuals that I need to randomize the order of...

Bob,Mary,Bill,Thomas,Jack,Jimbo

All I need to do is put them in random order in a new string.

I thought this would be easy.... the code I have found in the forums is a little difficult to follow. Any ideas?

EDIT: A GREAT feature for the application would be a command to shuffle an array (with an option for the feature of allowing or not allowing the array elements to stay in the same position)!

Thanks!

[JRL]

Here's one way with comments to explain.

Code: Select all

//Older versions of Macro Scheduler need this
Let>comma=,
//Added "RoseMary" to demonstrate the need to surround the list elements
//with delimiters.  Otherwise StringReplace>Mary makes RoseMary "Rose"
Let>vOrig_List=Bob,Mary,Bill,Thomas,Jack,Jimbo,RoseMary
//Create a list copy if you need to preserve the original list
//as we will incrementally erode the working list.
Let>vCopy_List=%comma%%vOrig_List%%comma%
//Create a variable to contain the new randomized list
Let>vNew_List=comma
//Get a count of list elements
Separate>vCopy_List,comma,vElement
//Loop through the possible list values adding one element
//at a time to the new list and removing that same element
//from the copy list
Repeat>vElement_Count
  //Create a random number to use as an array element selector
  //deduct for the extra commas
  Let>vRandomLimit=%vElement_Count%-2
  Random>vRandomLimit,vRandom_Number
  //Add one to the random number so it will never be zero
  //plus one for the extra commas
  Add>vRandom_Number,2
  //assign the random element to a variable
  Let>value=vElement_%vRandom_Number%
  //Add the random element to the new list
  Concat>vNew_List,%value%%comma%
  //Remove the random element from the old list
  StringReplace>vCopy_List,%comma%%value%%comma%,%comma%,vCopy_List
  //Get a new element count
  Separate>vCopy_List,comma,vElement
Until>vElement_Count=2

//Remove the extra comma we added at the end of the loop
StringReplace>vNew_List,%comma%%value%%comma%,%comma%%value%,vNew_List
//Remove first comma
MidStr>vNew_List,2,99999999,vNew_List
MDL>vNew_List

[Djek]

hi Andrew,

i guess the solution JRL offers is a good one, but i think difficult to follow?


here i have a quick and dirty way i created :

Code: Select all

let>max=6
let>maxr=%max%*30
ArrayDim>name,%max%
ArrayDim>order,%max%
let>name_1=1Bob
let>name_2=2Mary
let>name_3=3Bill
let>name_4=4Thomas
let>name_5=5Djek
let>name_6=6Jimbo

let>T=0
  label>nextT
  add>T,1
  if>T>%max%
    goto>disp
  endif
  Random>%maxr%,rnumber
  let>order_%T%=rnumber
  goto>nextT

  label>disp
  let>teller=0
  label>nextteller
  let>teller=teller+1
  if>teller>maxr
    goto>einde
  endif
  
  let>TT=0
  label>nextTT
  add>TT,1
  if>TT>%max%
    goto>nextteller
  endif
  if>order_%TT%=Teller
    Message>name_%TT%
    wait>1
    goto>nextteller
  endif
 
  goto>nextTT
  
label>einde

remind, its not properly formatted but i think you can use it
kind regards
Djek

[JRL]

Djek,

I like your solution but for some reason I sometimes only get five of the six results. I rewrote your script to write to a file so I could confirm this. In each case of five results it missed "6jimbo".

Not being critical. I've rewritten my solution 3 times since I first posted it last night and I'm still not certain it will always work.

Code: Select all

Let>WLN_NOCRLF=1
WriteLn>%temp_dir%RandomNameList.txt,wres,%crlf%

let>max=6
let>maxr=%max%*30
ArrayDim>name,%max%
ArrayDim>order,%max%
let>name_1=1Bob
let>name_2=2Mary
let>name_3=3Bill
let>name_4=4Thomas
let>name_5=5Djek
let>name_6=6Jimbo
let>T=0
  label>nextT
  add>T,1
  if>T>%max%
    goto>disp
  endif
  Random>%maxr%,rnumber
  let>order_%T%=rnumber
  goto>nextT
  label>disp
  let>teller=0
  label>nextteller
  let>teller=teller+1
  if>teller>maxr
    goto>einde
  endif
 
  let>TT=0
  label>nextTT
  add>TT,1
  if>TT>%max%
    goto>nextteller
  endif
  if>order_%TT%=Teller
    //Message>name_%TT%
    Let>Entry=name_%TT%
    WriteLn>%temp_dir%RandomNameList.txt,wres,%Entry%%comma%
    //wait>1
    goto>nextteller
  endif
 
  goto>nextTT
 
label>einde

Here are my results for 20 trials:

4Thomas,1Bob,5Djek,6Jimbo,2Mary,3Bill,
3Bill,5Djek,6Jimbo,1Bob,4Thomas,2Mary,
1Bob,5Djek,2Mary,3Bill,6Jimbo,4Thomas,
2Mary,4Thomas,3Bill,5Djek,1Bob,
3Bill,6Jimbo,2Mary,1Bob,5Djek,4Thomas,
3Bill,2Mary,1Bob,4Thomas,5Djek,6Jimbo,
1Bob,5Djek,6Jimbo,3Bill,4Thomas,2Mary,
1Bob,4Thomas,3Bill,2Mary,5Djek,
4Thomas,5Djek,1Bob,2Mary,6Jimbo,3Bill,
3Bill,1Bob,2Mary,6Jimbo,5Djek,4Thomas,
4Thomas,2Mary,6Jimbo,1Bob,5Djek,3Bill,
4Thomas,1Bob,5Djek,2Mary,3Bill,6Jimbo,
4Thomas,6Jimbo,2Mary,3Bill,1Bob,5Djek,
2Mary,1Bob,5Djek,3Bill,4Thomas,
5Djek,1Bob,4Thomas,3Bill,6Jimbo,2Mary,
1Bob,3Bill,6Jimbo,2Mary,4Thomas,5Djek,
6Jimbo,3Bill,2Mary,4Thomas,1Bob,5Djek,
3Bill,4Thomas,2Mary,1Bob,6Jimbo,5Djek,
5Djek,6Jimbo,4Thomas,1Bob,2Mary,3Bill,
4Thomas,1Bob,6Jimbo,5Djek,3Bill,2Mary,

[Djek]

hi JRL,
thats because of the Randomize function isnt always random.

But we kan "help' that
just change the

let>maxr=%max%*30
into
let>maxr=%max%*60
and look again,
you will notice a better score !!

(ahum, i know that this isnt properly programming, but for only use at home, this is allowed)

[JRL]

Djek,

There's something else awry. I changed from let>maxr=%max%*30 to let>maxr=%max%*60 and still got 3 out of 20 with only 5 elements returned. Changed it to let>maxr=%max%*600 and still get one out of 50 with five elements. So I added a loop to check for and eliminate duplicate "random" numbers and still got only 5 elements 10% of the time.

Code: Select all

Let>WLN_NOCRLF=1
WriteLn>%temp_dir%RandomNameList.txt,wres,%crlf%
let>max=6
let>maxr=%max%*30
ArrayDim>name,%max%
ArrayDim>order,%max%
let>name_1=1Bob
let>name_2=2Mary
let>name_3=3Bill
let>name_4=4Thomas
let>name_5=5Djek
let>name_6=6Jimbo
let>T=0
  label>nextT
  add>T,1
  if>T>%max%
    goto>disp
  endif
  Label>NewRandomNumber
  Random>%maxr%,rnumber
  
  
  //Check to see if random number has already been used
  Let>kk=0
  Repeat>kk
    Add>kk,1
    Let>value=Order_%kk%
    If>rnumber=value,NewRandomNumber
  Until>kk=max
  //End Check//////////////////////////////////////////
  
  
  let>order_%T%=rnumber
  WriteLn>%temp_dir%RandomNameList.txt,wres,%rnumber%%comma%
  goto>nextT
  label>disp
  let>teller=0
  label>nextteller
  let>teller=teller+1
  if>teller>maxr
    goto>einde
  endif
 
  let>TT=0
  label>nextTT
  add>TT,1
  if>TT>%max%
    goto>nextteller
  endif
  if>order_%TT%=Teller
    //Message>name_%TT%
    Let>Entry=name_%TT%
    WriteLn>%temp_dir%RandomNameList.txt,wres,%Entry%%comma%
    //wait>1
    goto>nextteller
  endif
 
  goto>nextTT
 
label>einde

You can see that in no line are there duplicate random numbers (the first six numbers in each line).

87,82,105,129,56,153,5Djek,2Mary,1Bob,3Bill,4Thomas,6Jimbo,
19,148,159,71,69,99,1Bob,5Djek,4Thomas,6Jimbo,2Mary,3Bill,
4,156,36,170,131,43,1Bob,3Bill,6Jimbo,5Djek,2Mary,4Thomas,
112,64,81,69,104,26,6Jimbo,2Mary,4Thomas,3Bill,5Djek,1Bob,
68,123,84,128,88,36,6Jimbo,1Bob,3Bill,5Djek,2Mary,4Thomas,
125,44,93,147,144,157,2Mary,3Bill,1Bob,5Djek,4Thomas,6Jimbo,
132,130,36,19,23,54,4Thomas,5Djek,3Bill,6Jimbo,2Mary,1Bob,
13,90,153,15,62,115,1Bob,4Thomas,5Djek,2Mary,6Jimbo,3Bill,
71,176,118,166,61,100,5Djek,1Bob,6Jimbo,3Bill,4Thomas,2Mary,
13,8,92,97,58,41,2Mary,1Bob,6Jimbo,5Djek,3Bill,4Thomas,
168,154,104,44,123,162,4Thomas,3Bill,5Djek,2Mary,6Jimbo,1Bob,
102,9,62,23,37,89,2Mary,4Thomas,5Djek,3Bill,6Jimbo,1Bob,
0,135,59,20,8,25,5Djek,4Thomas,6Jimbo,3Bill,2Mary,
96,9,24,69,173,117,2Mary,3Bill,4Thomas,1Bob,6Jimbo,5Djek,
80,123,6,17,15,87,3Bill,5Djek,4Thomas,1Bob,6Jimbo,2Mary,
30,6,18,0,97,90,2Mary,3Bill,1Bob,6Jimbo,5Djek,
6,89,161,140,146,35,1Bob,6Jimbo,2Mary,4Thomas,5Djek,3Bill,
136,30,20,21,1,110,5Djek,3Bill,4Thomas,2Mary,6Jimbo,1Bob,
144,129,6,71,84,56,3Bill,6Jimbo,4Thomas,5Djek,2Mary,1Bob,
108,49,139,155,119,1,6Jimbo,2Mary,1Bob,5Djek,3Bill,4Thomas,
121,123,168,77,171,54,6Jimbo,4Thomas,1Bob,2Mary,3Bill,5Djek,

[Djek]

hah !
it a bug,
it looks like its the zero that is missed by the Teller counter

change
let>teller=0
into
let>teller=-1

and then the bug is exterminated

... i hope...

[JRL]

That was the final bug zapper. Still need the random number check loop to be sure that no random number is used twice. But this script seems to work.

I would like to point out that my script (posted above) also seems to work...

Thank you andrewbarbour for posing the question. This was fun

Code: Select all

Let>WLN_NOCRLF=1
WriteLn>%temp_dir%RandomNameList.txt,wres,%crlf%
let>max=6
let>maxr=%max%*30
ArrayDim>name,%max%
ArrayDim>order,%max%
let>name_1=1Bob
let>name_2=2Mary
let>name_3=3Bill
let>name_4=4Thomas
let>name_5=5Djek
let>name_6=6Jimbo
let>T=0
  label>nextT
  add>T,1
  if>T>%max%
    goto>disp
  endif
  Label>NewRandomNumber
  Random>%maxr%,rnumber
  
  

  //Check to see if random number has already been used
  Let>kk=0
  Repeat>kk
    Add>kk,1
    Let>value=Order_%kk%
    If>rnumber=value,NewRandomNumber
  Until>kk=max
  //End Check//////////////////////////////////////////

  
  
  let>order_%T%=rnumber
  WriteLn>%temp_dir%RandomNameList.txt,wres,%rnumber%%comma%
  goto>nextT
  label>disp
  let>teller=-1
  label>nextteller
  let>teller=teller+1
  if>teller>maxr
    goto>einde
  endif
 
  let>TT=0
  label>nextTT
  add>TT,1
  if>TT>%max%
    goto>nextteller
  endif
  if>order_%TT%=Teller
    //Message>name_%TT%
    Let>Entry=name_%TT%
    WriteLn>%temp_dir%RandomNameList.txt,wres,%Entry%%comma%
    //wait>1
    goto>nextteller
  endif
 
  goto>nextTT
 
label>einde

[andrewbarbour]

AWESOME! You have no idea how long this took me.... I should have posted sooner. So much more elegant than what I was doing (or rather trying to do). You ever take on a project and it is FAR more complex than you thought? I am trying to optimize the shift schedules for a group of employees. And then... I a find out that schedule optimization is so complex it is included in operations science competitions https://en.wikipedia.org/wiki/Nurse_scheduling_problem

Basically - I grab everyone's availability via an exchange webservice and then have to pick up to 4 people for each shift (2 hours out of their day) into one of four shifts each day. And keep all the staff (physicians) happy. The optimization is tricky as some shift we have only 4 people available - so I have to schedule this shift first. And then keep track of who has a shift for the day so as not to pick them again!

Thanks to both of you for your help with this! If you are ever in Ottawa - beers are on me!

EDIT - But wouldn't a 'shuffle' function be AWESOME! Marcus?

[andrewbarbour]

change
let>teller=0
into
let>teller=-1

and then the bug is exterminated

... i hope...

That did not work entirely for me - the incidents of only 5 items in the list were as follows:
Trial 1 - 4/100 had only 5 items after the shuffle
Trial 2 - 2/100
Trial 3 - 9/100

It was the third line below you meant to change - correct?

Code: Select all

 goto>nextT
  label>disp
  let>teller=-1
  label>nextteller

- but I will just write in a check to ensure that the randomized list has the same number before and after the randomization sub routine - and if not go do it again.

THanks!

[Djek]

pfff its a long way to Ottawa from here,
slightly to far to fetch a beer. But its tempting though...

look at
let>maxr=%max%*30
if you change 30 into 100 or 400 (if time is not an issue)
than the odd that randomize takes the same value is minimized.

Indeed thank you for submitting this question, and success with the nurse sheduling problem.
I developped last year a parents night schedule for a school. Were former the calculating manually took 3 evenings, and now it takes 5 minutes including mailing parents and teachers. But i read the wiki, the nurse problem is much more difficult.

kind regards,
Djek

[andrewbarbour]

When I complete my solution I will post it all here - as long as nobody gives me too much grief for my coding skills...

My first cut got the time down from 8 hours per month to 25 minutes. And considering the individuals doing the schedule were SENIOR physicians - you can imagine the cost savings this represented!

EDIT - OK so here is the version that I have just for the shuffling - I tweaked the code from above a bit - so that it starts with a string to shuffle strToShuffle and produces a shuffled string strShuffled. I will also post my fully complete scheduling solution should anyone find it remotely interesting.

Code: Select all

Let>comma=,
Let>strToShuffle=ABC,CRC,AGD,LLB,ARS
messagemodal>About to shuffle %strToShuffle%
gosub>ShuffleAString
messageModal>I shuffled it: %strShuffled%

SRT>ShuffleAString
// This SRT takes a string to shuffle strToShuffle
// shuffles it and saves it as strShuffled

//First save the starting string to test against later
Separate>strToShuffle,comma,OriginalString
Let>ItemCountToShuffle=OriginalString_count
//Reset the strShuffled
Label>SuffleTime
Let>strShuffled=
Let>WLN_NOCRLF=1
Separate>strToShuffle,comma,strfromfile
let>max=strfromfile_count
let>maxr=%max%*100
ArrayDim>name,%max%
ArrayDim>order,%max%
Separate>strToShuffle,comma,strfromfile

let>T=0
  label>nextT
  add>T,1
  if>T>%max%
    goto>disp
  endif
  Random>%maxr%,rnumber
  let>order_%T%=rnumber
  goto>nextT
  label>disp
  let>teller=-1
  label>nextteller
  let>teller=teller+1
  if>teller>maxr
    goto>einde
  endif
 
  let>TT=0
  label>nextTT
  add>TT,1
  if>TT>%max%
    goto>nextteller
  endif
  if>order_%TT%=Teller
    //Message>name_%TT%
    Let>Entry=strfromfile_%TT%
    Concat>strShuffled,%Entry%%comma%
    //WriteLn>C:\Users\bar20\Documents\_YellowCallAutomation\April2016\Test_betteroptomizer\TESTMJT.txt,wres,%Entry%%comma%
    
    //wait>1
    goto>nextteller
  endif
goto>nextTT
label>einde
Length>strShuffled,nLength
Let>trimlength=%nLength%-1
MidStr>strShuffled,1,trimlength,strShuffled
Separate>strShuffled,comma,AR_strShuffled
If>strfromfile_count<>AR_strShuffled_count,ShuffleTime
END>ShuffleAString

[hagchr]

Hi, I think you have some good ideas already, but just to throw one more in there. It is similar to JRL's but different in the sense it uses the RegEx> command. For smaller strings there is no practical difference, but if you have to run it many times or for many names, there could be a big performance difference.
I note that your version will need around 130 seconds to randomize 100 names whereas, JRL's and mine version will need a fraction of 1 second. I have not had time to check Djek's version.

Code: Select all

//Make a copy of the original string and add a (temporary) comma at the end
Let>String0=Bob,Mary,Bill,Thomas,Jack,Jimbo,RoseMary

Let>String=%String0%,
Separate>String,Comma,arrString

//Loop through, Select random name, add to result, remove from String
Let>res=
Let>k=%arrString_count%-1
While>k>0
    Random>k,tmp
    Let>Pattern=^(?:[^,]+,){%tmp%}\K[^,]+,
    RegEx>Pattern,String,0,m,nm,1,,String
    Add>k,-1
    Let>res=%res%%m_1%
EndWhile

//Remove the temporary trailing comma
RegEx>%comma%$,res,0,m,nm,1,,res

MDL>res

(A (temporary) comma is added at the end of the string which makes it more structured, just a sequence of names with commas)

In this case you use RegEx> to search for the following pattern (assume random number is 3):

Pattern=^(?:[^,]+,){3}\K[^,]+,

An explanation:

Start at the beginning of the string and match the first three names (name = one or more consecutive non-comma characters) each followed by comma. Then reset/forget the match (\K) and continue matching the next name (with comma).

So with the string:
String=Bob,Mary,Bill,Thomas,Jack,Jimbo,RoseMary,

You first match the first three names (Bob,Mary,Bill,) reset\forget with \K then match the next name (Thomas,).

Using the command:
RegEx>Pattern,String,0,m,nm,1,,String

nm contains the number of matches and m is an array that contains each match (m_1, m_2, ... m_nm). In this case there is only one match so that nm=1 and m_1=Thomas. The 1 is an option to replace any matches with a replacement string (here empty) so in effect you remove Thomas from the string.

Then it is just a matter of looping so that all names are processed, with each loop add a (random) name to the result string and remove the name from the original string. You start with a string with all names and remove a name in each iteration.

(The ?: in the (?:...) just instructs RegEx it does not have to capture/store anything matched within () which is otherwise standard but not needed here.).

The second pattern just defines that you search for a comma before the end of the string ($) and remove it.

It will be interesting to see how you solve the rest of the scheduling.

[Djek]

hi Hagchr,
i just run a test with 50.000 elements, and your solution runs amazingly fast; 2 seconds.
Thank you.
And for you explanation,
kind regards,
Djek