如何与QUOT;展开" A"递归"结构体 [英] How to "unroll" a "recursive" structure

问题描述

不知道如何称呼它，而是说你有一个类，它看起来像这样：

 类Person 
 {
公共字符串名称; 
公开的IEnumerable<&人GT;朋友; 
} 
  

您然后有一个人，你想展开这个结构递归方式你结束了所有的人没有重复一个列表。

你会如何做呢？我已经做的东西，似乎是工作，但我很好奇，看看其他人是怎么做的，尤其是如果有一些内置到LINQ，你可以在一个巧妙的方式用于解决这个小问题：）

---

下面是我的解决方案：

 公共静态的IEnumerable< T> SelectRecursive< T>（这个IEnumerable的< T>科目，Func键< T，IEnumerable的< T>>选择器）
 {
 //停止，如果对象是null或空
如果（科目= = NULL）
产量突破; 
 
 //为每个主题
的foreach（VAR学科科目）
 {
 //屈服它
收益率的回报主体; 
 
 //然后产生其所有decendants 
的foreach（VAR decendant在SelectRecursive（选择器（主题），选择器））
收益率的回报decendant; 
} 
} 
  

将用于这样的：

 变种人= somePerson.SelectRecursive（X => x.Friends）; 
  

解决方案

我不相信有内置LINQ什么做这个。

有与递归做这样一个问题 - 你最终造就了一大批的迭代器。这可能是如果树是深深的效率相当低。 韦斯代尔并的Eric利珀特兼得的博客上讲述这一点。

您可以通过删除直接递归删除这种低效率。例如：

 公共静态的IEnumerable< T> SelectRecursive< T>（这个IEnumerable的< T>科目，
 Func键< T，IEnumerable的< T>>选择器）
 {
如果（科目== NULL）
 {
产量突破; 
} 
 
问答LT; T> stillToProcess =新队列< T>（学科）; 
 
，而（stillToProcess.Count大于0）
 {$ B $（B T）项目= stillToProcess.Dequeue（）; 
收益回报的项目; 
的foreach（T孩子选择器（项目））
 {
 stillToProcess.Enqueue（小孩）; 
} 
} 
} 
  

这也将改变迭代为了 - 它成为广度优先，而不是深度优先;改写它仍然是深度优先是棘手的。我也改变了它不使用任何（） - 这个修订版不会评价任何序列不止一次，这可能是在某些情况下派上用场。这确实有一个问题，你要知道 - 这将需要更多的内存，由于排队。我们可以通过存储迭代器，而不是项目的队列可能缓解这一点，但我不知道随便......这肯定会更加复杂。

一个点注（也ChrisW指出，而我一直在寻找了博客文章:) - 如果你有你的朋友列表中的任何周期（即如果A有B和B的），那么你将永远递归

Not sure how to call it, but say you have a class that looks like this:

class Person
{
    public string Name;
    public IEnumerable<Person> Friends;
}

You then have a person and you want to "unroll" this structure recursively so you end up with a single list of all people without duplicates.

How would you do this? I have already made something that seems to be working, but I am curious to see how others would do it and especially if there is something built-in to Linq you can use in a clever way to solve this little problem :)

---

Here is my solution:

public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> subjects, Func<T, IEnumerable<T>> selector)
{
    // Stop if subjects are null or empty
    if(subjects == null)
        yield break;

    // For each subject
    foreach(var subject in subjects)
    {
        // Yield it
        yield return subject;

        // Then yield all its decendants
        foreach (var decendant in SelectRecursive(selector(subject), selector))
            yield return decendant;
    }
}

Would be used something like this:

var people = somePerson.SelectRecursive(x => x.Friends);

解决方案

I don't believe there's anything built into LINQ to do this.

There's a problem with doing it recursively like this - you end up creating a large number of iterators. This can be quite inefficient if the tree is deep. Wes Dyer and Eric Lippert have both blogged about this.

You can remove this inefficiency by removing the direct recursion. For example:

public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> subjects,
    Func<T, IEnumerable<T>> selector)
{
    if (subjects == null)
    {
        yield break;
    }

    Queue<T> stillToProcess = new Queue<T>(subjects);

    while (stillToProcess.Count > 0)
    {
        T item = stillToProcess.Dequeue();
        yield return item;
        foreach (T child in selector(item))
        {
            stillToProcess.Enqueue(child);
        }
    }
}

This will also change the iteration order - it becomes breadth-first instead of depth-first; rewriting it to still be depth-first is tricky. I've also changed it to not use Any() - this revised version won't evaluate any sequence more than once, which can be handy in some scenarios. This does have one problem, mind you - it will take more memory, due to the queuing. We could probably alleviate this by storing a queue of iterators instead of items, but I'm not sure offhand... it would certainly be more complicated.

One point to note (also noted by ChrisW while I was looking up the blog posts :) - if you have any cycles in your friends list (i.e. if A has B, and B has A) then you'll recurse forever.

这篇关于如何与QUOT;展开" A"递归"结构体的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！