Int Array Reorder with Even Distribution in C#?

Question

12,13,14,15,16,19,19,19,19 

to

12,19,13,19,14,19,15,19,16

Hey all. Can anyone point me to clues/samples on how to distribute the first array of Int32 values, where a bunch of 19 values were appended, to the second where the 19 values are fairly evenly interspersed in the array?

I am not looking for a random shuffling, as in this example #19 could still appear consecutively if there was randomization. I want to make sure that #19 is placed in between the other numbers in a predictable pattern.

The use-case for this is something like teams taking turns presenting a topic: teams 12-16 each present once and then team #19 shows up but should not show their topic four times in a row, they should show their topic in between the other teams.

Later, if twelve values of 7 are added to the array, then they will also have to be evenly distributed into the sequence as well, the array would be 21 elements but the same rule that neither #19 or #7 should have consecutive showings.

I thought there might be something in Math.NET library that would do this, but I did not find anything. Using C# on .NET Framework 4.7.

Thanks.

Answer 1

Here's how to do this.

var existing = new[] { 12, 13, 14, 15, 16 };
var additional = new [] { 19, 19, 19, 19 };

var lookup =
    additional
        .Select((x, n) => new { x, n })
        .ToLookup(xn => xn.n * existing.Length / additional.Length, xn => xn.x);

var inserted =
    existing
        .SelectMany((x, n) => lookup[n].StartWith(x))
        .ToArray();

This gives me results like 12, 19, 13, 19, 14, 19, 15, 19, 16.

The only thing that this won't do is insert a value in the first position, but otherwise it does evenly distribute the values.

Answer 2

Details on the following method that evenly (mostly) distributes the duplicates in your list. Duplicates can be anywhere in your list, they will be distributed.

1. Create a dictionary of all numbers and keep track of the number of times they appear in the list
2. Use a new list without any duplicates. For Each number that has duplicates, spread it over the size of this new list. Each time the distribution is even.

    public static List<int> EvenlyDistribute(List<int> list)
    {
        List<int> original = list;

        Dictionary<int, int> dict = new Dictionary<int, int>();
        list.ForEach(x => dict[x] = dict.Keys.Contains(x) ? dict[x] + 1 : 1);

        list = list.Where(x => dict[x] == 1).ToList();

        foreach (int key in dict.Where(x => x.Value > 1).Select(x => x.Key))
        {
            int iterations = original.Where(x => x == key).Count();
            for (int i = 0; i < iterations; i++)
                list.Insert((int)Math.Ceiling((decimal)((list.Count + iterations) / iterations)) * i, key);
        }

        return list;
    }

Usage in main:

    List<int> test = new List<int>() {11,11,11,13,14,15,16,17,18,19,19,19,19};
    List<int> newList = EvenlyDistribute(test);

Output

19,11,13,19,14,11,19,15,16,19,11,17,18

Answer 3

In case random distribution is enough the following code is sufficient:

    static void MixArray<T>(T[] array)
    {
        Random random = new Random();

        int n = array.Length;
        while (n > 1)
        {
            n--;
            int k = random.Next(n + 1);
            T value = array[k];
            array[k] = array[n];
            array[n] = value;
        }
    }

For instance:

    int[] input = new int[]{12,13,14,15,16,19,19,19,19};
    MixArray<int>(input);

In case you require precise evenly distribution while retaining the order of the elements, to following code will do the job:

    public static T[] EvenlyDistribute<T>(T[] existing, T[] additional)
    {
        if (additional.Length == 0)
            return existing;

        if (additional.Length > existing.Length) 
        {
            //switch arrays
            T[] temp = additional;
            additional = existing;
            existing = temp;
        }

        T[] result = new T[existing.Length + additional.Length];
        List<int> distribution = new List<int>(additional.Length);
        double ratio = (double)(result.Length-1) / (additional.Length);
        double correction = -1;

        if (additional.Length == 1)
        {
            ratio = (double)result.Length / 2;
            correction = 0;
        }

        double sum = 0;
        for (int i = 0; i < additional.Length; i++)
        {
            sum += ratio;

            distribution.Add(Math.Max(0, (int)(sum+correction)));
        }

        int existing_added = 0;
        int additional_added = 0;
        for (int i = 0; i < result.Length; i++)
        {
            if (additional_added == additional.Length)
                result[i] = existing[existing_added++];
            else
            if (existing_added == existing.Length)
                result[i] = additional[additional_added++];
            else
            {
                if (distribution[additional_added] <= i)
                    result[i] = additional[additional_added++];
                else
                    result[i] = existing[existing_added++];
            }
        }

        return result;
    }

For instance:

    int[] existing = new int[] { 12, 13, 14, 15, 16};
    int[] additional = new int[] { 101, 102, 103, 104};

    int[] result = EvenlyDistribute<int>(existing, additional);
    //result = 12, 101, 13, 102, 14, 103, 15, 104, 16