Search code examples
c#arrayssequences

How to make random sequences from array elements?


I made an array containing 24 elements. I want to iterate a loop 24 times, each time taking all the elements from the array and making a unique sequence.

For example:

for(int i=0; i<4 ; i++) 
 array = [a,b,c,d]

The output I want is:

iteration1: abcd
iteration2: acdb
iteration3: bacd
iteration4: dcab

The specific order is not important. What's important is the sequence for each iteration must be unique.

Can somebody recommend a way to this? Perhaps there is some function for randomisation in C#?


Solution

  • When you need individual sequences to be unique, it's no longer good enough for things to be truly random. True randomness would allow you to repeat sequences. What you need instead are called permutations.

    I don't have time right now to going into all the details, but Eric Lippert (formerly on the C# language team at Microsoft) has a series of blog posts with some great information on doing permutations in C#:

    https://ericlippert.com/2013/04/15/producing-permutations-part-one/

    Read through all the parts. It's part three before he gets to any code, but you need parts one and two to understand what he's doing.

    It's also worth noting here that the individual permutations are likely to come out somewhat ordered. To get what you really need, you'll likely need to generate all permutations, shuffle the set of permutation results, and then take the first 24 entries from the shuffled results.

    That sounds... expensive. This is why it's important to read and understand what's happening in the earlier articles. If you can understand how it works, you may be able to randomize your output to some degree as you go, and thus greatly increase the efficiency.

    That's also the formal computer-sciencey solution. Since the size of your problem set seems small, you may also be able to do a more practical solution. Clone the array 24 times (possibly to a 2D array) and then loop through the clones. For each loop iteration, you shuffle that clone, as well as check it against prior clones to make sure it's unique, repeating as necessary. For larger sets this will be slower; probably much slower. But at your size (24x24), this should be a win.