Моделирование процесса считалки с помощью LINQ

Question

Стоит задача смоделировать процесс считалки. Есть коллекция необходимо удалять элементы через одного до тех пор, пока в ней не останется один элемент. Нельзя просто удалять только четные/нечетные элементы. Т.к. после первого обхода всех элементов, на втором круге четные могут смениться нечетными и наоборот. На примере: если в коллекции 5 элементов и мы удалять начинаем с 1-ого, тогда удаляются: 1-ый, 3-ий. После 3-его мы пропускаем 4-ый и переходим опять на начало, удаляем уже 0-ой (а не 1-ый). И так далее, пока не останется один элемент в колекции.

Еще решение ограничено тем, что колекция передаётся в качестве ICollection, и изменить нужно именно входной параметр. Метод не возвращает параметров, void. Я реализовал решение, но хочу понять как решить эту задачу с помощью LINQ.

Моя реализация:

private static void RemoveEachSecondItem<T>(ICollection<T> collection)
    {
        int num = 1;
        while (collection.Count != 1)
        {
            foreach (var a in collection.ToArray())
            {
                if (num % 2 == 0)
                {
                    collection.Remove(a);
                }
                num++;
            }
            PrintHumans(collection);
        }
    }

И вот что у меня получилось с использованием LINQ:

private static void RemoveEachSecondItem<T>(ICollection<T> collection)
    {
        int num = 0;
        while (collection.Count != 1)
        {
            var a = collection.Where(p => ++num % 2 == 0);
            foreach (var i in a.ToArray())
                collection.Remove(i);
            PrintHumans(collection);
        }
    }

Собственно, как можно сделать лучше с использованием LINQ?

Answer 1

Просто оставлю это здесь.

Задача легко решается аналитически. Для этого нужно просто взглянуть на последовательность индексов элементов для разных длин коллекции.

for (int i = 1; i < 200; i++)
{
    var a = Enumerable.Range(0, i).ToList();
    RemoveEachSecondItem(a);
    Console.WriteLine(i + "=" + a[0]);
}

После чего получается некая формула арифметической последовательности, вычисление члена которой я представил в виде метода.

private static int GetLoserIndex(int count)
{
    int i = 1;
    while (i * 2 <= count)
        i *= 2;
    return (count - i) * 2;
}

Тогда основной метод сводится к такому коду

private static void RemoveEachSecondItem<T>(ICollection<T> collection)
{
    int index = GetLoserIndex(collection.Count);
    foreach (var a in collection.Where((x, i) => i != index).ToArray())
    {
        collection.Remove(a);
    }
}

Преимущество такого решения в том, что оно будет очень сильно быстрее любого другого на основе перебора.

Может это даже еще можно оптимизировать, но я просто хотел показать идею.

БЛОГ НА HUSL

Моделирование процесса считалки с помощью LINQ

Ответы (1 шт):