Удаление элементов по кругу

#c_sharp #net

Есть задача: по кругу стоят от 1 до N человек. Идя по кругу надо вычеркивать каждого
второго, пока не останется один и, соответственно, вывести его в консоль. Программа
должна работать с классами List и LinkedList (обращаться напрямую по индексу к элементу
нельзя).

Метод для удаления должен быть общий для List и LinkedList.
В метод я передаю IEnumerable ie, но у него нет метода Remove.
Пытался создать объект ICollection - кидает ошибку.  

Как грамотно реализовать метод, чтобы работал и для List, и для LinkedList?   

public static void RemoveEachSecondItem(IEnumerable ie)
    {
        ICollection ic = new ICollection(ie);
        while (ie.Count() > 1)
        {
            bool isOdd = false;//четный элемент
            foreach (var item in ic)
            {
                if (isOdd)
                {
                    ic.Remove(item);
                }

            }
        }
    }

    

Ответы

Ответ 1

"Честный" вариант решения

Алгоритм, по идее, прост:


Cтроим кольцевой односвязный список (как упомянуто в комментарии @A K) по исходному
перечислению (IEnumerable) элементов
Пока элементов в построенном списке больше одного, идём по нему и удаляем каждый
четный элемент
Возвращаем единственный оставшийся в списке элемент


Реализация может получиться сложнее или проще... Пример:

Узел списка:

private class MyNode
{
    public readonly T item;
    public MyNode next;

    public MyNode(T item)
    {
        this.item = item;
    }
}


Построение списка по перечислению элементов:


Храним ссылки на первый и предыдущий узлы


Ссылка на первый узел нужна для его особой обработки: мы не можем на первой итерации
цикла последнему узлу проставить в качестве следующего первый (мы не знаем ещё ничего
про последний узел), поэтому для этого по-особому обрабатываем первый узел в цикле
и делаем недостающую связку "последний -> первый" после цикла
Ссылка на предыдущий узел нужна, чтобы на итерации цикла (кроме первой) предыдущему
узлу в качестве следующего проставить текущий, тем самым создавая односвязный список
с направлением "вперёд"

Проходим по исходному перечислению, по-особому обрабатывая первый узел и проставляя
связь между предыдущим и текущим для остальных узлов
Закольцовываем список, указывая последнему элементу (после цикла previousNode как
раз указывает на него) в качестве следующего первый
Возвращаем первый узел - его достаточно для работы со списком


_

private static MyNode CreateCircularList(IEnumerable ie)
{
    MyNode firstNode = null;
    MyNode previousNode = null;
    foreach (var item in ie)
    {
        var newNode = new MyNode(item);
        if (firstNode == null)
        {
            firstNode = newNode;
        }
        else
        {
            previousNode.next = newNode;
        }
        previousNode = newNode;
    }
    previousNode.next = firstNode;
    return firstNode;
}


Непосредственно само удаление элементов:


Считаем пустое перечисление элементов недопустимым вариантом
Создаём список и получаем ссылку на первый узел
Создаём флаг (isOdd), отвечающий за удаление каждого второго узла (== true - удалять,
== false - нет)
В качестве текущего (рассматриваемого) узла первоначально берём первый
Ссылка на предыдущий узел нужна для "склеивания" предыдущего и следующего при удалении
текущего
Пока узлов в списке больше одного:


Если узел нужно удалить (он второй/"четный") - склеиваем предыдущий со следующим,
тем самым исключая текущий узел из списка, и уменьшаем счетчик количества узлов в списке
на единицу
Иначе в качестве предыдущего узла устанавливаем текущий, плавно готовясь к следующей
итерации цикла, в которой этот самый предыдущий узел понадобится для "склеивания"
После чего переходим к следующему узлу и меняем значение флага

В итоге возвращаем значение единственного оставшегося узла


_

public static T RemoveEachSecondItem(IEnumerable ie)
{
    var elementsCount = ie.Count();
    if (elementsCount == 0)
        throw new Exception("Empty ie");

    var firstNode = CreateCircularList(ie);
    var isOdd = false;
    var currentNode = firstNode;
    MyNode previousNode = null;
    while (elementsCount > 1)
    {
        if (isOdd)
        {
            previousNode.next = currentNode.next;
            elementsCount--;
        }
        else
        {
            previousNode = currentNode;
        }
        currentNode = currentNode.next;
        isOdd = !isOdd;
    }
    return currentNode.item;
}




"Нечестный" вариант решения


Посчитать сразу индекс элемента, который останется. Доказательства приведённой формулы
(из количества элементов вычитаем ближайшую снизу степень двойки, после чего разность
умножаем на два - получаем нужный индекс) у меня нет, но она работает
Вернуть элемент по этому индексу. Из-за условий задачи для этого придётся воспользоваться
foreach-ем


Пример:

public static T RemoveEachSecondItemShort(IEnumerable ie)
{
    var elementsCount = ie.Count();
    var powOfTwo = 1;
    while (powOfTwo <= elementsCount)
    {
        powOfTwo <<= 1;
    }
    powOfTwo >>= 1;
    var requiredElementIndex = (elementsCount - powOfTwo) * 2;
    var index = 0;
    foreach (var element in ie)
    {
        if (index == requiredElementIndex)
            return element;

        index++;
    }
    throw new Exception("Empty ie");
}


Ответ 2

Вам в код(в цикл foreach) нужно добавить изменение переменной isOdd, ибо сейчас это
выглядит как просто foreach, в котором никогда не вызывается Remove. 


Сейчас он: isOdd == false постоянно. Когда мы в foreach делаем if(isOdd == true),
это никогда не произойдет

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


while (ie.Count() > 1)


что вы хотите получить от этого куска кода? ie.Count() будет возвращать одно и то
же, ибо когда вы делаете это ICollection ic = new ICollection(ie); вы получаете
копию, а не работаете с той же коллекцией 

В итоге когда закончится цикл foreach, вы выйдете в цикл while иии... он будет крутится
вечно). 
Если я правильно понял идею, вам нужно заменить while (ie.Count() > 1) на while (ic.Count() > 1)


ICollection ic = new ICollection(ie); нельзя создавать объект интерфейса. Ибо
интерфейс - лишь декларация, описание того как можно работать с чем то. Он не имеет
ни строчки реализации и не может. Вы можете создать(инстанцировать) только объект определенного
класса. 


Например ICollection ic = new List(ie);

тут мы говорим, что я создаю объект класс List, но работать с ним буду через интерфейс
ICollection.


Вы не можете изменять коллекцию внутри цикла foreach(спасибо @aa_talanin. Как я такое
мог забыть). Используйте не foreach, а цикл for. Но т.к. нельзя использовать цикл for...Стоит
записывать элементы, который вы хотите удалить в отдельный список, а потом в цикле
делать Remove из первой коллекции.


Ответ 3

По сути ваша задача — "Считалка Иосифа Флавия"

И если у нас на входе N элементов, то нужно найти такое максимальное целое A, чтобы
N = 2A+L, где L ⩾ 0. Тогда результатом будет элемент под индексом 2L (индексы с 0).

Поскольку, по условию на входе могут быть List или LinkedList, которые реализуют
ICollection, можно написать такое простое решение:

T FlaviusRoulette(ICollection source)
{
    int c = source.Count, n = 0;
    while (1 << n <= c) ++n;
    return source.ElementAt(2 * c - (1 << n));
}


Если же вы хотите, чтобы метод работал для любых IEnumerable — выхода нет, придется
закешировать все элементы, т. к. любой может оказаться ответом:

T FlaviusRoulette(IEnumerable source)
{
    var col = source as ICollection ?? source.ToList();
    int c = col.Count, n = 0;
    while (1 << n <= c) ++n;
    return col.ElementAt(2 * c - (1 << n));
}


Проверка:

Console.WriteLine(FlaviusRoulette(Enumerable.Range(1, 41))); // 19


Проверку source == null и source.Count == 0 оставляю на ТС.


Ответ 4

Можно пожертвовать памятью и получить быстрое и довольно простое решение:

T RemoveEachSecondItem(IEnumerable source)
{
    List src = source.ToList();
    List tgt = new List(src.Count / 2);   
    foreach(var item in source)
        src.Add(item);
    bool isRemoved = false;
    while(src.Count > 1)
    {
        foreach(T item in src)
        {
            if(!isRemoved)
                tgt.Add(item);
            isRemoved = !isRemoved;
        }
        List temp = src;
        src = tgt;
        tgt = temp;
        tgt.Clear();
    }
    return src.FirstOrDefault();
}

//Пример использования
Console.WriteLine(RemoveEachSecondItem(Enumerable.Range(1, 7), false));


Достоинства:


работать будет с любым перечислением.
хорошо оптимизируется для эффективного использования кэша процессора, за счет использования
линейных массивов, на которых строится List.


Недостатки:


дополнительный расход памяти (N*2,5+x с учетом хранения исходных данных входного
перечисления или N*1,5+x, если исходные данные не хранятся в памяти процесса, а генерируются
например, где x - разница между реальной и используемой емкостями src)
при материализации перечисления будет происходить постепенное увеличение емкости
src со всеми вытекающими накладными расходами.