5

Looking to shuffle four variables (trying to change the order they appear in on a multiple choice list).

I've been poking around for a while but I can't quite get my head around the logic, and looking up random shuffles in past questions gives super-detailed algorithms that are beyond my newbie skills (and the needs of this program I'm trying to write, I'd just like to make a multiple-choice image picker).

Ideally I'd like something that follows this pseudocode:

// int Answer1 = Random(min1 max4)

// int Answer2 = Random(min1 max4)

// int Answer3 = Random(min1 max4)

// int Answer4 = Random(min1 max4)

// If Answer 1 equals ANY of the other three, re-randomize Answer1 and loop.

// Loop through this cycle for all answers.

I'd post my current regular code, but frankly, it's garbage. :( This seems like a simple enough problem but I just can't get it right.

Thanks in advance!

user236494
  • 65
  • 1
  • 4

4 Answers4

8

Shuffling - http://www.codinghorror.com/blog/archives/001008.html

Though, don't use a guid, use a random number:

//create only once, please
static readonly Random random = new Random();

and then:

var numbers = Enumerable.Range(1, 4);
var shuffle = numbers.OrderBy(a => random.NextDouble());
Kobi
  • 135,331
  • 41
  • 252
  • 292
  • Curious why you wouldn't use a GUID. – Alastair Pitts Jan 06 '10 at 06:46
  • Personal preference, really. Looking around some more, this is better: http://stackoverflow.com/questions/1287567/c-is-using-random-and-orderby-a-good-shuffle-algorithm (in fact, the question is why *no*t to use this method!) – Kobi Jan 06 '10 at 07:06
  • Generating a GUID is more expensive and has some fixed components. If you want a pseudo-random number, then use a pseudo-random number. Period. – Joey Jan 06 '10 at 08:16
  • One cannot shuffle numbers properly by sorting them according to a "random order comparator", since every comparator must be reflexive, asymmetric and transitive. Random number generators are none of these. – Roland Illig Aug 26 '11 at 06:07
  • @Roland - Not really. A *good* comparer must be these things, but we are not looking for consistent or well-defined behavior. Besides, **that is not what I did here at all** - I *don't* have a comparer that returns random 1 0 or -1. I assign a random number to each index (once), and sort by those numbers. I don't do anything less random than the other answers, only less efficient. – Kobi Aug 26 '11 at 06:23
  • Have you measured how often the random number generator is called in this code? I very much doubt it will always be called exactly four times. – Roland Illig Aug 26 '11 at 06:32
  • @Roland - You can easily confirm it: http://ideone.com/nnNat : I'm pretty sure that's the defined behavior of `OrderBy` (In theory, you can have a collection you can only iterate once, and Linq would still work). – Kobi Aug 26 '11 at 06:43
  • Ok, I take everything back, thanks for the clarification. I didn't know about collections that can be iterated only once; the pattern looked very similar to the wrong "random comparator" pattern; I didn't find a word in the specification that explicitly mentioned how often the "key function" is called. – Roland Illig Aug 28 '11 at 18:41
5

Well, technically, who cares if it's just 4 numbers of 400 numbers. You should be using an implementation of Fisher-Yates shuffle. However, to make it easier to understand:

var possibleNumbers = new List<int>(Enumerable.Range(1, 4));
var result = new List<int>(4);
var rnd = new Random();
while (possibleNumbers.Count > 0) {
    int r = rnd.Next(possibleNumbers.Count);
    result.Add(possibleNumbers[r]);
    possibleNumbers.RemoveAt(r);
}

The algorithm demonstrated above is basically Fisher-Yates shuffle. In practice, you don't use two distinct lists to hold stuff. You simply choose a random element from the part of the array you haven't fixed yet and move it to its place. The beginning of the single list will be fixed elements while the end will be the possibilities.

Community
  • 1
  • 1
Mehrdad Afshari
  • 414,610
  • 91
  • 852
  • 789
5

I like this extension method:

static class IListExtensions {
    public static void Shuffle<T>(this IList<T> list, Random rg) {
        for (int i = list.Count; i > 1; i--) {
            int k = rg.Next(i);
            T temp = list[k];
            list[k] = list[i - 1];
            list[i - 1] = temp;
        }
    }
}

Then:

Random rg = new Random();
List<int> list = Enumerable.Range(1, 4).ToList();
list.Shuffle(rg);

Now list is a shuffling of {1, 2, 3, 4}.

The algorithm that I used here is the Fisher-Yates shuffle.

jason
  • 236,483
  • 35
  • 423
  • 525
  • +1 Like the extension method and generic to sort different kinds of lists. Also can plug in algorithm of choice without affecting callers. – John K Jan 06 '10 at 05:47
  • 1
    @jdk: In particular, one could pass in an implementation of Mersenne Twister which has enough internal states to ensure that we have a truly unbiased shuffler for lists the size of a deck of playing cards (gamble gamble!). Or one could pass in a lava lamp shuffler (http://www.lavarnd.org/). – jason Jan 06 '10 at 05:54
  • Efficient algorithm choice too - sorts in place, doesn't generate a second list. – John K Jan 06 '10 at 06:49
0
        Random rand = new Random();
        List<int> choices = new List<int>() { 1, 2, 3, 4 };

        while (choices.Count > 0)
        {
            int index = rand.Next() % choices.Count;
            int choice = choices[index];
            Console.WriteLine(choice);
            choices.RemoveAt(index);
        }

edit - Instead of just printing the numbers, you could obviously add them to a new list.

Sapph
  • 6,118
  • 1
  • 29
  • 32
  • +1 Like the modulus to put the random number in range of the decreasing choices size. – John K Jan 06 '10 at 06:47
  • @John: this code is a very bad idea, since the random numbers will not be distributed equally. Don't use `rnd.Next()` when you really want `rnd.Next(int)`, which does all the nasty work for you. – Roland Illig Aug 26 '11 at 06:12
  • @RolandIllig why is the code bad? Is it something fundamental about the shuffling method or is it just because of the `MAXINT % choices`-part not necessarily evenly dividing up? If the latter, is it really fair to say it is a *very* bad idea (as opposed to a not ideal idea)? The skew from uniform does not seem very large even with a "low" maxint like $2^31$ unless the size of your choices pool is in the millions. – Meowf Oct 20 '21 at 13:52
  • 1
    @Meowf the bias in randomness is one bad thing about the code. The other is the complexity class. For a list of 4 items, it is perfectly fine to remove one of the items from the middle. Since the code from this answer is general enough to be used for lists of a million items as well, performance will degrade in such a case. The standard shuffle algorithm doesn't have this drawback. – Roland Illig Oct 21 '21 at 18:05