Get random values from an Array

Question

I'm trying to change the elements of an array randomly, by changing the indexes. Thats ok. Now the problem is that as the random is always random, I can get two results that are the same.

for example:

Monday:

song 1

song 2

song 3

Tuesday:

song 2

song 1

song 3

Wednesday:

song 1

song 2

song 3

And so on...

And the list from

Monday

and

Wednesday

in this case is the same. I need to control that, but as you can see on the code, once I get the list from one day, I just print it. I thought about putting it on an array or Tuples and check if that tuple exists, but I think its too complicated. I thought that maybe I can make my own random function. But still, I'm not sure about that solution either. Any ideas of how can I solve this situation? Thanks!

Here is the code I have so far:

    static string[] songs = new string[] { "song1", "song2", "song3" };
    static string[] days = new string[] { "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday" };
    private static Random random = new Random();

/* Random number between lower and higher, inclusive */
    public static int rand(int lower, int higher)
    {
        int r = lower + (int)(random.Next(0, 2) * (higher - lower));

        return r;
    }

    /* pick M elements from original array. Clone original array so that
   7 * we don’t destroy the input. */
    public static string[] pickMRandomly()
    {
        string[] subset = new string[songs.Length];
        string[] array = (string[])songs.Clone();
        for (int j = 0; j < songs.Length; j++)
        {
            int index = rand(j, array.Length - 1);
            subset[j] = array[index];
            array[index] = array[j]; // array[j] is now “dead”
        }
        return subset;
    }

    public static void playListCreation()
    {
        for (int j = 0; j < days.Length; j++)
        {
            var result =pickMRandomly();
            System.Console.WriteLine(days[j]);
            foreach (var i in result)
            {
                System.Console.WriteLine(i + " ");
            }
            System.Console.WriteLine("/n");
        }
    }
}

I'm slighlty confused about the issue. Is it that duplicates are being generated? If you're testing with 3 songs, there are only 6 different permutations and 7 days of the week so you're going to get a duplicate. The more songs you test with, the less likely you're going to get duplicates. Regardless, are you asking how you can compare two arrays to see if they're identical? — keyboardP, Jun 19 '16 at 10:55
I don't understand the question. For any length list of songs, there is a finite number N of possible orderings of that list. As the previous comment points out, after N days, you are _guaranteed_ to repeat an order. For a list of significant length, N is large, the possibility of randomly repeating the sequence is small, and trying to avoid repeating the sequence before N days will require storing all of the previous permutations, which could be a lot of data. Is this really what you want to do? — Peter Duniho, Jun 19 '16 at 17:58
One way or the other, you can certainly improve on the code you have now: there's no need to create _two_ different arrays; just copy the original and [shuffle it](http://stackoverflow.com/a/110570). Also, since you want a non-destructive shuffle anyway, instead of shuffling the strings references themselves, shuffle an array of indexes, initialized in order (i.e. `{ 0, 1, 2, ... }`). Shuffling an array of indexes will also minimize the size of the data you need to store in order to remember the last (up to) N shuffles so you can avoid repeating the order. — Peter Duniho, Jun 19 '16 at 17:58
Do you know that your `public static int rand(int lower, int higher)` method returns either `lower` or `higher`? It does not return `/* Random number between lower and higher, inclusive */`. — Enigmativity, Jun 20 '16 at 03:22

score 2 · Accepted Answer · answered Jun 19 '16 at 11:19

If I understand you correctly, you don't just want a random arrangement of songs for each day, you want a unique (and random) arrangement of songs each day.

The only way that I can think of to guarantee this is to work out all of the possible combinations of songs and to randomly sort them - then to pick out a different combination from the list for each day.

using System;
using System.Collections.Generic;
using System.Linq;

namespace StackOverflowAnswer
{
    class Program
    {
        static string[] songs = new string[] { "song1", "song2", "song3" };
        static string[] days = new string[] { "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday" };

        static void Main(string[] args)
        {
            var rnd = new Random();
            var allCombinationsInRandomOrder = GetCombinations(songs, songs.Length)
                .Select(combination => new { Combination = combination, Order = rnd.Next() })
                .OrderBy(entry => entry.Order)
                .Select(entry => entry.Combination);

            var dayIndex = 0;
            foreach (var combination in allCombinationsInRandomOrder)
            {
                var day = days[dayIndex];
                Console.WriteLine(day);
                Console.WriteLine(string.Join(", ", combination));

                dayIndex++;
                if (dayIndex >= days.Length)
                    break;
            }
            Console.ReadLine();
        }

        private static IEnumerable<IEnumerable<string>> GetCombinations(IEnumerable<string> songs, int numberOfSongsInGeneratedLists)
        {
            if (songs == null)
                throw new ArgumentNullException(nameof(songs));
            if (numberOfSongsInGeneratedLists <= 0)
                throw new ArgumentOutOfRangeException(nameof(numberOfSongsInGeneratedLists));
            if (numberOfSongsInGeneratedLists > songs.Count())
                throw new ArgumentOutOfRangeException("can't ask for more songs in the returned combinations that are provided", nameof(numberOfSongsInGeneratedLists));

            if (numberOfSongsInGeneratedLists == 1)
            {
                foreach (var song in songs)
                    yield return new[] { song };
                yield break;
            }

            foreach (var combinationWithOneSongTooFew in GetCombinations(songs, numberOfSongsInGeneratedLists - 1))
            {
                foreach (var song in songs.Where(song => !combinationWithOneSongTooFew.Contains(song)))
                    yield return combinationWithOneSongTooFew.Concat(new[] { song });
            }
        }
    }
}

Thank you for the answer! I have one question. Why in this foreach `foreach (var combinationWithOneSong in GetCombinations(songs, numberOfSongsInGeneratedLists - 1))` I need to call the function recursevly ? Why can't I just iterate over `songs` array? Thanks!! — SomeAnonymousPerson, Jun 22 '16 at 06:57
The problem with simple looping is that I couldn't think of a good way to do it without knowing when writing the code how long the song lists should be. If I only wanted two songs in each play list then I would loop through the songs array and then loop through it again in a nested loop. If I wanted three songs then I would have a third nested loop and if I wanted four then I'd need a fourth nested loop. Doing each level one at a time using a recursive function seemed easiest to me because I could easily call "n" levels deep. — Dan Roberts, Jun 22 '16 at 07:03

score 1 · Answer 2 · edited May 23 '17 at 12:16

From what I understand, you want to create a random playlist and if this playlist has been created before, you want to generate another (until it's unique). One way you could do this is to add a hash of some sort to a HashSet and see if it's previously been generated. For example,

bool HashSet<int> playlistHashes = new HashSet<int>();
private bool CheckIfUnique(string[] playlist)
{
    //HashSet returns false if the hash already exists 
    //(i.e. playlist already likely to have been created)
    return playlistHashes.Add(string.Join("",playlist).GetHashCode());
}

Then once you've generated your playlist, you can call that method and see if it returns false. If it returns false, that playlist order has been created before and so you can generate again. Using the technique above means that song1, song2, song3 is different from song3, song2, song1 so the order is important.

As mentioned in my comment on the question, if you're testing with 3 songs, there are only 6 different permutations and 7 days of the week so you're going to get a duplicate.

Side note, GetHashCode can throw 'false-positives' but it's up to you to determine how likely it is, and if the impact is actually of any significance since a new playlist is generated anyway. Good thread for more information here. There are numerous hashing techniques possible with lower collision chances if GetHashCode would not suffice here.

Why was this downvoted, the question isn't fully clear but seems to be what OP was asking for? — TryNCode, Jun 20 '16 at 12:40

sujith karivelil · Answer 3 · 2016-06-20T03:25:13.977

Consider that you have 3 Songs in hand and want to assign unique Combination for each day of a week( 7days). It is not possible since you can made only six unique combinations with these three. So definitely there may be one repeating sequence. You will get 24 unique song sequence if you add another song(let it be "song4") to this collection. I have included a snippet that help you to get these combination of unique sequence of songs.

string[] songs = new string[] { "song1", "song2", "song3", "song4" };       
int numberOfSongs = songs.Count();
var collection = songs.Select(x => x.ToString()); ;
for (int i = 1; i < numberOfSongs; i++)
{
    collection = collection.SelectMany(x => songs, (x, y) => x + "," + y);                            
}
List<string> SongCollections = new List<string>();
SongCollections.AddRange(collection.Where(x => x.Split(',')
                                   .Distinct()
                                   .Count() == numberOfSongs)
                                   .ToList());

Now the SongCollections will contains 24 unique sequence of 4 songs. (if you choose 3 songs then you will get 6 unique sequences). You can apply Random selection of sequence from these collection and assign to days as you wish.

Now Let me use a Dictionary<string, int> dayCollectionMap to map a collection to a day(Note : Here i use a collection of 4 songs since 3 is not enough for 7 days). Consider the snippet below:

Dictionary<string, int> dayCollectionMap = new Dictionary<string, int>();
string[] days = new string[] { "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday" };
Random randomCollection = new Random();
foreach (string day in days)
{
    int currentRandom = randomCollection.Next(0, SongCollections.Count());
    if (!dayCollectionMap.Any(x => x.Value == currentRandom))
    {
        dayCollectionMap.Add(day, currentRandom);
    }
    else
    {
        // The collection is already taken/ Add another random sequence
        while (true)
        {
            currentRandom = randomCollection.Next(0, SongCollections.Count());
            if (!dayCollectionMap.Any(x => x.Value == currentRandom))
            {
                dayCollectionMap.Add(day, currentRandom);
                break;
            }

        }
    }

}

So that you can select the song collection for Wednesday by using the code

  var songCollectionForWed = SongCollections[dayCollectionMap["Wednesday"]];

@down-voter : Let me know reason please, if it is reasonable then it will help me to improve the answer — sujith karivelil, Jun 20 '16 at 03:58
Someone downvoted the other answer too but can't see why. +1 to balance it out until a valid reason is given — TryNCode, Jun 20 '16 at 15:53

Get random values from an Array

3 Answers3