0

I need to create a random array of int with certain parameters. 

int[] test = new int[80];
Random random = new Random();

I need to assign 1's and 0's, randomly to the array. I know how to do that.

test[position] = Random.Next(0,2);//obviously with a for loop

But I need to have exactly 20 1's, but they need to be randomly positioned in the array. I don't know how to make sure that the 1's are randomly positioned, AND that there are exactly 20 1's. The rest of the positions in the array would be assigned 0.

Z10987654321X
  • 124
  • 3
  • 14
  • So you don't want an array filled with random data, you want a predefined array (`var arr = new int[] { 1,1,... (20 times), 0,0, ..(the rest)};`) randomly shuffled. That's a different thing. Try a `for` loop with a few iterations and randomly exchange two elemets. – Maximilian Gerhardt Mar 10 '17 at 18:17
  • Generate a list of 20 1's and N-20 0's, then shuffle it. – CodeCaster Mar 10 '17 at 18:17
  • use Random to also generate a random index. You would first have to check if that slot was assigned, then keep calling random(0,80) until you get an unused slot. – OldProgrammer Mar 10 '17 at 18:18

3 Answers3

2

I think you need to turn your thinking around.

Consider:

var cnt = 20;
while (cnt > 0) {
    var r = Random.Next(0, 80);
    if (test[r] != 1) {
        test[r] = 1;
        cnt--;
    }
}

Expanding explanation based on comments from CodeCaster. Rather than generate a random value to place in the array, this code generates and index to set. Since C# automatically initializes the test array to 0 these values are already set. So all you need is to add your 1 values. The code generates a random index, tests it to see if it isn't 1, if so it sets the array element and decrements a count (cnt). Once count reaches zero the loop terminates.

This won't properly function if you need more values than 0 and 1 that is true. Of course the questions explicitly stated that these were the needed values.

"This causes horrible runtime performance". What!? Can you produce any prove of that? There is a chance that the index generated will collide with an existing entry. This chance increases as more 1's are added. Worst case is there is a 19/80 (~23%) chance of collision.

Dweeberly
  • 4,668
  • 2
  • 22
  • 41
  • Alright, thank you for adding this very thorough explanation. This way people will be warned that this is suboptimal code, and it's up to them when they copy-paste it into their program. Because of the potential collisions, the performance is suboptimal - and not properly random. A proper shuffle is the optimal solution. – CodeCaster Mar 10 '17 at 19:40
-1

If you know you need exactly 20 of one value, a better way to go about this is to pre-populate the array with the required values and then shuffle it.

Something like this should work:

int[] array = new int[80];
for (int i = 0; i < 80; i++)
{
    int val = 0;
    if (i < 20)
    {
        val = 1;
    }
    array[i] = val;            
}

Random rnd = new Random();
int[] shuffledArray = array.OrderBy(x => rnd.Next()).ToArray();
clinton3141
  • 4,751
  • 3
  • 33
  • 46
JonBee
  • 249
  • 1
  • 5
-2

You can do

for (int i = 0; i < 20; i++)
{
    var rand = random.Next(0,80);
    if (test[rand] == 1)
    {
        i--;
        continue;
    }
    test[rand] = 1;
}

Remaining are automatically zero.

Nikhil Agrawal
  • 47,018
  • 22
  • 121
  • 208
  • 2
    That won't work if the random returns the same index twice. – OldProgrammer Mar 10 '17 at 18:17
  • @OldProgrammer: Fixed. – Nikhil Agrawal Mar 10 '17 at 18:19
  • It's simply a too naive implementation that runs the loop an unnecessarily large amount of times, and the setting to 0 is also unnecessary. – CodeCaster Mar 10 '17 at 18:32
  • @CodeCaster: Even better, then it loops just 20 then. Thanks. – Nikhil Agrawal Mar 10 '17 at 18:33
  • 1
    No, it doesn't loop just 20 times. It's true that it at most sets 20 indices to 1, but this code loops, in theory, an infinite number of times if only 19 different indices are generated. This "looping and generating a random index" approach is the wrong approach for this problem altogether, and all answers are equally wrong. – CodeCaster Mar 10 '17 at 18:35
  • @CodeCaster: Shuffling after entering first 20 values = 1 is also costly. – Nikhil Agrawal Mar 10 '17 at 18:37
  • 1
    But shuffling a list through Fisher-Yates has a definitive end state and runs in a time of `O(N)`. Just because something looks random to you doesn't mean it's the correct approach. – CodeCaster Mar 10 '17 at 18:37