Фиксировать неизменный список рекурсивно

Question

Предположим, у меня есть массив целых чисел, и мне нужно вернуть массив всех чисел, которые делятся на 3 по порядку.

Я дал интерфейс:

List<int> ListElementsDivisibleBy3Recursive(List<int> input) 

Так он должен взять список и возвращает список, фильтровать и рекурсивно. Я пробовал выскакивать элементы из начала списка, пока не набрал число, соответствующее требуемому условию, и вот где я застрял. Я не знаю, как перейти к следующему элементу и сохранить элемент, соответствующий условию. Это то, что я до сих пор:

static List<int> ListElementsDivisibleBy3Recursive(List<int> input) 
     { 
      if (input.Count == 0) 
       return input; 
      else if (input.ElementAt(0) % 3 == 0) 
      { 
       return ListElementsDivisibleBy3Recursive(input); <--I have no idea what to do here 
      } 
      else 
      { 
       input.RemoveAt(0); 
       return ListElementsDivisibleBy3Recursive(input); 
      } 
     } 

Было бы намного проще, если бы мне было позволено передать указатель на позицию в списке я на, но все у меня есть список входных и возвращение список для работы. Как удалить элементы в списке, сохранив те, которые соответствуют условию? Или я все об этом ошибаюсь? Не знаю, как я должен это делать логически. Я также понимаю, что мое базовое условие ошибочно.

Answer 1

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

List<int> ListElementsDivisibleBy3Recursive(List<int> input) { 
    if (input.Count > 0) { 
     int last = input.Last(); 
     input.RemoveAt(input.Count - 1); 
     input = ListElementsDivisibleBy3Recursive(input); 
     if (last % 3 == 0) 
      input.Add(last); 
    } 
    return input; 
} 

Хотя это бессмысленно возвращать ничего из этого метода, поскольку input изменяется в соответствии с требованиями, независимо от возвращаемого значения. Таким образом, это достигает такого же результата:

void ListElementsDivisibleBy3Recursive(List<int> input) { 
    if (input.Count > 0) { 
     int last = input.Last(); 
     input.RemoveAt(input.Count - 1); 
     ListElementsDivisibleBy3Recursive(input); 
     if (last % 3 == 0) 
      input.Add(last); 
    } 
} 

Answer 2

return input.Where(i => (i % 3) == 0).ToList(); 

Answer 3

Вся эта проблема странная.

Для решения вопроса начальная, обработки текущей позиции, вы можете следить за вашим текущим индексом (в переменной с именем count для моего кода), а затем сделать:

return currentList.AddRange(ListElementsDivisibleBy3Recursive(input.Skip(count).ToList())); 

Использование Skip для избавиться от уже обработанных элементов. Конечно, в тот момент, у вас есть LINQ, так что вы могли бы также сделать:

return currentList.AddRange(ListElementsDivisibleBy3Recursive(input.SkipWhile(i => i % 3 != 0).ToList())); 

Предоставленный, что один требует перечисления в два раза, так как вы не получите значение из SkipWhile. Но вы на самом деле не нужно рекурсии вообще, вы могли бы просто написать:

return currentList.Where(i => (i % 3) == 0).ToList(); 

Answer 4

Если вы действительно хотите, чтобы решить эту проблему с помощью рекурсии, вы можете сделать это, как этот

static List<int> FilterMod3Internal(List<int> state, List<int> initialList, int index) 
{ 
    if (index >= initialList.Count()) 
    { 
     return state; 
    } 
    else 
    { 
     var number = initialList[index]; 
     if (number%3 == 0) 
     { 
      state.Add(number); 

     } 

     return FilterMod3Internal(state, initialList, index + 1); 
    } 
} 
static List<int> FilterMod3(List<int> list) 
{ 
    return FilterMod3Internal(new List<int>(), list, 0); 
} 

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

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

static void FilterListMod3Internal(List<int> list, int index) 
{ 
    if (index >= list.Count()) 
    { 
     return; 
    } 

    var number = list[index]; 

    if (number%3 != 0) 
    { 
     list.RemoveAt(index); 
     FilterListMod3Internal(list, index); 
    } 
    else 
    { 
     FilterListMod3Internal(list, index + 1); 
    } 
} 

Оба версий являются рекурсивными, но они должны иметь какое-то внутреннюю функцию, которая имеет дополнительные параметры для поддержания состояния между вызовами функций.

Вы также можете обобщить этот вид методов, как этот

static List<T> FilterInternal<T>(List<T> state, List<T> initialList, int index, Func<T, bool> filterFunction) 
{ 
    if (index >= initialList.Count()) 
    { 
     return state; 
    } 
    else 
    { 
     var item = initialList[index]; 
     if (filterFunction(item)) 
     { 
      state.Add(item); 

     } 

     return FilterInternal(state, initialList, index + 1, filterFunction); 
    } 
} 
static List<T> Filter<T>(List<T> list, Func<T, bool> filterFunction) 
{ 
    return FilterInternal<T>(new List<T>(), list, 0, filterFunction); 
} 

и тот, который не потребляет никакой дополнительной памяти

static void FilterListInternal<T>(List<T> list, int index, Func<T, bool> filterFunction) 
{ 
    if (index >= list.Count()) 
    { 
     return; 
    } 

    var item = list[index]; 

    if (!filterFunction(item)) 
    { 
     list.RemoveAt(index); 
     FilterListInternal(list, index, filterFunction); 
    } 
    else 
    { 
     FilterListInternal(list, index + 1, filterFunction); 
    } 
} 

static void FilterList<T>(List<T> list, Func<T, bool> filterFunction) 
{ 
    FilterListInternal<T>(list, 0, filterFunction); 
} 

где filterFunction должна возвращать верно, когда вы хотите деталь быть в и в противном случае. Это легко изменить, поэтому попробуйте, вы хотите.

Answer 5

Weird вопрос :-)

Это один более гибкое решение: метод расширения для IList RecursiveFilter принимает предикат и вернуть IEnumerable (который может быть использован для построения списка, массив или что-то еще).

using System; 
using System.Collections.Generic; 

namespace Sandbox 
{ 
    class Program 
    { 
     static void Main() 
     { 
      var array = new[] { 1, 6, 8, 3, 6, 2, 9, 0, 7, 3, 5 }; 
      var filtred = array.RecursiveFilter(i => i % 3 == 0); 

      foreach (var item in filtred) 
       Console.WriteLine(item); 
     } 
    } 

    public static class MyCollectionExtensions 
    { 
     public static IEnumerable<T> RecursiveFilter<T>(this IList<T> collection, Func<T, bool> predicate, int index = 0) 
     { 
      if (index < 0 || index >= collection.Count) 
       yield break; 
      if (predicate(collection[index])) 
       yield return collection[index]; 
      foreach (var item in RecursiveFilter(collection, predicate, index + 1)) 
       yield return item; 
     }   
    } 
} 

Answer 6

Recursivly обходе список для фильтрации не особенно соответствующий алгоритм для изменяемого массива спинками списка. Это подход, который больше подходит для работы с неизменяемыми структурами. Когда имеют дело с непреложным списком (обычно моделируются как узлы как с текущим элементом и ссылкой на другой узел) рекурсивное решение очень хорошо подходит к этой проблеме:

public class Node<T> 
{ 
    public Node(T value, Node<T> tail) 
    { 
     Value = value; 
     Tail = tail; 
    } 

    public T Value { get; private set; } 
    public Node<T> Tail { get; private set; } 
} 

public static Node<int> ListElementsDivisibleBy3Recursive(Node<int> node) 
{ 
    if (node == null) 
     return node; 
    else if (node.Value % 3 == 0) 
     return new Node<int>(node.Value, ListElementsDivisibleBy3Recursive(node.Tail)); 
    else 
     return ListElementsDivisibleBy3Recursive(node.Tail); 
} 

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

A List<T> просто не подходит для этого типа алгоритма, поскольку он полагается на возможность вычислить «список со всем после первого элемента», а также легко вычислить «новый список, который равен старому но с одним добавленным к нему элементом », ни одна из которых не является операциями, которые List<T> может выполнять легко или эффективно, но эти неизменные списки обычно будут иметь в качестве основных операций.