c# element sort

Question

I have a problem trying to sort a Dictionary<int,Elem>/SortedList<int,Elem> of elements.

I have a list of N elements that should appear X times on the list, but if an element is on i index then it cannot reappear on i - 1 or i + 1. I also must respect list limits (elem N is before elem 1 and elem 1 is next to elem N).

I have two possible starting points:

1. A list of elements which have a Times property, which has the number of times the element should appear on the resulting list.

   Example Input:

   List<elem> elements = new List<elem>(){new Elem("star", 3), new Elem("square", 2), new Elem("circle", 3)}; 
   //Elem construct take element name, and number of times on result list
   

2. A list, containing all the elements I want to sort, obviously, in an unssorted fashion.

   List<elem> elements = new List<elem>(){new Elem("star"),new Elem("star"),new Elem("star"),new Elem("circle"),("circle"),("circle"),new Elem("sqare"),new Elem("sqare")}; 
   

Expected output:

star circle star sqare circle sqare star circle

// or any other combination in which any element is not preceded by itself

Better performance sort algorithms are welcome but not a must here, since this will be done infrequently.

I'm using C# 4.0 and .Net Framework 4.0.

Answer 1

I dont have time to test this as i do not have access to visual studio at the moment, but ill get you started.

First, id recommend taking all the objects and sorting them into three different lists. (this is going by the fact you would be using a List, edit as nessisary,

List<string> circle = new List<string>();
List<string> square = new List<string>();
List<string> star = new List<string>();
foreach(string item in yourList)
{
    switch(item)
    {
        case "circle":
            circle.Add(item);
            break;
        case "star":
            star.Add(item);
            break;
        case "square":
            square.Add(item);
            break;
    }
}
//then you would move to sorting them into one list, which would be
List<string> finnished = new List<string>();
int count = 0;
while(count != square.Count -1)
{
    finished.Add(square[count]);
    finished.Add(star[count]);
    finished.Add(circle[count]);
    count++
}

Answer 2

You can do this using a very simple backtracking algorithm (akin to the standard solution to the eight queens puzzle. Let me know if you need details.

Answer 3

Implement a custom key class for SortedList. e.g.

class MyKey : IComparer
{
    int count;
    int index; // Or maybe something else
    ...
}

Adding to your SortedList would involve incrementing the count variable in that values custom key if it exists. Or adding a new key with a count of 1 if it does not.