3

I remember to see a method seems to buble sort, where can unsort items.

For example, I was trying to show randomize items from 0 to 10, using Random class. But I guess is not the best choice.

So, I guess creating an extension for IEnumberable, List or array, whatever can be a best way.

Darf Zon
  • 6,268
  • 20
  • 90
  • 149
  • possible duplicate of [Optimal LINQ query to get a random sub collection - Shuffle](http://stackoverflow.com/questions/1651619/optimal-linq-query-to-get-a-random-sub-collection-shuffle) – Muad'Dib Jan 19 '12 at 22:01
  • what do you mean by items from 0 to 10? the first 10 items? a list of size 10? – Muad'Dib Jan 19 '12 at 22:03
  • Yes, I mean, to have an array with the elementos { 0, 1, 2, ... 9 } – Darf Zon Jan 19 '12 at 22:28

5 Answers5

16

You are looking for a shuffle, a good example for randomized re-ordering is the Fisher-Yates Shuffle.

Here's an implementation by Jon Skeet in C#.

Community
  • 1
  • 1
BrokenGlass
  • 158,293
  • 28
  • 286
  • 335
7

The algorithm that looks like bubble sort would be:

for i= 0:(len(x)-1):
    j = random(i,len(x)-1)
    swap(x[i],x[j])

Assume that random(a,b) returns a random integer c such that a<=c<=b.

And, this algorithm is called "Fisher Yates Shuffle".

FWIW, you cannot "truly" shuffle a big array with the standard inbuilt random number generators. A 21-item shuffle has a entropy of 65 bits, where as most RNGs are of 64 bits or 32 bits.

ElKamina
  • 7,747
  • 28
  • 43
0

This will give you a random values from 0 to 10 (including 10):

int[] randomNumbers = Shuffle(Enumerable.Range(0, 11), new Random()).ToArray(); 

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random random)
{
    T[] list = source.ToArray();
    int count = list.Length;

    while (count > 1)
    {
        int index = random.Next(count--);
        T temp = list[index];
        list[index] = list[count];
        list[count] = temp;
    }
    return list;
}
Chuck Savage
  • 11,775
  • 6
  • 49
  • 69
  • It's not 'basically' Fisher-Yates, it's random selection from a list. About all it has in common is that it's fair and unbiased. It's also O(n^2) runtime. – Nick Johnson Jan 19 '12 at 23:23
  • Why on earth are you seeding the random class with the time in such a bizarre manner? The random class automatically seeds itself with the current time. – Eric Lippert Jan 19 '12 at 23:26
  • And Nick is of course correct; this is extraordinarily inefficient if the list is large. – Eric Lippert Jan 19 '12 at 23:27
  • Fisher-Yates is select numbers from a hat, as they are removed, so does the numbers remaining shrink. By the way, the OP doesn't require Fisher-Yates, I was just giving credit where I thought credit was due, it doesn't deserve a -1. OP just wants random numbers from 0 to 10. – Chuck Savage Jan 19 '12 at 23:29
  • @ChuckSavage, there are a few disadvantages here. 1) It's a shortcut over a useful and efficient algorithm without the actual advantage of being shorter (see Jon Skeet's FY implementation in a linked answer). 2) As you say, the OP is only interested in shuffling 0 to 10, but the OP isn't the only person who might find this particular question and its answers useful. The audience is the internet, not just the asker, and they might be sorting larger lists. I haven't downvoted, but that's not to say a downvote isn't justifiable in light of better alternatives. – Anthony Pegram Jan 19 '12 at 23:50
  • @Eric Lippert why the random seed? Because if it is just Random() then the seed doesn't change often enough. I just tested, mine vs Random() and Random() on its own repeats the sequence about 40 times for Random() and mine about 10 times. So I'd say my bizarre manner is more random. – Chuck Savage Jan 19 '12 at 23:57
  • 3
    Chuck, all I think you have proven is that you shouldn't create Random instances inside loops. 10 repeated sequences versus 40, you shouldn't want any unless you are actually testing the repeatable results of PRNGs. The second thing you may have proven is that your version was slower, because it gets out of the realm of repeats in a lower number of iterations. – Anthony Pegram Jan 20 '12 at 00:03
  • modified to swap values, hopefully this is more efficient than using a list. – Chuck Savage Jan 20 '12 at 00:03
  • @Anthony Pegram thanks for the tip, moved random to an argument, which removes any repeats. – Chuck Savage Jan 20 '12 at 00:08
-3

you can use linq...

var result = Enumerable.Range(0,10).OrderBy( n=> Guid.NewGuid() )
Muad'Dib
  • 28,542
  • 5
  • 55
  • 68
  • Except that LINQ's `OrderBy`/`ThenBy` uses Quicksort under the hood, give it O( n log n ) performance (average case), not to mention requiring additional space. The "standard" shuffle algorithm is O(n)and requires no additional space. – Nicholas Carey Jan 19 '12 at 22:33
  • 1
    No, Never use this. http://blogs.msdn.com/b/ericlippert/archive/2011/01/31/spot-the-defect-bad-comparisons-part-four.aspx – L.B Jan 19 '12 at 22:36
  • @L.B, OrderBy is stable, it doesn't suffer from the same drawback as the Sort method on lists. For a quick one-off shuffle over a small sequence, using OrderBy isn't *terrible*, but a better algorithm will certainly be more scalable. – Anthony Pegram Jan 19 '12 at 23:04
  • 3
    This is a terribly bad idea. **Guids are not guaranteed to be random, they are guaranteed to be unique.** Use guids to make unique identifiers; use them for nothing else. Guids are not sort keys. – Eric Lippert Jan 19 '12 at 23:25
  • And of course that's a valid point on Guids. "Right tools for right jobs" wins again. – Anthony Pegram Jan 19 '12 at 23:34
-3

Interesting problems, I propose to leave work linq:

IEnumerable<int> list = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
Random rnd = new Random();
list = list.Select(i => new { value = i, rank = rnd.Next(list.Count()) }).OrderBy(n => n.rank).Select(n => n.value);
Khamzat
  • 1
  • 1