CODEWITHSUNDEEP
algorithm
Ray Jenkins
Ray Jenkins

Reputation: 123

Creating a random ordered list from an ordered list

I have an application that takes the quality results for a manufacturing process and creates graphs both to show Pareto charts of the bad, and also to show production throughput.

To automate the task of testing these statistical procedures I would like to deterministically be able to add records into the database and have the quality tech go to certain graphs and compare to a known good graph. But, I also would like to simulate the results so they would go into the database as if a user was running through the testing process.

One idea I have had is to fill a list with i number good, j number bad1, k number bad 2, etc. And then somehow randomly sort the list before insertion into the database.

So, my question, is there a standard algorithm to take a sorted list of values and create a randomly sorted list?

Upvotes: 6

Views: 6335

Answers (6)

Neil Williams
Neil Williams

Reputation: 12578

You'll want to use a shuffle algorithm. Make sure to use a proper shuffle algorithm and not a home-baked one, because it may introduce some form of subtle pattern to the data. See this post by Jeff Atwood about the problem with using "random enough" shuffles.

Upvotes: 12

quamrana
quamrana

Reputation: 39354

A simple answer is to have an array or vector, loop once through it, and for each position visited, pick an element at random from the remainder of the list and swap it with the current element.
You need a reasonable random number generator for this.

Upvotes: 0

albertein
albertein

Reputation: 27120

Random rnd = new Random();
List<int> orderedList = new List<int>();
List<int> randomList = new List<int>();
while (orderedList.Count != 0)
{
    int index = rnd.Next(0, orderedList.Count);
    randomList.Add(orderedList[index]);
    orderedList.RemoveAt(index);
}

Upvotes: 0

Daniel Spiewak
Daniel Spiewak

Reputation: 55123

Depends on what you need for "randomness". The easiest way is probably just to through all of the elements into a hash set and iterate over the result. The order you get will be deterministic, but for most intents and purposes can be considered random. Alternatively, you can generate random numbers between [0..length] of the list, picking out elements and pushing them onto a new list. Assuming that list removal is constant time, the result would be a random list generated with O(n) efficiency.

Upvotes: 0

John Boker
John Boker

Reputation: 83709

the way i used to do this was to have a loop that ran a number of times that would generate two random numbers between 0 and the length of the list, then swap those two elements.

Upvotes: -1

massimogentilini
massimogentilini

Reputation: 4172

Our host has a very good article about card shuffling, I believe some good ideas can be adopted
http://www.codinghorror.com/blog/archives/001008.html

Upvotes: 0

Related Questions