Reputation: 311

Sort List C# in arbitrary order

I have a C# List I.E. List<Food> x = new List<Food> () ;

This list is populated with this class

public class Food {
           public string id { get; set; }
           public string idUser { get; set; }               
           public string idType { get; set; } 
          //idType could be Fruit , Meat , Vegetable , Candy 
           public string location { get; set; }    
}

Now i have this unsorted List<Food> list ; which has I.E. 15 elements. There are 8 Vegetable Types , 3 Fruit Types , 1 Meat Types , 1 Candy Types

I would sort this so that to have a list ordered in this way :

1° : Food.idType Fruit 
2° : Food.idType Vegetables 
3° : Food.idType Meat
4° : Food.idType Candy
5° : Food.idType Fruit
6° : Food.idType Vegetables
7° : Food.idType Fruit //Becouse there isnt more Meat so i insert the 
                       //next one which is Candy but also this type is empty 
                       //so i start from begin : Fruit
8° : Food.idType Vegetables
9° : Food.idType Vegetables // For the same reason of 7°
10 ° Food.idType Vegetables
......
....
....
15 : Food.idType Vegetables

I cant find a rule to do this. Is there a linq or List.Sort instruction which help me to order the list in this way?

Update i changed the return value of idType and now return int type instead string so 1=Vegetable , 2=Fruit , 3=Candy 4=Meat

Upvotes: 1

Answers (6)

Binary Worrier

Reputation: 51719

A standard sort method isn't going to cut this for you.
You need something like a custom Round Robin sort methd. e.g. This is kind of like a bubble sort.

public enum FoodType
{
    Fruit,
    Veg,
    Meat,
    Candy
}

public class Food
{
    public FoodType Type;
    public string Name { get; set; }
}


void RoundRobinSort(List<Food> foods)
{
    var typeValues = (FoodType[])Enum.GetValues(typeof(FoodType));
    int nextType = 0;
    for (int i = 0; i < foods.Count - 1; i++)
    {
        if (foods[i].Type != typeValues[nextType])
        {
            int itemToSwap = -1;
            int loopGuard = 0;
            while (itemToSwap == -1 && loopGuard <= typeValues.Length)
            {
                itemToSwap = foods.FindIndex(i, f => f.Type == typeValues[nextType]);
                if(itemToSwap == -1)
                    nextType = (nextType + 1) % typeValues.Length;
                loopGuard++;
            }
            if (itemToSwap == -1)
                throw new Exception("Should never happen, Put a meaningful message here");

            if (itemToSwap != i)
            {
                var temp = foods[itemToSwap];
                foods[itemToSwap] = foods[i];
                foods[i] = temp;
            }
        }
        nextType = (nextType + 1) % typeValues.Length;
    }
}

Upvotes: 3

Gabe

Reputation: 86818

Your algorithm does not lend itself to a Sort or OrderBy function because there's no way to tell from looking at two individual elements which one will go first.

What you need to do is take your unordered List and perform a GroupBy on the idType field. This will give you a set of fruits, a set of vegetables, and so on. Then sort the groups by their key (idType). Finally, you need to interleave the elements of each group, leaving out a group once it's run out of items.

Here's an example that assumes idType is in the order that you want your outputs selected:

    public static IEnumerable<Food> InterleaveFoods(IEnumerable<Food> source)
    {
        var groups = (from food in source
                      group food by food.idType into foodGroup
                      orderby foodGroup.Key
                      select foodGroup.ToArray())
                     .ToList();

        int i = 0;
        while (groups.Any())
        {
            for (int group = 0; group < groups.Count; group++)
            {
                if (i < groups[group].Length)
                    yield return groups[group][i];
                else
                {
                    // group is empty; remove it
                    groups.RemoveAt(group);
                    group--;
                }
            }
            i++;
        }
    }

Upvotes: 3

Tony Hopkinson

Reputation: 20330

Guessing here but if you wanted to model Four bags. One of each type. and then choose one from each in order, until all the bags were empty then.

Make food type an enum so it's in the right order.

dump your List into SortedList> something like

SortedList<enumFoodType,List<Food>> sortedFood = new     SortedList<enumFoodType,List<Food>>
foreach(Food f in x)
{
  if (sortedFood.ContainsKey(f.foodType))
  {
    sortedFood[f.foodType].Add(f);
  }
else
{
  sortedfood.Add(f.foodType,f);
}

will do that.

then

List<Food> chosenX  = new List<Food>();
while (sortedFood.Count > 0)
{
  foreach(enumFoodType ft in sortedFood.Keys)
  {
    if (sortedKeys[ft].Count > 0)
    {
      chosenX.Add(sortedKeys[ft][0];
      sortedKeys[ft].RemoveAt(0);
    }  
}

not checked but it's sort of right, could be neater and faster, but you can look at that when it does what you want.

Almost like a weird bin packing algorithm this one. Each bin will contain one of each things that's left in this order.

Upvotes: 0

David Burhans

Reputation: 363

I think you'll want to implement your own IEnumerable object for this. I would start with a list for each food type, or better yet, a dictionary that stores a list for each food type. You will need to handle your own enumeration. This means keeping track of your current position in each list and what the last food type requested was. Then you simply find that list in the dictionary, and get the next value out if it and update the lastRequestedFoodType. Just make sure you are returning your own IEnumerator instead of one that belongs to one of the lists in the dictionary. This basically lets you cycle through all of your lists in the dictionary. If you are out of items in one list, just skip it and move on to the next one. When you reach the end of all of the lists, you are done.

Adding items in this fashion should be pretty straight forward, but inserting them or changing order will be hard.

Since you aren't really sorting, you are arranging, there is nothing really built in to do this.

Upvotes: 0