«Умная» группировка с LINQ

Question

У меня есть список строк, и я хочу преобразовать его в какой-то сгруппированный список, в результате чего значения будут сгруппированы по их расположению в списке (не обычная группировка, но таким образом, что одни и те же элементы находятся в группа, только если они вместе). Рассмотрим следующий пример:

LinkedList<string> myList = new LinkedList<string>();
myList.AddLast("aaa");
myList.AddLast("aaa");
myList.AddLast("bbb");
myList.AddLast("bbb");
myList.AddLast("aaa");
myList.AddLast("aaa");
myList.AddLast("aaa");

LinkedList<MyTuple> groupedList = new LinkedList<MyTuple>();
groupedList.AddLast(new MyTuple("aaa", 2));
groupedList.AddLast(new MyTuple("bbb", 2));
groupedList.AddLast(new MyTuple("aaa", 3));

Может ли это преобразование быть выполнено с помощью LINQ или я должен написать алгоритм обычным образом с циклами?

Answer 1

Метод расширения из этого ответа в значительной степени выполняет то, что вы просите (Microsoft также предоставляет реализацию для группировки смежных элементов в последовательности ):

public static IEnumerable<IGrouping<int, T>> 
    GroupConsecutive<T>(this IEnumerable<T> set, Func<T, T, bool> predicate)
{
    var i = 0;
    var k = 0;
    var ranges = from e in set
                 let idx = ++i
                 let next = set.ElementAtOrDefault(idx)
                 let key = (predicate(e, next)) ? k : k++
                 group e by key into g
                 select g;
    return ranges;
}

Вы можете использовать его следующим образом:

void Main()
{
    LinkedList<string> myList = new LinkedList<string>();
    myList.AddLast("aaa");
    myList.AddLast("aaa");
    myList.AddLast("bbb");
    myList.AddLast("bbb");
    myList.AddLast("aaa");
    myList.AddLast("aaa");
    myList.AddLast("aaa");
    IGrouping<int,string> ggg;

    var groups=myList.GroupConsecutive((a,b)=>a==b);

    ILookup<string,int> lookup=groups.ToLookup(g=>g.First(),g=>g.Count());

    foreach(var x in lookup["aaa"])
    {
        Console.WriteLine(x); //outputs 2 then 3
    }
    foreach(var x in lookup["bbb"])
    {
        Console.WriteLine(x); //outputs 2
    }

}

Обратите внимание, что конечным контейнером является ILookup , который немного похож на словарь, но позволяет хранить несколько значений для одного ключа.

Answer 2

Это невозможно с помощью словаря.Словарь является ассоциативным (то есть: каждый ключ должен указывать только на один и только один) и по своей природе неупорядочен.Вам нужно будет использовать что-то еще для этой структуры данных.Это не было бы ужасно сложно, хотя!

Edit

A List<Tuple<string, int>> должно сделать трюк:

List<KeyValuePair<string, int>> structure = new List<KeyValuePair<string, int>>();
structure.Add(new KeyValuePair<string, int>(myList[0], 1);
for(int i = 0; i < myList.Count; i++ )
{
    if( myList[i] == structure[structure.Count-1].Key )
    {
        structure[structure.Count-1].Value += 1;
    }
    else
    {
        structure.Add(new KeyValuePair<string, int>(myList[i], 1);
    }
}

После этого вы должны(не проверено!) есть то, что вы ищете.

Редактировать (еще одна мысль)

Хотя это возможно с помощью linq (используя TakeWhile и count ..)Я все еще думаю, что здесь есть смысл использовать цикл, все просто.Кто-то более блестящий, чем я мог бы попытаться работать с Linq.