Shuffling an array of integers for making secure key pad

Question

I have created a method that shuffles an array of integers between 0 to 9 to make a secure key pad for a page in my website. I have made it like:

int[] array = new int[10] {0,1,2,3,4,5,6,7,8,9};
List<int> numbs = new list<int>();
Random r = new Random();
for (int i = 0; i < array.Lenght;i++) {
   Boolean b = true;
   while (b){
      if (i == r.Next(10)){
          numbs.Add(array[i]);
          b = false;
      }
   }
}

I know that this code has a very poor performance because the Random must generate a random number again and again and I don't know how many times it should run to generate a value which is equal to i. So, I wanna know what the best way to randomize the int array is.

Besides the poor performance, it doesn't work at all. All the code does is pick numbers by random until you find one that is the same as the current number, then add the current number to the array. You end up with the numbers in the same order as the original. — Guffa, Aug 02 '14 at 18:49

score 2 · Accepted Answer · answered Aug 02 '14 at 18:21

2

One of the more efficient methods for shuffling data with a good distribution is the Fisher-Yates algorithm.

answered Aug 02 '14 at 18:21

Albin Sunnanbo

46,430
8
69
108

ProgrammingLlama · Answer 2 · 2014-08-03T22:29:05.683

0

You could use Linq:

Random rn = new Random();
List<int> srcNumbers = new List<int>() { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
List<int> endNumbers = srcNumbers.OrderBy(x => rn.NextDouble()).ToList();

For 1000000 numbers, the linq/lambda method takes 393 miliseconds to sort them randomly on an i7 4770k CPU. After about 30 seconds with the OP's original method, I was only 4300 elements in.

edited Aug 03 '14 at 22:29

answered Aug 02 '14 at 18:19

ProgrammingLlama

36,677
7
67
86

Are you sure this will work? I would expect that the key and comparisons functions are required to be a pure function, or at least give consistent results when called multiple times. – Aug 02 '14 at 18:20
@delnan C# uses the data returned by the lambda expression to evaluate that entry against the others. Therefore, by supplying a random number, it is ordered randomly. – ProgrammingLlama Aug 02 '14 at 18:22
But does it guarantee to only evaluate the function once per entry? A similar concern applies to the second version. – Aug 02 '14 at 18:23
@delnan It relies on the underlying sorting algorithm of .NET so I think QuickSort will be applied and will obviously loop over elements. I would expect it to be more performant than the OP's method. – ProgrammingLlama Aug 02 '14 at 18:26
In other words, it's not guaranteed to work and you don't even know whether it will actually work. Gotcha ;-) – Aug 02 '14 at 18:26
@delnan Performance and whether it works are not are two different things. They wanted a way to shuffle an array and I provided them a completely effective way of doing this which is more performant than the OP's – ProgrammingLlama Aug 02 '14 at 18:28
I doubt **whether it works at all** and so far you haven't addressed these concerns. – Aug 02 '14 at 18:29
@delnan Yes I have, see my first response explaining how it works. I'm not sure how you're missing this. http://rextester.com/live/KJN9139 - Seems to work just fine for me? Perhaps try things out yourself before being adamant that things won't work. – ProgrammingLlama Aug 02 '14 at 18:33
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/58553/discussion-between-delnan-and-john). – Aug 02 '14 at 18:44

The Paramagnetic Croissant · Answer 3 · 2014-08-02T18:28:48.983

0

Instead of brute-forcing the numbers in the array, how about picking a random element from the original array, adding it to the new one and then removing it? Something like (sorry for pseudo code, I don't speak C#):

int[] orig = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int[] copy = {};

for (int i = 0; i < 10; i++) {
    int index = random(orig.size);
    copy.push(orig[index]);
    orig.removeAt(index);
}

edited Aug 02 '14 at 18:28

answered Aug 02 '14 at 18:20

The Paramagnetic Croissant

9,223
3
25
38

This is the "original" Fisher-Yates shuffle which is relatively inefficient (quadratic complexity). The usual way to fix that issue is to swap the element to be removed with the last element first (and if you leave it there instead of removing it, it shuffles the array in-place). – Aug 02 '14 at 18:26
No, that just moves the cause of the quadratic complexity elsewhere (the random access at `orig[index]`). And no, for ten elements it doesn't matter, but for ten elements OP's version is also good enough. – Aug 02 '14 at 18:27
@delnan "that just moves the cause of the quadratic complexity elsewhere (the random access at `orig[index]`" - ah right. I forgot about that. – The Paramagnetic Croissant Aug 02 '14 at 18:29

Shuffling an array of integers for making secure key pad

3 Answers3