radomize a number list

[William Stacey [MVP]]

int[] list = {1,2,3,4,5,6};

Function to randomize the list?
Cheers!

 

[William Stacey [MVP]]

More specific example/need. Take any ArrayList of length >=2. Now
randomize the elements in most efficient method. TIA

 

[John Wood]

Run the ArrayList.Sort method, passing in a custom comparer that returns -1
or 1 randomly.
?

More specific example/need. Take any ArrayList of length >=2. Now
randomize the elements in most efficient method. TIA

--
William Stacey, MVP

int[] list = {1,2,3,4,5,6};

Function to randomize the list?
Cheers!

 

[Scott]

Try this: http://www.boyet.com/Articles/SimpleShuffling.html.

Scott

 

[William Stacey [MVP]]

That sounds like it should work. Good idea John. Related (kinda) question.
Say you have a collection that contains an arraylist. You export the same
Sort apis on your collection. However each object in the collection is an
internal object that contains the user object, yet you still want the sort
methods to assume sorting on value object, not on Node object. See below.
Thanks again. Cheers!

public class MyList
{
ArrayList al = new ArrayList();
public MyList()
{
}
public Add(object key, object value)
{
Node newNode = Node(key, value);
al.Add(newNode);
}
public void Sort()
{
// Use default Compare of Node.value ??
}
public virtual void Sort(IComparer comparer)
{
// Use comparer on Node.value, Not on Node object itself ??
}
}

public class Node
{
public object key;
public object value;
public Node(object key, object value)
{
this.key = key;
this.value = value;
}
}

--
William Stacey, MVP

Run the ArrayList.Sort method, passing in a custom comparer that returns -1
or 1 randomly.
?

More specific example/need. Take any ArrayList of length >=2. Now
randomize the elements in most efficient method. TIA

--
William Stacey, MVP

int[] list = {1,2,3,4,5,6};

Function to randomize the list?
Cheers!

 

[John Wood]

I am kinda assuming the CLR's quicksort routine can handle an inconsistent
response from a comparer... best to test it to make sure.

Well to answer your question, sounds like you should implement a custom
IComparer implementation that casts the objects passed in to a Node object,
gets the value out and uses that to compare.

In the second implementation of Sort (where a custom IComparer is already
passed in), your custom implementation of IComparer should still extract the
Node and the Value member, but use *their* IComparer to actually do the
comparing on the two Values. Hope that makes sense!

John

That sounds like it should work. Good idea John. Related (kinda) question.
Say you have a collection that contains an arraylist. You export the same
Sort apis on your collection. However each object in the collection is an
internal object that contains the user object, yet you still want the sort
methods to assume sorting on value object, not on Node object. See below.
Thanks again. Cheers!

public class MyList
{
ArrayList al = new ArrayList();
public MyList()
{
}
public Add(object key, object value)
{
Node newNode = Node(key, value);
al.Add(newNode);
}
public void Sort()
{
// Use default Compare of Node.value ??
}
public virtual void Sort(IComparer comparer)
{
// Use comparer on Node.value, Not on Node object itself ??
}
}

public class Node
{
public object key;
public object value;
public Node(object key, object value)
{
this.key = key;
this.value = value;
}
}

--
William Stacey, MVP

Run the ArrayList.Sort method, passing in a custom comparer that returns -1
or 1 randomly.
?

More specific example/need. Take any ArrayList of length >=2. Now
randomize the elements in most efficient method. TIA

--
William Stacey, MVP

int[] list = {1,2,3,4,5,6};

Function to randomize the list?
Cheers!

 

[William Stacey [MVP]]

hmm. After more testing. Sometimes that works, other times you get
Exception about Index outside bounds of array. Must have something to do
with compare when you sending it bogus compare results and thinking there
must be one more element to compare when there is none.

--
William Stacey, MVP

Run the ArrayList.Sort method, passing in a custom comparer that returns -1
or 1 randomly.
?

More specific example/need. Take any ArrayList of length >=2. Now
randomize the elements in most efficient method. TIA

--
William Stacey, MVP

int[] list = {1,2,3,4,5,6};

Function to randomize the list?
Cheers!

 

[William Stacey [MVP]]

Cheers!

--
William Stacey, MVP

Try this: http://www.boyet.com/Articles/SimpleShuffling.html.

Scott

 

[William Stacey [MVP]]

Seems to work pretty well. Here is the c# code if anyone else is
interested.
public void Randomize()
{
// list is an ArrayList or Array in class.
Random rand = new Random();
int randIndex;
object tmpObj;
for(int i = list.Count - 1; i >= 0; i--)
{
randIndex = rand.Next(i + 1);
if ( randIndex != i )
{
tmpObj = list;
list = list[randIndex];
list[randIndex] = tmpObj;
}
}
}

 

[Justin Rogers]

I talked with Brian Grunkmeyer on this one time. My basic issue was that I
wanted
to simulate quantum interactions. I chose to test by randomly returning whether
or
not the passed in numbers compared to each other and how. They throw the
exception
because in most cases, it is an error in your compare routine, that would cause
you to
return inconsistent results. They put the error in there on purpose to protect
you from
this happening.

I eventually found a work-around, but it escapes me.

--
Justin Rogers
DigiTec Web Consultants, LLC.
Blog: http://weblogs.asp.net/justin_rogers

hmm. After more testing. Sometimes that works, other times you get
Exception about Index outside bounds of array. Must have something to do
with compare when you sending it bogus compare results and thinking there
must be one more element to compare when there is none.

--
William Stacey, MVP

Run the ArrayList.Sort method, passing in a custom comparer that returns -1
or 1 randomly.
?

More specific example/need. Take any ArrayList of length >=2. Now
randomize the elements in most efficient method. TIA

--
William Stacey, MVP

int[] list = {1,2,3,4,5,6};

Function to randomize the list?
Cheers!

 

[William Stacey [MVP]]

Here is a version that selects first element randomly, then puts rest in
order (same way Bind does round robin.) I needed another ArrayList for
this, but may be better way. Cheers!

public void RandomizeFirst()
{
Random rand = new Random();
if ( list.Count < 2 )
return;
int randIndex = rand.Next(0, list.Count - 1);
if ( randIndex == 0 )
return;
int index = randIndex;
ArrayList newList = new ArrayList(list.Count);
for(int i = 0; i < list.Count; i++)
{
newList.Add(list[index]);
index = (index + 1) % list.Count;
}
list = newList;
}

 

[Justin Rogers]

This does the same, doesn't require the extra list, and handles a
condition with your and logic. Note if the list is small, this will
work great. Larger lists you may run into some thrasing because
of the removals and insertions. There are better algorithms for
this if you are using array's or linked lists.

private Random rand = new Random();
public void RandomizeFirst() {
if ( list.Count < 2 ) { return; }

// Rand never returns the top number
int randIndex = rand.Next(0, list.Count);
if ( randIndex == 0 ) { return; }

int endList = list.Count - 1;
for(int i = endList; i >= randIndex; i--) {
object item = list[endList];
list.RemoveAt(endList);
list.Insert(0, item);
}
}


--
Justin Rogers
DigiTec Web Consultants, LLC.
Blog: http://weblogs.asp.net/justin_rogers

Here is a version that selects first element randomly, then puts rest in
order (same way Bind does round robin.) I needed another ArrayList for
this, but may be better way. Cheers!

public void RandomizeFirst()
{
Random rand = new Random();
if ( list.Count < 2 )
return;
int randIndex = rand.Next(0, list.Count - 1);
if ( randIndex == 0 )
return;
int index = randIndex;
ArrayList newList = new ArrayList(list.Count);
for(int i = 0; i < list.Count; i++)
{
newList.Add(list[index]);
index = (index + 1) % list.Count;
}
list = newList;
}

--
William Stacey, MVP

Try this: http://www.boyet.com/Articles/SimpleShuffling.html.

Scott

 

[William Stacey [MVP]]

Thanks Justin. Will check this out. Just curious what condition I had with
logic for education purposes. Cheers!

--
William Stacey, MVP

This does the same, doesn't require the extra list, and handles a
condition with your and logic. Note if the list is small, this will
work great. Larger lists you may run into some thrasing because
of the removals and insertions. There are better algorithms for
this if you are using array's or linked lists.

private Random rand = new Random();
public void RandomizeFirst() {
if ( list.Count < 2 ) { return; }

// Rand never returns the top number
int randIndex = rand.Next(0, list.Count);
if ( randIndex == 0 ) { return; }

int endList = list.Count - 1;
for(int i = endList; i >= randIndex; i--) {
object item = list[endList];
list.RemoveAt(endList);
list.Insert(0, item);
}
}


--
Justin Rogers
DigiTec Web Consultants, LLC.
Blog: http://weblogs.asp.net/justin_rogers

Here is a version that selects first element randomly, then puts rest in
order (same way Bind does round robin.) I needed another ArrayList for
this, but may be better way. Cheers!

public void RandomizeFirst()
{
Random rand = new Random();
if ( list.Count < 2 )
return;
int randIndex = rand.Next(0, list.Count - 1);
if ( randIndex == 0 )
return;
int index = randIndex;
ArrayList newList = new ArrayList(list.Count);
for(int i = 0; i < list.Count; i++)
{
newList.Add(list[index]);
index = (index + 1) % list.Count;
}
list = newList;
}

--
William Stacey, MVP

Try this: http://www.boyet.com/Articles/SimpleShuffling.html.

Scott

More specific example/need. Take any ArrayList of length >=2. Now
randomize the elements in most efficient method. TIA

 

[Justin Rogers]

It should have read condition with your rand logic. That should
explain the problem. As was, you would never select the last
item in your list to be your first, since you were specifying
list.Count-1 as the upper bound. Next never returns the upper
bound and so in actuality you were selecting an index between 0
and list.Count - 2.


--
Justin Rogers
DigiTec Web Consultants, LLC.
Blog: http://weblogs.asp.net/justin_rogers

Thanks Justin. Will check this out. Just curious what condition I had with
logic for education purposes. Cheers!

--
William Stacey, MVP

This does the same, doesn't require the extra list, and handles a
condition with your and logic. Note if the list is small, this will
work great. Larger lists you may run into some thrasing because
of the removals and insertions. There are better algorithms for
this if you are using array's or linked lists.

private Random rand = new Random();
public void RandomizeFirst() {
if ( list.Count < 2 ) { return; }

// Rand never returns the top number
int randIndex = rand.Next(0, list.Count);
if ( randIndex == 0 ) { return; }

int endList = list.Count - 1;
for(int i = endList; i >= randIndex; i--) {
object item = list[endList];
list.RemoveAt(endList);
list.Insert(0, item);
}
}


--
Justin Rogers
DigiTec Web Consultants, LLC.
Blog: http://weblogs.asp.net/justin_rogers

Here is a version that selects first element randomly, then puts rest in
order (same way Bind does round robin.) I needed another ArrayList for
this, but may be better way. Cheers!

public void RandomizeFirst()
{
Random rand = new Random();
if ( list.Count < 2 )
return;
int randIndex = rand.Next(0, list.Count - 1);
if ( randIndex == 0 )
return;
int index = randIndex;
ArrayList newList = new ArrayList(list.Count);
for(int i = 0; i < list.Count; i++)
{
newList.Add(list[index]);
index = (index + 1) % list.Count;
}
list = newList;
}

--
William Stacey, MVP

Try this: http://www.boyet.com/Articles/SimpleShuffling.html.

Scott

More specific example/need. Take any ArrayList of length >=2. Now
randomize the elements in most efficient method. TIA

 

[Mike Schilling]

Run the ArrayList.Sort method, passing in a custom comparer that returns -1
or 1 randomly.
?

Bad idea. If you get inconsistent results (A > B sometimes but A < B other
times) during the same sort, the sort algorithm is likely to blow up.

 

[Roy Fine]

Run the ArrayList.Sort method, passing in a custom comparer that returns -1
or 1 randomly.
?

The Sort method used is the bubble sort - the end result will be jumbled,
but will be very much a function of (i.e. highly biased in favor of) the
starting order -

Consider this: The last item in the input list has a 50/50 change of being
the first item in the random list, but only a 1/n! of being the last item.
True random would suggest that the probability of any item appearing in any
slot would be uniform.

Consider generating a list of n random numbers in the range of 1..n. the
list of random numbers then corresponds to the position mapping from the the
input list to the randomized list.

regards
roy fine

More specific example/need. Take any ArrayList of length >=2. Now
randomize the elements in most efficient method. TIA

--
William Stacey, MVP

int[] list = {1,2,3,4,5,6};

Function to randomize the list?
Cheers!

 

[William Stacey [MVP]]

It does. Thanks for confirming.

 

[Jon Skeet [C# MVP]]

int[] list = {1,2,3,4,5,6};

Function to randomize the list?

The method others have given (I think!) also introduces an interesting
way of generating permutations. Here's my own implementation of the
randomization:

using System;
using System.Collections;

public class Test
{
static void Main()
{
int[] foo = {1, 2, 3, 4, 5};
Randomize(foo);
foreach (int f in foo)
{
Console.Write ("{0} ", f);
}
Console.WriteLine();
}

static Random rng = new Random();
static void Randomize(IList list)
{
for (int i=list.Count-1; i > 0; i--)
{
int swapIndex = rng.Next(i+1);
if (swapIndex != i)
{
object tmp = list[swapIndex];
list[swapIndex] = list;
list = tmp;
}
}
}
}

(Note that the > 0 is deliberate here; it is logically >= 0 but the
last step will always be a no-op.)

Now, a permutation can be expressed just as the sequence of random
numbers generated. For up to 20 elements, this can be expressed as a
single long, which can then be passed in as a parameter:

using System;
using System.Collections;

public class Test
{
static void Main()
{
int[] foo = {1, 2, 3, 4};


for (int i=0; i < 4*3*2*1; i++)
{
IList copy = (IList) foo.Clone();
Permute(copy, i);
foreach (int f in copy)
{
Console.Write ("{0} ", f);
}
Console.WriteLine();
}
}

static void Permute(IList list, long permutation)
{
for (int i=list.Count-1; i >= 0; i--)
{
int swapIndex = (int)(permutation%(i+1));
permutation = permutation/(i+1);
if (swapIndex != i)
{
object tmp = list[swapIndex];
list[swapIndex] = list;
list = tmp;
}
}
}
}

For longer lists, you could pass in an array of ints (swapNums, say),
of the same length as the list, and with swapNums[index] being in the
range [0, index]. It would be very easy to iterate through a series of
such arrays (increment the final index; if it goes out of bounds, set
it to 0 and increment the previous index, etc).

 

[William Stacey [MVP]]

Here is a Permuted Order class to find the next permutation of any ArrayList
using Lexicographic order based on HashCodes.
I would prefer to use Object Reference int as the order key as would not
have to call GetHashCode() on each object in arraylist, but can't figure out
a way to get object ref int in a safe context. Maybe not good either as GC
can move refs - right?

Note the Array itself keeps the "state" (i.e. the current order of its
objects) so Methods can be static as done here. A call to GetNext(array),
just moves around objects in the Array to give you next permuted
combination. This is nice as you don't have to build all combinations first
and you can add and remove items as needed.

You can have duplicate objects (i.e. duplicate hashcodes) in the array or
add or delete objects from array and function will still work, but may sort
the array again to start perms from top again. If all hashcodes are unique,
number of permutations is factorial of unique items. If have some dup
items, number of permutations depends on number of unique items, number of
dup items, etc. For example, try the following with ArrayList of {1,2,3}
and {0,0,1} to see the difference. First will yield 6 combinations, second
will yield 3 (not 2 or 6 as you may first think.) Anyway, here is the code.
Cheers!

/// <summary>
/// Summary description for PermutedOrder.
/// </summary>
public class PermutedOrder
{
private static bool reset;

private PermutedOrder()
{
}

internal class HashComparer : IComparer
{
#region IComparer Members

public int Compare(object x, object y)
{
int xHash = x.GetHashCode();
int yHash = y.GetHashCode();
if ( xHash == yHash )
return 0;
if ( xHash < yHash )
return -1;
return 1;
}
#endregion
}

public static void SortArray(ArrayList values)
{
if ( values == null )
throw new ArgumentNullException("values");
if ( values.Count < 2 )
return;
values.Sort(new HashComparer());
}

/// <summary>
/// Find the next permutation using Lexicographic order of hash codes
returned by array objects.
/// Normally, the array would start sorted in hash code order, but is not
required.
/// Adding or deleting elements is ok too as the function will re-sort when
needed.
/// Call GetNext to have array arranged to next permutation. Call GetNext
N number of times
/// to see all permutations of unique objects in array (i.e. unique
hashcodes.)
/// </summary>
/// <param name="values">ArrayList of objects to permutate.</param>
public static void GetNext(ArrayList values)
{
if ( values == null || values.Count < 2 )
return;
int i = values.Count - 1;
while ( values[i-1].GetHashCode() >= values.GetHashCode() )
{
i = i - 1;
if ( i == 0 )
{
reset = true;
values.Sort(new HashComparer());
return;
}
}
int j = values.Count;
while ( values[j-1].GetHashCode() <= values[i-1].GetHashCode() )
j = j - 1;
Swap(values, i-1, j-1); // swap values at positions (i-1) and (j-1)
i++;
j = values.Count;
while (i < j)
{
Swap(values, i-1, j-1);
i++;
j--;
}
}

/// <summary>
/// Returns the number of permutations the ArrayList could be ordered by.
/// A simple Factorial function does not work as {0,0,1} would yield 3
perms, not 6.
/// </summary>
/// <param name="values"></param>
/// <returns></returns>
public static int PermutationsCount(ArrayList values)
{
if ( values == null || values.Count == 0 )
return 0;
if ( values.Count == 1 )
return 1;
int permCount = 0;
ArrayList tmp = (ArrayList)values.Clone();
SortArray(tmp);
reset = false;
while( reset == false )
{
GetNext(tmp);
permCount++;
}
return permCount;
}

private static void Swap(ArrayList values, int i, int j)
{
object tmp = values;
values = values[j];
values[j] = tmp;
}
} // End PermutedOrder Class

//
// *** Test the class ***
//
private void button20_Click(object sender, System.EventArgs e)
{
ArrayList values = new ArrayList();
// {0,1,2} will yield 6 permutations.
values.Add(0);
values.Add(1);
values.Add(2);
// Try other values to see effect of duplicate objects on permutations.
// Below will yield 3 permutations, not 4.
// values.Add(0);
// values.Add(0);
// values.Add(1);

int permsCount = PermutedOrder.PermutationsCount(values);
Console.WriteLine("Number of Permutations:"+permsCount);

PermutedOrder.SortArray(values);
Console.WriteLine(GetArrayAsString(values));

for(int i = 0; i < permsCount - 1; i++)
{
PermutedOrder.GetNext(values);
Console.WriteLine(GetArrayAsString(values));
}
}

private string GetArrayAsString(ArrayList values)
{
string s = null;
for(int i = 0; i < values.Count; i++)
{
s = s + values.ToString() + (( i == values.Count - 1 ) ? "" : ", ");
}
return s;
}

 

[John Wood]

Well.. c'mon now, it took me all of 10ms to think up... you have to give me
points for innovation at least!