查找另一个数组中所有值的索引，并从第三个数组中收集该索引中的值

Question

我想从parentIdList中的descendentList中找到匹配的索引，然后添加该索引中存在的值从idList到descendentList，然后再次检查parentIdList以获取所有匹配值的索引。

我基本上是想创建一个循环结构，这将导致在寻找这样的：

Answer 1

这似乎是工作，但只有当你可以让descendentList成为一个集。如果不是，那么我不确定终止条件是什么，它会一直添加相同索引的值。我认为设置是适当考虑你在你的评论说上面......“我想通过这个循环，直到没有更多的比赛被添加到descendentList”

Set descendentList = [2] 
def parentIdList = [0,1,2,3,2] 
def idList = [1,2,3,4,5] 

/** 
* First: I would like to find the index of matches from the descendentList in the 
* parentIdList 
*/ 
def findIndexMatches(Set descendentList, List parentIdList, List idList) { 
    List indexes = [] 
    def size = descendentList.size() 

    descendentList.each { descendent -> 
    indexes.addAll(parentIdList.findIndexValues { it == descendent }) 
    } 

    addExistingValuesToFromIdListToDecendentList(descendentList, idList, indexes) 

    // Then once again check the parentIdList for the index of all the matching values. 
    if(size != descendentList.size()) { // no more indexes were added to decendentList 
    findIndexMatches(descendentList, parentIdList, idList) 
    } 
} 

/** 
* and then add the value which exists in that index from the 
* idList to the descendentList 
*/ 
def addExistingValuesToFromIdListToDecendentList(Set descendentList, List idList, List indexes) { 
    indexes.each { 
    descendentList << idList[it as int] 
    } 
} 

findIndexMatches(descendentList, parentIdList, idList) 
println descendentList // outputs [2,3,4,5] 

Answer 2

类似下面的东西似乎工作 - 不尽管写了任何测试，所以可能会因不同的用例而失败 - 只是一个简单的，惯用的递归解决方案。

def descendentList = [2] 
def parentIdList = [0,1,2,3,2] 
def idList = [1,2,3,4,5] 

def solve(List descendentList, List parentIdList, List idList){ 
    List matchedIds = descendentList.inject([]){ result, desc -> 
     result + idList[ parentIdList.findIndexValues{ it == desc } ] 
    } 
    if (matchedIds){ 
     descendentList + solve(matchedIds, parentIdList, idList) 
    } else { 
     descendentList 
    } 
} 

println solve(descendentList, parentIdList, idList) 

Answer 3

你也可以这样做没有递归，使用迭代器：

class DescendantIterator<T> implements Iterator<T> { 
    private final List<T> parents 
    private List<T> output 
    private final List<T> lookup 
    private List<T> next 

    DescendantIterator(List<T> output, List<T> parents, List<T> lookup) { 
     this.output = output 
     this.parents = parents 
     this.lookup = lookup 
    } 

    boolean hasNext() { output } 

    Integer next() { 
     def ret = output.head() 
     parents.findIndexValues { it == ret }.with { v -> 
      if(v) { output += lookup[v] } 
     } 
     output = output.drop(1) 
     ret 
    } 

    void remove() {} 
} 

def descendentList = [2] 
def parentIdList = [0,1,2,3,2] 
def idList = [1,2,3,4,5] 

def values = new DescendantIterator<Integer>(descendentList, parentIdList, idList).collect() 

在此之后，values == [2, 3, 5, 4]

Answer 4

首先建立从父ID映射到它的所有子ID。接下来找到输入的结果，并只要没有更多的结果迭代新发现的结果。

def parentIdList = [0,1,2,3,2] 
def idList = [1,2,3,4,5] 

tree = [parentIdList, idList].transpose().groupBy{it[0]}.collectEntries{ [it.key, it.value*.get(1)] } 

def childs(l) { 
    l.collect{ tree.get(it) }.findAll().flatten().toSet() 
} 

def descendants(descendentList) { 
    def newresults = childs(descendentList) 
    def results = [].toSet() + descendentList 
    while (newresults.size()) { 
     results.addAll(newresults) 
     newresults = childs(newresults) - results 
    } 
    return results 
} 

assert descendants([2]) == [2,3,4,5].toSet() 
assert descendants([2,1]) == [1,2,3,4,5].toSet() 
assert descendants([3]) == [3,4].toSet()