Scala：在元素列表的元素之间递归搜索 [英] Scala: Recursive search among elements of a list of elements

问题描述

如果我有这样的类：

  class Person（var name：String，var surname：String，var sons ：Set [Person]）
  

我想控制一个人在他的儿子之间不能包含自己和他的儿子的儿子。
我该如何做？

我曾经想过一个递归搜索。但我必须小心不要创建循环。
我可以使用一个布尔作为警卫，只是你发现一个包含自身的项目停止搜索。

如何实现？你有想法吗？
非常感谢。

UPDATE
非常感谢您的帮助。好的答案，但最重要的是你有很好的想法。

我的实际情况如下：

b
trait ArchitecturalElement使用TypedElement {}扩展PropertyHolderElement

抽象类Component extends ConnectableElement with ArchitecturalElement {
var subElements：Set [ ArchitecturalElement]
var interactionPoints：Set [InteractionPoint]
//这里我把控件
//一个组件不能包含自己在他的subElements和子元素
def notHerOwnDescendant = {
def notDescendant（ancestor：Component，current：Component，checked：Set [ArchitecturalElement]）：Boolean =
！current.subElements.contains（ancestor）&& current.subElements.forall（
p => checked.contains（p）|| notDescendant（ancestor，p，checked + p））

notDescendant（this，this，Set
}

} //组件

抽象类InteractionPoint扩展ConnectableElement {}

类SAInterface（var name：String，
var description：String =empty，
var direction：SAInterfaceDirection = null
）使用ArchitecturalElement扩展InteractionPoint

类SAComponent（var name：String，
var description：String =empty，
var subElements：Set [ArchitecturalElement] = Set（），
var interactionPoints：Set [InteractionPoint] = Set（）
）extends Component


但我有不兼容的类型：

;发现：a0Dominio.ArchitecturalElement必需：a0Dominio.SAComponent

  p => checked.contains（p）|| notDescendant（ancestor，p，checked + p）
 // ^ here 
  

[ArchitecturalElement]，我派生一个Set [Component]？
组件继承自ArchitecturalElement。

解决方案

以下方法生成当前人员的所有后代，

  def descendants（stop：Set [Person] = Set（））：Set [Person] 
 if（stop contains this）Set（）
 else this.sons.flatMap（descendants（_，stop + this））+ this 
  

您可以使用它来检查您的条件。为了检测任意循环，一旦你在 if 的第一个分支中结束，你就有一个肯定的结果。

另一种方法是在构造函数/ setters中强制执行图形为非循环。这允许您使用没有停止集的搜索，因为所有现有实例都保证无循环，并且可以使用稍微更简单和更快的方法来测试条件。

If I have a class like this:

class Person (var name:String, var surname:String, var sons: Set[Person])

I want to have a control that a Person cannot contain herself between his sons and the sons of his sons. How can I do this?

I had thought a recursive search. But I have to be careful not to create cycles. I can use a Boolean as a guard and just you find an item that contains itself stops searching.

How can I implement this? Do you have ideas? Thank you very much.

UPDATE Thank you very much for your help. Good answers, but above all you had great ideas. Now I just need a little last help to test this check on my small project.

My real situation is as follows:

trait ArchitecturalElement extends PropertyHolderElement with TypedElement{}

abstract class Component extends ConnectableElement with ArchitecturalElement {
  var subElements : Set[ArchitecturalElement]
  var interactionPoints : Set[InteractionPoint]
  //Here I put the control
  //A component cannot contain himself in his subElements and in subElements of it subelement
  def notHerOwnDescendant = {
  def notDescendant(ancestor: Component, current: Component, checked: Set[ArchitecturalElement]): Boolean =
  !current.subElements.contains(ancestor) && current.subElements.forall(
        p => checked.contains(p) || notDescendant(ancestor, p, checked + p))

  notDescendant(this, this, Set())
  }

 }//Component

abstract class InteractionPoint extends ConnectableElement{}

class SAInterface(  var name : String,
        var description : String = "empty",
        var direction : SAInterfaceDirection = null
        )extends InteractionPoint with ArchitecturalElement

class SAComponent ( var name :String,
        var description : String = "empty",
        var subElements : Set[ArchitecturalElement] = Set(),
        var interactionPoints : Set[InteractionPoint] = Set()
        ) extends Component

But I have an incompatible types:

type mismatch; found : a0Dominio.ArchitecturalElement required: a0Dominio.SAComponent

p => checked.contains(p) || notDescendant(ancestor, p, checked + p)
                                                //  ^  here

From a Set [ArchitecturalElement], I derive a Set [Component]? Whereas Component inherits from ArchitecturalElement.

解决方案

The following method produces all descendants of the current person, while it doesn't get lost in cycles:

def descendants(stop: Set[Person] = Set()): Set[Person] = 
  if(stop contains this) Set() 
  else                   this.sons.flatMap(descendants(_,stop + this)) + this

You can use it to check for your condition. In order to detect arbitrary cycles, you have a positive result once you end up in the first branch of the if.

An alternative is to enforce the graph to be acyclic in the constructor/setters. This allows you to use a search without the stop set, since all existing instances are guaranteed to be cycle free and the condition can be tested with a slightly more simpler and faster approach.

这篇关于Scala：在元素列表的元素之间递归搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！