Randomising a list whilst ensuring duplicates are not sequential

Question

I am looking for an efficient mechanism of randomizing the order of a list with the caveat that duplicate items must have at least 9 items between them, if the length of the list allows, otherwise they must be as far apart as the length of the list will allow.

Firstly this is only for small data-sets there will never be more than 150 items in a list and there could be as few as 1.

So the basic premise is this:

1. Take a list of peoples names that may contain a few duplicates (typically there will never be more than 2 instances of any given name but there could be 3 in exceptional circumstances)
2. Randomize the list (I have this part working already using a Fisher-Yates (or Knuth shuffle))
3. If the list contains duplicates identify those that have less than 9 items between them and adjust if possible to make the gap at least 9 items.

Part 3 is the tricky bit, I have no guidelines on any business rules on how the system should ensure the spacing is correct just that it should be so where possible. At its simplest level an iterative loop that checks for violations and then moves a list element as appropriate would seem the way to go however I can imagine several scenarios where an adjustment made for one pairing then causes an issue with another and so on.

I am not looking for someone to write the code for this, I'm just really after some sensible ideas on a good, efficient way to approach this problem.

The source list will be a IList<string> in C# for reference.

Answer 1

Try code below. I group the strings together using Linq to get all the duplicates. I then create a random list of unique strings. Then add the remaining duplicates to the list spreading the string out evenly. The results is completely random and evenly spread.

Note : I found a minor error. Change line below

from : firstItem += spacing;​
to : firstItem += spacing + 1;​

While debugging the code I found firstItem was occasionally going negative so I added code to make sure firstItem was always positive. I then started thinking why I didn't get any overflows where firstItem was larger than the array size. That is when I realized I had to added 1 to spacing. The old code with an array A,B,C,D,E would give 1,1,1,1,1,A,B,C,D,E. New code will give 1,A,1,B,1,C,1,D,1,E.

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

namespace ConsoleApplication20
{
    class Program
    {
        static void Main(string[] args)
        {
            Random rand = new Random();
            List<string> input = new List<string>();
            List<string> output = new List<string>();
            //create 150 random strings with duplicates
            for(int i = 0; i < 150; i++)
            {
                input.Add(rand.Next(0,25).ToString());
            }
            //create dictionary with two columns key, number of entries
            Dictionary<string, Value> dict = input.AsEnumerable()
                .GroupBy(x => x)
                .ToDictionary(x => x.Key, y => new Value { count = y.Count(), ranNumber = rand.Next() });

            dict = dict.OrderBy(x => x.Value.ranNumber).ToDictionary(x => x.Key, y => y.Value);
            //add 1 sorted numbers to output
            foreach(string key in dict.Keys)
            {
                output.Add(key);
            }
            //add rest of numbers
            foreach (string key in dict.Keys)
            {
                int numberOfItems = dict[key].count;
                if (dict[key].count > 1)
                {
                    int arraySize = output.Count;
                    int spacing = arraySize / numberOfItems;
                    int firstItem = 0;
                    //center around middle
                    if (numberOfItems % 2 == 0)
                    {
                        firstItem = (arraySize / 2) - (((numberOfItems / 2) * spacing) + (spacing / 2));
                    }
                    else
                    {
                        firstItem = (arraySize / 2) - (((numberOfItems - 1) / 2) * spacing);
                    }
                    if (firstItem < 0)
                    {
                        firstItem = 0;
                    }
                    //remove existing item
                    output.Remove(key);
                    //insert items
                    for (int i = 0; i < numberOfItems; i++)
                    {
                        output.Insert(firstItem,key);
                        firstItem += spacing;
                    }
                }
            }

            
        }
        public class Value
        {
            public int count { get; set; }
            public int ranNumber { get; set; }
        }

    }
}

Answer 2

Try this:

Pass #0 Shuffle all names

Pass #1: find out which names exist more than once.

Pass #2: for each multiple-name find its closest pairing, exchange this name with a name which is 9 positions away if it is not a name known as a multiple-name. Exchange with name 10 positions away in such a case (repeat and increase distance)

Of course you need to pay attention if a name is close to start or end of the list and handle this adequately.

Answer 3

Here's how I'd probably do it:

1. Remove all duplicates leaving one copy of each item, but keep track of how many of each you remove.
2. Randomize list of unique entries
3. For each duplicate removed in step 1:
   1. Locate duplicated item(s) in list.
   2. Split list into parts at each position ± 9, ignoring zero or negative length partitions.
   3. Determine which partition that doesn't contain a duplicate is largest.
   4. Insert duplicate at random position in that partition.