Ask Ben: Selecting Random Values Without Repetition In ColdFusion
Hi, I have string defined like this: myStr = "1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20"
I need a function to randomly to pick out any number of the above string, no duplication, mean if it pick 4, then it never pick 4 again. I tried CF functions likerand, randrange, Randomize , but nothing works. This is a survey project, when user hit a button, system suppose randomly to pick 6 out of 20 questions out of database. I wonder if you have any advise please? Thanks.
If we are dealing with randomly selected database rows, then all you would need to do is ORDER BY a random value (such as NEWID()) and select the top N records. But, since you showed me a list, I'm gonna work with a list. In the past, I have come up with ways to randomly select elements from an array, which would work nicely here if you simply converted the list to an array before you made your selection (assuming the list itself doesn't have repeat values). But, some of those examples are complicated. For this, I'm gonna keep it super simple.
For this version of random selection without repetition, the trick is to make good use of the fact that ColdFusion structs won't store the same key twice. If we go with that (and don't worry about case sensitivity, which it looks like you won't have to), then all we need to do is keep adding random values to a struct until its size (number of keys) is equal to the desired set. Then, we just use the key collection as our list of random values.
<!--- Define the list of numbers. --->
<cfset strList = "1,2,3,4,5,6,7,8,9,10" />
<!---
Create a struct to hold the list of selected numbers. Because
structs are indexed by key, it will allow us to not select
duplicate values.
--->
<cfset objSelections = {} />
<!---
Now, all we have to do is pick random numbers until our
struct count is the desired size (4 in this demo).
--->
<cfloop condition="(StructCount( objSelections ) LT 4)">
<!--- Select a random list index. --->
<cfset intIndex = RandRange( 1, ListLen( strList ) ) />
<!---
Add the random item to our collection. If we have
already picked this number, then it will simply
overwrite the previous and the StructCount() will
not be changed.
--->
<cfset objSelections[ ListGetAt( strList, intIndex ) ] = true />
</cfloop>
<!--- Output the list collection. --->
#StructKeyList( objSelections )#
When I run this a few times, I get:
10,3,4,5
8,9,10,4
7,8,9,3
8,9,10,2
7,8,10,2
9,3,5,6
Works quite nicely and is straightforward. There are things you could do to optimize this; but, I don't think you could do anything to beat this simplicity. I hope that helps.
Want to use code from this post? Check out the license.
Reader Comments
Ben,
This code has the potential to run, especially if the length of the list and the number of items to pull are fairly close to each other.
Imaging 1000 numbers and pulling 990 out. The random number generator may pick many times in a row already picked items. Of course for relatively small sets of numbers, the extra processing may not be a big deal, but in theory, it's possible (not likely though) for the random number generator to select the same number a billion+ times in a row.
If you were to pluck out the list item when you access it (using ListDeleteAt) then at least you have a guarantee that the current list of items will never have a match. You can copy the list if you want to have an untouched list to use later.
Now granted in my example, you could simply remove the number of unnecessary items (10) and then perform the shuffle on the remaining items.
@Danilo,
You raise a good point. The close the size of the list and the number of items you need to randomly select, the more the potential processing. I think this kind of solution is only usable in certain situations. I tried to keep is simple only because I have other examples on the site that are more effective but much more complicated.
Probably, the happy medium between ease and speed is to convert the list to an array, shuffle it (as a collection), and then just select the top N indexes. Relatively painless and very fast.
Seems to me, for speed reasons, we should be shoving all this into an array via ListToArray() and using array functions.
For this guy, it should be done on the database side.
In SQL Server, you add ORDER BY NewID()
This blog has a run down of a host of random ordering options in different databases: http://www.carlj.ca/2007/12/16/selecting-random-records-with-sql/
If you have an Array, MyArray, an efficient process is this:
<cfset ToValue = 4>
<cfset ArrayLength = ArrayLen(MyArray)>
<cfif ArrayLength LTE ToValue>
<cfset ToValue = ArrayLength-1>
</cfif>
<cfloop from="1" to="#ToValue#" index="X">
<cfset Y = RandRange(X, ArrayLength)>
<cfset Element = MyArray[X]>
<cfset MyArray[X] = MyArray[Y]>
<cfset MyArray[Y] = Element>
</cfloop>
This reorders the array using swaps, with only one swap required per element.
Of course, I just wrote the above on the fly - but I remember that being the most efficient way for random ordering without replacement (O(n)) from my undergraduate days.
I thought that this might work quite well-
<cffunction name="randomNums" access="public" returntype="array">
<cfargument name="numOutput" type="numeric" required="yes">
<cfargument name="listValues" type="string" required="yes">
<cfset var local = {}>
<!---Convert the list to an array--->
<cfset LOCAL.completeList = listToArray(arguments.listValues)>
<!---Get the length of the array, don't want to calculate this each loop--->
<cfset LOCAL.listLength = arrayLen(LOCAL.completeList)>
<!---We are going to return an array with the values--->
<cfset LOCAL.returnArray = []>
<!---Loop until we have reached the required number--->
<cfloop from="1" to="arguments.numOutput" index="LOCAL.i">
<!---Append the random item to the new array--->
<cfset arrayAppend(LOCAL.returnArray,LOCAL.completeList[randRange(1,LOCAL.listLength)])>
<!---Shorten the length of the list so that we are not out of bounds on the next iteration--->
<cfset LOCAL.listLength -= 1>
</cfloop>
<cfreturn LOCAL.returnArray>
</cffunction>
Hi Brandon,
Does that take care of duplicate selections? It seems like you would have a chance of grabbing the first element of the complete list with each loop iteration.
With a List (MyList) and a desire of 4 randomized values (ToValue), you could alter the array code to:
<cfset ListLength = ListLen(MyList)>
<cfif ListLength LTE ToValue>
<cfset ToValue = ListLength-1>
</cfif>
<cfloop from="1" to="#ToValue#" index="X">
<cfset Y = RandRange(X, ListLength)>
<cfset Element = ListGetAt(MyList,X)>
<cfset MyList = ListSetAt(MyList,X,ListGetAt(MyList,Y))>
<cfset MyList = ListSetAt(MyList,Y,Element>
</cfloop>
and have something on the order of O(tovalue) without a chance of duplicated values (assuming no duplicates existed in MyList to begin with).
-Lyle
@Lyle
You were right about the dups. I wasn't actually removing anything from the array, which is obviously an issue. Try this one-
<cffunction name="randomNums" access="public" returntype="array">
<cfargument name="numOutput" type="numeric" required="yes">
<cfargument name="listValues" type="string" required="yes">
<cfset var local = {}>
<!---Convert the list to an array--->
<cfset LOCAL.completeList = listToArray(arguments.listValues)>
<!---Get the length of the array, don't want to calculate this each loop--->
<cfset LOCAL.listLength = arrayLen(LOCAL.completeList)>
<!---We are going to return an array with the values--->
<cfset LOCAL.returnArray = []>
<!---Loop until we have reached the required number--->
<cfloop from="1" to="#arguments.numOutput#" index="LOCAL.i">
<cfset LOCAL.randNum = randRange(1,LOCAL.listLength)>
<!---Append the random item to the new array--->
<cfset arrayAppend(LOCAL.returnArray,LOCAL.completeList[LOCAL.randNum])>
<!---Shorten the length of the list so that we are not out of bounds on the next iteration--->
<cfset arrayDeleteAt(LOCAL.completeList,LOCAL.randNum)>
<cfset LOCAL.listLength -= 1>
</cfloop>
<cfreturn LOCAL.returnArray>
</cffunction>
<cfdump var="#randomNums(5,"1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20")#">
Are we over thinking this?
list="1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20"
list = customDedupFunctionIfNecessary(list);
randList=""
Loop X times{
Index = randRange(1,listLen(list))
randList = ListAppend(randList,listGetAt(list,Index));
list = listDeleteAt(Index);
}
I read thru this post and came up with this code. I used it to pick 2 days of the week to send an email message. I wanted the messages to go out on random days during the week. Days selected by code where stored in DB and used for following week...
<cfset daysOfWkList = "1,2,3,4,5,6,7">
<cfset randList="">
<cfloop from="1" to="2" index="i">
<!--- rand number in betwn 1 & daysOfWkList length --->
<cfset RandPos = randRange(1,listLen(daysOfWkList))>
<!--- number in daysOfWkList that's at random number position --->
<cfset NumAtRandPos = ListGetAt(daysOfWkList,RandPos)>
<!--- add number at random position to randList --->
<cfset randList = ListAppend(randList,NumAtRandPos)>
<!--- now delete number at rand position in daysOfWkList --->
<cfset daysOfWkList = ListDeleteAt(daysOfWkList,RandPos)>
</cfloop>
<!--- sort list --->
<cfset randList = ListSort(randList,"numeric")>
@Pen,
Looks good my man. I'm glad that I could help point you in the right direction.
@Ben,
F.Y.I. Pen is short for Penelope...
;-)
@Pen,
Nice to meet you Penelope :) My lady....
Thanks sir for valuable post