shuffling an arraylist

[John Slate]

Not sure exactly how to ask this, but I have a situation where I need to
'shuffle' the order of a list of test questions, so that the questions
appear in a random order each time the test is taken. I am not sure how
to go about this. The questions and multiple choice answers are stored
in SQL Server. Any suggestions?

 

[Dan Bass]

There's a few ways you could do this. Here's one.

Say there are n questions, then you could generate a random number between 0
and n-1 (for zero indexed arraylist), then use that number as the index of
the question you'll use... After that remove the question from the
arraylist.
The next time you generate an index by a random number between 0 and n-2
(new length of the remaining array).
The next time it will be between 0 and n-3, and so on until there is only
one element left.

 

[Picho]

Hi John,

recently did just that exact scenario...
the following function takes an array of objects and returns a shuffled
arraylist.
this ofcourse can be modified to recieve an arraylist instead of array, and
to return an array instead of an arraylist.
this might not be efficient or finished, but it works and I had it here
so...

p.s. - you can use the ArrayList.ToArray() for easy conversion back to array
of a givven type.

public static ArrayList Randomize(object[] source)
{
if (source==null)
return null;

if (source.Length<2)
return new ArrayList(source);

int length = source.Length;
int[] positions = new int[length];
object[] target = new object[length];

for (int i=0;i<positions.Length;i++)
positions = -1;

Random rnd = new Random();
for (int i=0;i<positions.Length;i++)
{
int position = -1;
bool alreadyAssigned = false;
bool first = true;
while (first || alreadyAssigned)
{
first = alreadyAssigned = false;
position = rnd.Next(length);
foreach (int assigned in positions)
{
if (assigned==position)
{
alreadyAssigned = true;
break;
}
}
}
positions = position;
}


for (int i=0;i<positions.Length;i++)
target[positions] = source;

ArrayList retval = new ArrayList(target);
return retval;
}

 

[James Curran]

Not sure exactly how to ask this, but I have a situation where I need to
'shuffle' the order of a list of test questions, so that the questions
appear in a random order each time the test is taken. I am not sure how
to go about this. The questions and multiple choice answers are stored
in SQL Server. Any suggestions?

Dan's method is close, but we don't want to go to the effort of removing
each item from the ArrayList, because that involves moving every item after
it down. Better to just swap it with the last item

public static void ShuffleInPlace(ArrayList source)
{
Random rnd = new Random();
for (int inx = source.Length-1; inx > 0; --inx)
{
int position = rnd.Next(inx);
object temp = source[inx];
source[inx] = source[position];
source[position] = temp;
}
}

--
Truth,
James Curran
[erstwhile VC++ MVP]
Home: www.noveltheory.com Work: www.njtheater.com
Blog: www.honestillusion.com Day Job: www.partsearch.com

 

[Dan Bass]

James,

While I prefer your method because you can reuse the ArrayList for the next
generation of questions, there is no involvement in moving items down in an
ArrayList because the RemoveAt ( index ) method does this for you...

See the Remarks section
http://msdn.microsoft.com/library/d...temCollectionsArrayListClassRemoveAtTopic.asp

Thanks.

Daniel.

Not sure exactly how to ask this, but I have a situation where I need to
'shuffle' the order of a list of test questions, so that the questions
appear in a random order each time the test is taken. I am not sure how
to go about this. The questions and multiple choice answers are stored
in SQL Server. Any suggestions?

Dan's method is close, but we don't want to go to the effort of
removing
each item from the ArrayList, because that involves moving every item
after
it down. Better to just swap it with the last item

public static void ShuffleInPlace(ArrayList source)
{
Random rnd = new Random();
for (int inx = source.Length-1; inx > 0; --inx)
{
int position = rnd.Next(inx);
object temp = source[inx];
source[inx] = source[position];
source[position] = temp;
}
}

--
Truth,
James Curran
[erstwhile VC++ MVP]
Home: www.noveltheory.com Work: www.njtheater.com
Blog: www.honestillusion.com Day Job: www.partsearch.com

 

[James Curran]

Different senses of the phrase "go to the effort". Yes, it's just one
library call, but then that library function has to copy every element. The
effort is being done by someone, and it's time-consuming & unnecessary....

This method also have the advantage of doing the shuffling all at once,
instead of one item at a time.

--
Truth,
James Curran
[erstwhile VC++ MVP]
Home: www.noveltheory.com Work: www.njtheater.com
Blog: www.honestillusion.com Day Job: www.partsearch.com

James,

While I prefer your method because you can reuse the ArrayList for the next
generation of questions, there is no involvement in moving items down in an
ArrayList because the RemoveAt ( index ) method does this for you...

See the Remarks section
http://msdn.microsoft.com/library/d...temCollectionsArrayListClassRemoveAtTopic.asp

Thanks.

Daniel.

Not sure exactly how to ask this, but I have a situation where I need to
'shuffle' the order of a list of test questions, so that the questions
appear in a random order each time the test is taken. I am not sure how
to go about this. The questions and multiple choice answers are stored
in SQL Server. Any suggestions?

Dan's method is close, but we don't want to go to the effort of
removing
each item from the ArrayList, because that involves moving every item
after
it down. Better to just swap it with the last item

public static void ShuffleInPlace(ArrayList source)
{
Random rnd = new Random();
for (int inx = source.Length-1; inx > 0; --inx)
{
int position = rnd.Next(inx);
object temp = source[inx];
source[inx] = source[position];
source[position] = temp;
}
}

--
Truth,
James Curran
[erstwhile VC++ MVP]
Home: www.noveltheory.com Work: www.njtheater.com
Blog: www.honestillusion.com Day Job: www.partsearch.com

 

[Dan Bass]

Sure, that makes sense.

I decided to knock up a test app to against the two methods. Hey it's
Christmas eve and quiet around the office at the moment. ;o)

It's a crude test at best, but really drives your point home about
efficiency. My first approach was just a first stab solution, and thought at
the time there's probably a much better way of doing this.

At testing an ArrayList of integers with a size of 200,000, the application
running on my machine took between 70 and 80 seconds on average, to
randomize the list with the remove and insert method i first suggested. The
in place swap you put forward took under a second, every time, for the same
amount.

What made things worse (from my stand point) is that the in place shuffle
looks linear ( O(n) ), while the remove and insert is closer to an
exponential curve. Eeek!

Different senses of the phrase "go to the effort". Yes, it's just one
library call, but then that library function has to copy every element.
The
effort is being done by someone, and it's time-consuming & unnecessary....

This method also have the advantage of doing the shuffling all at once,
instead of one item at a time.

--
Truth,
James Curran
[erstwhile VC++ MVP]
Home: www.noveltheory.com Work: www.njtheater.com
Blog: www.honestillusion.com Day Job: www.partsearch.com

James,

While I prefer your method because you can reuse the ArrayList for the next
generation of questions, there is no involvement in moving items down in an
ArrayList because the RemoveAt ( index ) method does this for you...

See the Remarks section
http://msdn.microsoft.com/library/d...temCollectionsArrayListClassRemoveAtTopic.asp

Thanks.

Daniel.

Not sure exactly how to ask this, but I have a situation where I need to
'shuffle' the order of a list of test questions, so that the questions
appear in a random order each time the test is taken. I am not sure
how
to go about this. The questions and multiple choice answers are stored
in SQL Server. Any suggestions?

Dan's method is close, but we don't want to go to the effort of
removing
each item from the ArrayList, because that involves moving every item
after
it down. Better to just swap it with the last item

public static void ShuffleInPlace(ArrayList source)
{
Random rnd = new Random();
for (int inx = source.Length-1; inx > 0; --inx)
{
int position = rnd.Next(inx);
object temp = source[inx];
source[inx] = source[position];
source[position] = temp;
}
}

--
Truth,
James Curran
[erstwhile VC++ MVP]
Home: www.noveltheory.com Work: www.njtheater.com
Blog: www.honestillusion.com Day Job: www.partsearch.com