c# Array timeout error

Question

I'm having difficulties since the program seems to work but gets stuck on developing and displaying the final array. It should have 45 elements each number 1 - 45 but generated in a random order with no duplicates.

    using System;

    namespace RandomArray
    {
        public class RandomArrayNoDuplicates
        {
            static Random rng = new Random();
            static int size = 45;
            static void Main()
            {
                int [] array = InitializeArrayWithNoDuplicates(size);
                DisplayArray(array);
                Console.ReadLine();
            }


            /// <summary>
            /// Creates an array with each element a unique integer
            /// between 1 and 45 inclusively.
            /// </summary>
            /// <param name="size"> length of the returned array < 45
            /// </param>
            /// <returns>an array of length "size" and each element is
            /// a unique integer between 1 and 45 inclusive </returns>
            public static int[] InitializeArrayWithNoDuplicates(int size)
            {
                int[] arr = new int[size];

                for (int i = 0; i < size; i++)
                {
                    int number = rng.Next(1, size + 1);
                    arr[i] = number;
                    if (i > 0)
                    {
                        for (int j = 0; j <= i; j++)
                        {
                            if (arr[j] == arr[i])
                            {

                                i = i - 1;

                            }
                            else if (arr[i] != arr[j])
                            {
                                arr[i] = number;
                            }
                        }
                    }
                }
                return arr;
            }
            public static void DisplayArray(int[] arr)
            {
                for (int x = 0; x < size; x++)
                {
                    Console.WriteLine(arr[x]);
                }
            }
        }
    }

It should check through element to check for duplicates after each element in the array is generated. Tips on a better way to approach this?

Why don't you start with an array with the numbers 1-45 and then scramble it? — Leonard Brünings, Aug 27 '17 at 03:50
Required to generate each number randomly and then add it to the array. — PotatoFries, Aug 27 '17 at 04:04
@PotatoFries - Why do you say that? It doesn't say that in the `summary`. — Enigmativity, Aug 27 '17 at 04:21

Christopher · Answer 1 · 2017-08-27T05:48:07.927

The more numbers you already have in the array, the more likely there is already a duplicate in it. With the last number there is literally a 44/45 chance to get a Duplicate. And in the worst case, you have to check all 44 elements to even find the duplicate. That is only going to get worse with more array elements.

I can only repeat Leonardos Advise: Create a array with the wanted numbers. Then scramble the order of said numbers. I call that the "lottery problem" and usually use two List(int) for it as that is the most intuitive. I should be able to find some example code as I use to write that somewhat often.

I jsut did this quick mockup code in notepad++. Might be mixing up lenght and count or messing up the indexes, but you should get the gist. I hope:

List<int> input = new List<int>();
List<int> output;

//Initialise Input
for(int i = 0; i < 45; i++)
  input[i]=i;
 
//Shuffle the array into output
random rng = new Random();  

output = new List<int>(input.Lenght);

for(; input.Lenght > 0;){
  int index = rng.NextInt(input.Lenght);
  int value = input(index);
  input.remove(index);
  
  output.add(value);
}

//output is a fully randomized version of input now

I originally did this code in Java, where Remove() has the nice property of returning the removed element making the inside of the loop a one liner.

score 0 · Answer 2 · answered Aug 27 '17 at 05:49

0

Yes, agreed with all, generating a random array is far most costly than scrambling a sorted array. Therefore, you should take scrambling option.

In this regards, please check this link Best way to randomize an array with .NET

answered Aug 27 '17 at 05:49

Tanjeer

89
4

score 0 · Answer 3 · answered Aug 27 '17 at 06:14

You can do this with Random, rather than Scramble, but your logic is at fault. In my example, I build an array with all possible numbers and another with bools, initially false. Every time I use a number I set used to true. Then next time I reduce the range of the Random by one and take the nth unused value from my number array. Then at the end (and this is very much where you came unstuck) the last value is not random - it is merely the last available number.

One other point, you must seed random, otherwise it is not random at all!.

The code looks like this:

namespace RandomArray
{
    class RandomArrayNoDuplicates
    {
        static Random rng = new Random(DateTime.Now.Millisecond);
        static int size = 45;

        static void Main(string[] args)
        {
            int[] array = InitializeArrayWithNoDuplicates(size);
            DisplayArray(array);
            Console.ReadLine();
        }
        /// <summary>
        /// Creates an array with each element a unique integer
        /// between 1 and 45 inclusively.
        /// </summary>
        /// <param name="size"> length of the returned array < 45
        /// </param>
        /// <returns>an array of length "size" and each element is
        /// a unique integer between 1 and 45 inclusive </returns>
        public static int[] InitializeArrayWithNoDuplicates(int size)
        {
            int[] allNos = new int[size];
            bool[] used = new bool[size];

            for (int i = 0; i < size; i++)
            {
                allNos[i] = i + 1;
                used[i] = false;
            }

            int[] arr = new int[size];
            int max = size;

            for (int i = 0; i < size - 1; i++)
            {
                int number = rng.Next(0, max);
                int ptr = 0;
                for (int j = 0; j < size; j++)
                {
                    if (used[j])
                    {
                        ptr++;
                    }
                    else
                    {
                        if (j == number + ptr)
                        {
                            break;
                        }
                    }
                }
                arr[i] = allNos[number + ptr];
                used[number + ptr] = true;
                max--;
            }
            for (int i = 0; i < size; i++)
            {
                if (used[i] == false)
                {
                    arr[size - 1] = allNos[i];
                    break;
                }
            }

            return arr;
        }
        public static void DisplayArray(int[] arr)
        {
            for (int x = 0; x < size; x++)
            {
                Console.WriteLine(arr[x]);
            }
        }
    }
}

score 0 · Answer 4 · answered Aug 27 '17 at 06:55

0

Thankyou, i must have missed the briefing in summary. Too straight forward trying to generate the Array then realising after each integer its trying to generate an Array with a 1/45 chance. I should be able to just scramble the array at the end.

answered Aug 27 '17 at 06:55

PotatoFries

49
7

c# Array timeout error

4 Answers4