424,855 Members | 1,934 Online
Need help? Post your question and get tips & solutions from a community of 424,855 IT Pros & Developers. It's quick & easy.

# array random sort

 P: n/a 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. Nov 17 '05 #1
9 Replies

 P: n/a "gl" wrote in message news:7E**********************************@microsof t.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 shuffledList(List listToShuffle) { /* * Make a new list of elements picked from listToShuffle * in a random order. */ List ints = new List(listToShuffle.Count); //0, 1, 2, ... for (int i = 0; i < listToShuffle.Count; i++) ints.Add(i); List randList = new List(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; } Nov 17 '05 #2

 P: n/a "gl" wrote in message news:7E**********************************@microsof t.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. Sniff....Sniff....Smells like homework. Search google groups for shuffle algorithm You should find what you need Good luck Bill Nov 17 '05 #3

 P: n/a 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 "Fred Mellender" wrote in message news:3h*****************@news02.roc.ny... "gl" wrote in message news:7E**********************************@microsof t.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 shuffledList(List listToShuffle) { /* * Make a new list of elements picked from listToShuffle * in a random order. */ List ints = new List(listToShuffle.Count); //0, 1, 2, ... for (int i = 0; i < listToShuffle.Count; i++) ints.Add(i); List randList = new List(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; } Nov 17 '05 #4

 P: n/a I'm using c# 1.1 so no generics. :( "Fred Mellender" wrote: "gl" wrote in message news:7E**********************************@microsof t.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 shuffledList(List listToShuffle) { /* * Make a new list of elements picked from listToShuffle * in a random order. */ List ints = new List(listToShuffle.Count); //0, 1, 2, ... for (int i = 0; i < listToShuffle.Count; i++) ints.Add(i); List randList = new List(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; } Nov 17 '05 #5

 P: n/a 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" wrote: "gl" wrote in message news:7E**********************************@microsof t.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. Sniff....Sniff....Smells like homework. Search google groups for shuffle algorithm You should find what you need Good luck Bill Nov 17 '05 #6

 P: n/a "gl" wrote in message news:28**********************************@microsof t.com... I'm using c# 1.1 so no generics. :( "Fred Mellender" wrote: So use ArrayList instead Bill Nov 17 '05 #7

 P: n/a Fred Mellender wrote: "gl" wrote in message news:7E**********************************@microsof t.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. 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[i]; int index = rng.Next(al.Count-i)+i; al[i]=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. -- Jon Skeet - http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet If replying to the group, please do not mail me too Nov 17 '05 #8

 P: n/a 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 shuffleList(List 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 "Fred Mellender" wrote in message news:3h*****************@news02.roc.ny... "gl" wrote in message news:7E**********************************@microsof t.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 shuffledList(List listToShuffle) { /* * Make a new list of elements picked from listToShuffle * in a random order. */ List ints = new List(listToShuffle.Count); //0, 1, 2, ... for (int i = 0; i < listToShuffle.Count; i++) ints.Add(i); List randList = new List(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; } Nov 18 '05 #9

 P: n/a If it were homework, I suspect he'd be asking about a random shuffle instead of a random sort. :-) Pete "Bill Butler" wrote in message news:2i4ff.49\$N44.45@trndny08... "gl" wrote in message news:7E**********************************@microsof t.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. Sniff....Sniff....Smells like homework. Search google groups for shuffle algorithm You should find what you need Good luck Bill Nov 18 '05 #10

### This discussion thread is closed

Replies have been disabled for this discussion.