array random sort

[Guest]

How do I take an array or arraylist, and sort it randomly? Like suppose the
items in it are (1,2,3,4,5) and I want to get it to be in a random order
(2,3,1,4,5). How do you do that? I think it's a call to the array or array
lists sort method, but i'm not exactly sure how you do it.

 

[Fred Mellender]

How do I take an array or arraylist, and sort it randomly? Like suppose
the
items in it are (1,2,3,4,5) and I want to get it to be in a random order
(2,3,1,4,5). How do you do that? I think it's a call to the array or array
lists sort method, but i'm not exactly sure how you do it.

public static List<T> shuffledList(List<T> listToShuffle)
{
/*
* Make a new list of elements picked from listToShuffle
* in a random order.
*/

List<int> ints = new List<int>(listToShuffle.Count); //0, 1,
2, ...
for (int i = 0; i < listToShuffle.Count; i++)
ints.Add(i);

List<T> randList = new List<T>(listToShuffle.Capacity);

for (int k = 0; k < listToShuffle.Count; k++)
{
int randIndx = Common.rand.Next(ints.Count); //random
from 0, 2, .. not already picked
int randK = ints[randIndx];
randList.Add(listToShuffle[randK]);
ints.RemoveAt(randIndx);
}

return randList;
}

 

[Bill Butler]

How do I take an array or arraylist, and sort it randomly? Like suppose the
items in it are (1,2,3,4,5) and I want to get it to be in a random order
(2,3,1,4,5). How do you do that? I think it's a call to the array or array
lists sort method, but i'm not exactly sure how you do it.

Sniff....Sniff....Smells like homework.

Search google groups for shuffle algorithm
You should find what you need

Good luck
Bill

 

[Fred Mellender]

I forgot to mention that Common.rand is an instance of Random, and is a
static member of class Common.

You can find this, and some other useful utilities, at
http://www.frontiernet.net/~fredm/dps/Contents.htm

How do I take an array or arraylist, and sort it randomly? Like suppose
the
items in it are (1,2,3,4,5) and I want to get it to be in a random order
(2,3,1,4,5). How do you do that? I think it's a call to the array or
array
lists sort method, but i'm not exactly sure how you do it.

public static List<T> shuffledList(List<T> listToShuffle)
{
/*
* Make a new list of elements picked from listToShuffle
* in a random order.
*/

List<int> ints = new List<int>(listToShuffle.Count); //0, 1,
2, ...
for (int i = 0; i < listToShuffle.Count; i++)
ints.Add(i);

List<T> randList = new List<T>(listToShuffle.Capacity);

for (int k = 0; k < listToShuffle.Count; k++)
{
int randIndx = Common.rand.Next(ints.Count); //random
from 0, 2, .. not already picked
int randK = ints[randIndx];
randList.Add(listToShuffle[randK]);
ints.RemoveAt(randIndx);
}

return randList;
}

 

[Guest]

I'm using c# 1.1 so no generics.

How do I take an array or arraylist, and sort it randomly? Like suppose
the
items in it are (1,2,3,4,5) and I want to get it to be in a random order
(2,3,1,4,5). How do you do that? I think it's a call to the array or array
lists sort method, but i'm not exactly sure how you do it.

public static List<T> shuffledList(List<T> listToShuffle)
{
/*
* Make a new list of elements picked from listToShuffle
* in a random order.
*/

List<int> ints = new List<int>(listToShuffle.Count); //0, 1,
2, ...
for (int i = 0; i < listToShuffle.Count; i++)
ints.Add(i);

List<T> randList = new List<T>(listToShuffle.Capacity);

for (int k = 0; k < listToShuffle.Count; k++)
{
int randIndx = Common.rand.Next(ints.Count); //random
from 0, 2, .. not already picked
int randK = ints[randIndx];
randList.Add(listToShuffle[randK]);
ints.RemoveAt(randIndx);
}

return randList;
}

 

[Guest]

it's definitely not homework. hehe..i wish it was.

I'm basically pulling an array of rows from a dataset, and they have to get
put into a random order (so the same first 3 people don't get a certain value
everytime, it's randomized).

I can check google like you said though.

 

[Bill Butler]

I'm using c# 1.1 so no generics.

:

So use ArrayList instead
Bill

 

[Jon Skeet [C# MVP]]

<snip>

Note that it's relatively easy to do this *without* creating two lists
(which Fred's solution does). You can shuffle within the list, by
having an imaginary dividing line between the "randomized" section and
the "unrandomized" section of the list. You start off considering
everything to be unrandomized, then pick a random element to be element
0, swapping it if necessary.

You then take a random element *other than 0*, and swap that into
position 1.

You then take a random element *other than 0 or 1* and swap that into
position 2, etc.

Here's some code which does that with an ArrayList:

public static void Shuffle (ArrayList al)
{
for (int i=0; i < al.Count; i++)
{
object x = al;

int index = rng.Next(al.Count-i)+i;
al=al[index];
al[index]=x;
}
}

In each iteration, we're looking to set element i (which is currently
in the "unshuffled" section) to be a random element from the unshuffled
section. At that stage, it becomes part of the shuffled section.

 

[James Curran]

The problem with Fred's solution is that while it appears to be an O(n)
algorithm, RemoveAt itself is O(n), making the overall algorithm O(n^2). If
the input array get big, it's going to get very slow.

The trick is to avoid deleting anything. We're starting with an array
of N, and we finish with an array of N, so there's no reason to delete
anything. This version is really O(n):

// Shuffles inplace.
public static List<T> shuffleList(List<T> listToShuffle)
{
for (int k = listToShuffle.Count-1; k > 1; --k)
{
int randIndx = Common.rand.Next(k); //
T temp = listToShuffle[k];
listToShuffle[k] = listToShuffle[randIndx]; // move random num to
end of list.
listToShuffle[randIndx] = temp;
}
return listToShuffle;
}

So, say, for example, listToShuffle has 10 elements (0-9). First we pick a
random number between 0 & 8, and we swap the element at the position with
the element at position 9. Then we pick an number between 0 & 7, and swap
that element with [8]. And so on until we're pick a number between 0 & 1 and
swapping it with listToShuffle[2]
--
Truth,
James Curran
[erstwhile VC++ MVP]

Home: www.noveltheory.com Work: www.njtheater.com
Blog: www.honestillusion.com Day Job: www.partsearch.com

How do I take an array or arraylist, and sort it randomly? Like suppose
the
items in it are (1,2,3,4,5) and I want to get it to be in a random order
(2,3,1,4,5). How do you do that? I think it's a call to the array or array
lists sort method, but i'm not exactly sure how you do it.

public static List<T> shuffledList(List<T> listToShuffle)
{
/*
* Make a new list of elements picked from listToShuffle
* in a random order.
*/

List<int> ints = new List<int>(listToShuffle.Count); //0, 1,
2, ...
for (int i = 0; i < listToShuffle.Count; i++)
ints.Add(i);

List<T> randList = new List<T>(listToShuffle.Capacity);

for (int k = 0; k < listToShuffle.Count; k++)
{
int randIndx = Common.rand.Next(ints.Count); //random
from 0, 2, .. not already picked
int randK = ints[randIndx];
randList.Add(listToShuffle[randK]);
ints.RemoveAt(randIndx);
}

return randList;
}

 

[Pete Davis]

If it were homework, I suspect he'd be asking about a random shuffle instead
of a random sort.

Pete