List with no sequential repeats (where possible)

Question

Assume I have the following list (List<string>)

G
G
M
T

I'd like this to be in an order where the same letter will not occur twice, such as

G
M
G
T

(I appreciate other variations would also suffice)

Please note, if I had the following

G
G
G
G
G
M
T

Then of course some values will have to occur concurrently. The position within the List where this concurrency occurs is not relevant. What I'm after is to stop this repetition where possible to most evenly spread the letters.

The C# console application code I share works

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

namespace resorting
{
    class Program
    {
        static void Main(string[] args)
        {
            List<string> list = new List<string> { "G", "G", "G", "G", "M", "M", "T", "T", "T", "T", "T", "T", "T", "T", "G", "G", "G", "G", "M", "M", "T", "T", "T", "T", "T", "T", "T", "T" };

            list.UpdateList();
        }      
    }

    public static class extension
    {
        public static void UpdateList(this List<string> list)
        {
            GetList(list);
            list.Reverse(); // DO I HAVE TO REVERSE
            GetList(list);  // AND THEN CALL THE METHOD AGAIN
        }

        private static void GetList(List<string> list)
        {
            int total = list.Count;

            int inc = 2;

            for (int i = 0; i < total; i++)
            {
                if (total <= i + 2)
                    break;

                if (total <= i + inc)
                    continue;

                if (list[i] == list[i + 1])
                {
                    var val = list[i];
                    list.RemoveAt(i);
                    list.Insert(i + inc, val);
                    i = i - 1;
                    inc++;
                    continue;
                }
                inc = 2;
            }
        }
    }
}

As you can see, I have to call this function twice. I reverse the order and then reapply the same logic. Whilst it works, and based upon the amount of data I will be using, I don't need the function to be more efficient my question is still about efficiency (if worth while against the amount of work required).

Can I update the code to not need to reverse the list to avoid calling the code twice?

Answer 1

Here's an alternate way to do it. It doesn't involve modifying and reversing the existing list. Instead, it first groups and counts the items, then yields the one that wasn't printed last time and still needs to be yielded the most times. I'm not sure about actual runtime for large lists, but as long as the number of distinct items in the list is small, the reorderings and searches should run very fast.

public static IEnumerable<T> WithoutDupes<T>(this IEnumerable<T> source) where T : IEquatable<T>
{
    var sourceGroups = source.GroupBy(x => x).Select(x => new GroupCount<T>(x)).ToList();
    T last = default(T);
    bool hasLast = false;
    while (sourceGroups.Count > 0)
    {
        sourceGroups = sourceGroups.OrderByDescending(x => x.Count - x.CountOutputted).ToList();
        var group = (hasLast ? sourceGroups.FirstOrDefault(x => !last.Equals(x.Value)) : null) ?? sourceGroups[0];

        yield return group.Value;
        group.CountOutputted++;
        if (group.CountOutputted == group.Count)
        {
            sourceGroups.Remove(group);
        }
        last = group.Value;
        hasLast = true;
    }
}
private class GroupCount<T>
{
    public T Value { get; private set; }
    public int Count { get; private set; }
    public int CountOutputted { get; set; }
    public GroupCount(IGrouping<T, T> grouping)
    {
        this.Value = grouping.Key;
        this.Count = grouping.Count();
    }
}

As example output, with your input, it produces this list (note how it handles the impossible case: puts the extra T's at the end)

T, G, T, G, T, G, T, G, T, G, T, M, T, M, T, G, T, G, T, M, T, M, T, G, T, T, T, T

Answer 2

@Tim gave a great solution of his own, so I won't talk about your algorithm, but about your code:

Naming Conventions
Class and namespace names in C# should be in PascalCase:

namespace Resorting
{
    public static class Extension
    {
        ....
    }
}

Meaningful Names
A class named Extension does not tell me anything about what it does. This goes twice for a method called UpdateList, and GetList is simply misleading. Give the method a name which actually explains what it does:

public static class ReorderListExtension
{
    public static void ReorderForNoSequentialRepeats(this List<string> list)
    {
    }

    private static void ReorderForNoSequentialRepeatsIteration(this List<string> list)
    {
    }
}

It might be longer, but it is meaningful...

Don't break the flow
Your use of the continue keyword inside the last if block is easy to miss, and may confuse a code reader.
When all the if block does it break;, continue; or return; using these keywords is fine (this is called guard conditions).
But if the block contains a lot of code before changing the flow, the keyword is easily missed.

Simply put the last line in

if (list[i] == list[i + 1])
{
    var val = list[i];
    list.RemoveAt(i);
    list.Insert(i + inc, val);
    i = i - 1;
    inc++;
} else
{
    inc = 2;
}

Why not generalize?
Your new API accepts List<string>, but it actually never uses the fact that the values are strings.
Why not simply accept List<T>? It costs you nothing, and extends your code considerably...
I would even take it a step further, and change the signature to accept IList<T>.

Answer 3

Another approach:

public static List<T> Reorder<T>(List<T> input)
{
    var workingList = new List<T>(input);
    var output = new List<T>();

    while(workingList.Count() != 0)
    {
        var skipped = new List<T>();
        bool anyAdded = false;

        foreach(T item in workingList)
        {
            if(item.Equals(output.LastOrDefault()))
            {
                skipped.Add(item);
                continue;
            }
            output.Add(item);
            anyAdded = true;
        }
        if(!anyAdded)
        {
            output.AddRange(workingList);
            break;
        }
        workingList = skipped;
    }
    return output;
}

Then for, e.g., input: "A", "A", "B", "B", "B", "A", "A", "C", "C", "B", "A" you get output: "A","B","A","C","B","A","B","A","C","A","B"

Answer 4

I turned this problem to an unsorting problem and I had so much pleasure doing so. To make that obviously you have to sort the list first. We all know that sorting takes it's time but I tried to reduce the complexity of the algorithm. If it was guaranteed that the collection was already sorted then we could discard the sorting time and thus this solution would be a clever solution (maybe). My solution assumes that there are at least three distinct values however it could be adapted to consider two or one (with probably a decreasing degree of complexity).

//find first and last index of elem
public static Tuple<int, int> BinarySearch<T>(List<T> list, T elem)where T:IComparable{
    return BinarySearch(list, elem, 0, list.Count-1);
}

public static Tuple<int, int> BinarySearch<T>(List<T> list, T elem, int left, int right)where T:IComparable{
    int idxFirst = -1;
    int auxRight = right;
    int auxLeft = -1;
    while(left <= right){
        int mid = left + (right - left) / 2;
        if(list[mid].CompareTo(elem) > 0){
            right = mid - 1;
        }else if(list[mid].CompareTo(elem) < 0){
            left = mid + 1;
        }else{
            if(list[right].CompareTo(elem) > 0){
                auxRight =  right+1;
            }
            right = mid - 1;
            idxFirst = mid;
            auxLeft = auxLeft < 0 ? mid : auxLeft;
        }
    }
    int idxLast = BinarySearchLast(list, elem, auxLeft, auxRight);
    return Tuple.Create(idxFirst, idxLast);
}

private static int BinarySearchLast<T>(List<T> list, T elem, int left, int right)where T:IComparable{
    int idxLast = - 1;
    while(left <= right){
        int mid = left + (right - left) / 2;
        if(list[mid].CompareTo(elem) > 0){
            right = mid - 1;
        }else if(list[mid].CompareTo(elem) < 0){
            left = mid + 1;
        }else{
            left = mid + 1;
            idxLast = mid;
        }
    }
    return idxLast;
}
//get's the 3 maximum elements
private static K[] ThreeMax<K, V>(Dictionary<K, V> map)where V:IComparable{
    K[] keys = new K[3];
    Dictionary<K, V> aux = new Dictionary<K, V>(map);
    for(int i = 0; i < keys.Length; ++i){
        KeyValuePair<K, V> pair = aux.First();
        foreach(var entry in aux){
            if(entry.Value.CompareTo(pair.Value) > 0){
                pair = entry;
            }
        }
        keys[i] = pair.Key;
        aux.Remove(pair.Key);
    }
    return keys;
}

public static IEnumerable<T> InterLeaveValues<T>(List<T> list)where T:IComparable{
    List<T> aux = new List<T>(list);
    aux.Sort(); //O(n) (I think it performs a quicksort)
    int idx = 0;
    //get all different values and put them on map O(number of different elements * lg n)
    Dictionary<T, int> map = new Dictionary<T, int>();
    while(idx < aux.Count){
        T elem = aux[idx];
        Tuple<int, int> range = BinarySearch(aux, elem, idx, aux.Count-1);
        //add to set the value and number of occurrences of the value
        map.Add(elem, range.Item2 - range.Item1 + 1);
        idx = range.Item2 + 1;
    }
    int idxMax = 0;
    int[] maxs;
    T[] keysMax;
    do{
         //find the 3 elements that occurr most time O(number of different elements)
        keysMax = ThreeMax(map);
        maxs = new int[keysMax.Length];
        for(int i = 0; i < keysMax.Length; ++i){
            maxs[i] = map[keysMax[i]];
        }
        int times = maxs[idxMax +1] - maxs[idxMax+2] + 1;
        //return the two elements with most occurrences interleaved
        for(int i = 0; i < times; ++i){
            yield return keysMax[0];
            yield return keysMax[1];
        }
        map[keysMax[0]] -= times;
        map[keysMax[1]] -= times;
    }while(maxs[1] > 0);
    for(int i = 0; i < maxs[0] ; ++i){
        yield return keysMax[0];
    }
}

EDIT Here lies all my remaining madness. I removed the ThreeMax method. I think this is the best as it can get maybe, I'm going to measure it againinst Tim S. solution.

public class DelegatedComparer<T> : IComparer<T>
{
   private readonly Func<T, T, int> compare;
   public DelegatedComparer(Func<T, T, int> compare)
   {
       this.compare = compare;
   } 

   public int Compare(T x, T y)
   {
        return compare(x, y);
   }
}

public class ItemAndCount<T>{
    public T Item{get;set;}
    public int Count{get;set;}
}

private static IEnumerable<T> InterleaveValues<T>(List<ItemAndCount<T>> distinctList)
{
  //yield all elements until distinctList[1] .. distinctList[n] is same
  for (int nElems = 2; nElems < distinctList.Count; ++nElems)
  {
      int nextCount = distinctList[nElems].Count;
      int times = distinctList[nElems - 1].Count - nextCount;
      for (int i = 0; i < nElems; ++i)
      {
          distinctList[i].Count -= times;
      }
      while (times > 0)
      {
          for (int i = 0; i < nElems; ++i)
          {
              yield return distinctList[i].Item;
          }
          --times;
      }
  }


  if (distinctList.Count >= 2)
  {
      int idxCurr = 1;
      int countFirst = distinctList[0].Count;
      int times = 0;
      while (countFirst >= distinctList[idxCurr].Count)
      {

          //yield first interleaved with the current Element, so first occurrs more times
          yield return distinctList[0].Item;
          yield return distinctList[idxCurr].Item;
          --countFirst;
          distinctList[idxCurr].Count -= 1;
          idxCurr = (idxCurr + 1) == distinctList.Count ? 1 : (idxCurr + 1);
          ++times;
      }
      distinctList[0].Count -= times;
      for (; idxCurr < distinctList.Count; ++idxCurr)
      {
          yield return distinctList[idxCurr].Item;
      }
      distinctList[distinctList.Count - 1].Count -= 1;
  }

  //here the list has only one element or all elements have the same amount of ocurrences
  int count = distinctList[distinctList.Count - 1].Count;
  distinctList[0].Count -= count;
  while (count > 0)
  {
      for (int i = 0; i < distinctList.Count; ++i)
      {
          distinctList[i].Count -= 1;
          yield return distinctList[i].Item;
      }
      --count;
  }

  for (int i = distinctList[0].Count; i > 0; --i)
  {
      yield return distinctList[i].Item;
  }
}


public static IEnumerable<T> InterleaveValues<T>(List<T> list)where T:IComparable{
    List<T> aux = new List<T>(list);
    aux.Sort(); //O(n) (I think it performs a quicksort)
    int idx = 0;
    //get all different values and put them on a sorted set set O(number of different elements * lg n)
    ICollection<ItemAndCount<T>> distinct = new SortedSet<ItemAndCount<T>>(new DelegatedComparer<ItemAndCount<T>>(
        //put those who occurr most in the beggining
        (t1, t2) => t2.Count - t1.Count
    ));
    while(idx < aux.Count){
        T elem = aux[idx];
        Tuple<int, int> range = BinarySearch(aux, elem, idx, aux.Count-1);
        //add the value and number of occurrences of the value
        distinct.Add(new ItemAndCount<T>(){Item = elem, Count = range.Item2 - range.Item1 + 1});
        idx = range.Item2 + 1;
    }
    return InterleaveValues(distinct.ToList());
}