I want to make limitation for random class in c# like generate random variables from 2 ranges without repeat it? example :
Xpoints[i] = random.Next(0, 25);
Ypoints[i] = random.Next(0, 12);
where 25 we 12 is image dimension so I need all pixels in this image but random ? any suggestion if I use this code i didn't get some pixels and some pixels repeated
Have a look at the Fisher-Yates Algorithm:
http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
It's easy to implement, and works really well.
It shuffles an array of digits, then you can access them sequentially if you like to ensure no repeats.
Update Simplified by not requiring any specific hashing [1]
Update Generalzed into generic SimpleShuffle extension method
public static IEnumerable<T> SimpleShuffle<T>(this IEnumerable<T> sequence)
{
var rand = new Random();
return sequence.Select(i => new {i, k=rand.Next()})
.OrderBy(p => p.k)
.Select(p => p.i);
}
I though in addition to downvoting (shouting? sorry :)) Anx's answer I thought it'd be nicer to also show what my code would look like:
using System;
using System.Linq;
using System.Collections.Generic;
namespace NS
{
static class Program
{
public static IEnumerable<T> SimpleShuffle<T>(this IEnumerable<T> sequence)
{
var rand = new Random();
return sequence.Select(i => new {i, k=rand.Next()}).OrderBy(p => p.k).Select(p => p.i);
}
public static void Main(string[] args)
{
var pts = from x in Enumerable.Range(0, 24)
from y in Enumerable.Range(0, 11)
select new { x, y };
foreach (var pt in pts.SimpleShuffle())
Console.WriteLine("{0},{1}", pt.x, pt.y);
}
}
}
I totally fixed my earlier problem of how to generate a good hash by realizing that we don't need a hash unless:
a. and b. are false in this case and c. was even going to be a problem (depending on what the OP was requiring). So now, without any strings attached, no more worries about performance (even the irrational worries),
Good luck!
[1] Incidentally this makes the whole thing more flexible because I no longer require the coords to be expressed a byte[]; you can now shuffle any structure you want.
You might want to use a shuffle algorithm on a list of the indexes (e.g. 25 elements with the values 0..24 for the X axis) instead of random.
By design random doesn't guarantee that no value is repeated; repetitions are very likely.
See also: Optimal LINQ query to get a random sub collection - Shuffle (look for the Fisher-Yates-Durstenfeld solution)
I also believe, Random should not be predictable, and we shouldn't even predict that the value will not be repeating.
But I think sometimes it could be required to randomly get non repeating int, for that we need to maintain state, like for particular instance of Random class, what all values were returned.
here is a small quick and dirty implementation of an algorithm which I thought just now, I am not sure if it is the same as Fisher-Yates solution. I just wrote this class so that you can use it instead of System.Random class.
So It may help you for your requirement, use below NonRepeatingRandom class as per your need...
class NonRepeatingRandom : Random
{
private HashSet<int> _usedValues = new HashSet<int>();
public NonRepeatingRandom()
{
}
public NonRepeatingRandom(int seed):base(seed)
{
}
public override int Next(int minValue, int maxValue)
{
int rndVal = base.Next(minValue, maxValue);
if (_usedValues.Contains(rndVal))
{
int oldRndVal = rndVal;
do
{
rndVal++;
} while (_usedValues.Contains(rndVal) && rndVal <= maxValue);
if (rndVal == maxValue + 1)
{
rndVal = oldRndVal;
do
{
rndVal--;
} while (_usedValues.Contains(rndVal) && rndVal >= minValue);
if (rndVal == minValue - 1)
{
throw new ApplicationException("Cannot get non repeating random for provided range.");
}
}
}
_usedValues.Add(rndVal);
return rndVal;
}
}
Please not that only "Next" method is overridden, and not other, if you want you can override other methods of "Random" class too.
Ps. Just before clicking "Post Your Answer" I saw sehe's answer, I liked his overall idea, but to hash 2 bytes, creating a 16 byte hash? or am I missing something? In my code I am using HashSet which uses int's implementation of GetHashCode method, which is nothing but that value of int itself so no overhead of hashing. But I could be missing some point as it is 3:59 AM here in India :)
Hope it helps salamonti...
The whole point of random numbers is that you do get repeats.
However, if you want to make sure you don't then remove the last chosen value from your array before picking the next number. So if you have a list of numbers:
index = random.Next(0, originallist.Length);
radomisedList.Add(originalList[index]);
originalList.RemoveAt(index);
The list will be randomised yet contain no repeats.
Instead of creating image through two one-dimensional arrays you should create an image through one two-dimensional matrix. Each time you get new random coordinate check if that pixel is already set. If it is then repeat the procedure for that pixel.
