家谱祖先查找算法

Question

我的方法无法通过单元测试。我白费了5个小时的努力。有人能帮我看看哪里出了问题吗？

PS：我的代码中的getAllRelations（）方法是将格式化的输入分成字符串的ArrayList的ArrayList，例如，如果我有这样的格式化输入（我在不能通过的测试用例中使用了它）

String format = "John Doe , Mary Smith" + "\n" + "Brian William , John Doe" + "\n" + "Brian William ,Robert Andrew" + "\n" + "Mary Smith , Max Jackson";

每一行的第一个人是第二个人的父母。getAllRelations()方法将把这些格式化字符串分割成arraylists，每个列表只包含每行中的两个名称字符串（名称前后没有空格）作为其元素。例如，arraylist1将是一个包含“John”和“Mary Smith”的列表。

这是我的方法，我无法确定哪里出了问题，我想使用此方法来检查两个人是否共享同一祖先。

private boolean hasSameAncestor(String person1, String person2){
    ArrayList<ArrayList<String>> allRelations = allRelations();
    int i = 0;
    int j = 0;
    String name1 = person1;
    String name2 = person2;
    String parent1;
    String parent2;
    for(i = 0, parent1 = ""; i < allRelations.size(); i++){
        if(name1.equals(allRelations.get(i).get(1))){
            parent1 = allRelations.get(i).get(0);
            for(j = 0, name2 = person2, parent2 = ""; j < allRelations.size(); j++){
                if(name2.equals(allRelations.get(j).get(1))){
                    parent2 = allRelations.get(j).get(0);
                    if(parent2.equals(parent1)){
                        return true;
                    }
                    else{
                        name2 = parent2;
                        j = 0;
                    }
                }
            }
            name1 = parent1;
            i = 0;
        }
    }
    return false;
}

我无法通过的测试用例如下。

    @Test
    public void testHasSameAncestor()
    FamilyTree familyTree4 = new FamilyTree("John Doe , Mary Smith" + "\n" + "Brian William , John Doe" + "\n" + "Brian William ,Robert Andrew" + "\n" + "Mary Smith , Max Jackson");
    assertEquals(true, format.hasSameAncestor("Max Jackson", "Robert Andrew"));
}

我不知道我的函数哪里出了问题，能否有人帮我一下？非常感谢。

以下是可粘贴到Eclipse进行调试的代码

package test;

import java.util.ArrayList;
import java.util.Arrays;


public class Test1 {

    String test;

    public Test1(String test){
        this.test = test;
    }


    private ArrayList<String> lineRelations(){
        int i;
        ArrayList<String> lineRelations = new ArrayList<String>();
        String[] lines = test.split("\n");
        for(i = 0; i < lines.length; i++){
            lineRelations.add(lines[i]);
        }
        return lineRelations;
    }

    private ArrayList<ArrayList<String>> allRelations(){
        int i;
        ArrayList<ArrayList<String>> allRelations = new ArrayList<ArrayList<String>>();
        ArrayList<String> lineRelations = lineRelations();
        for(i = 0; i < lineRelations.size(); i++){
            ArrayList<String> eachLine = new ArrayList<String>(Arrays.asList(lineRelations.get(i).split("\\s*,\\s*")));
            allRelations.add(eachLine);
        }
        return allRelations;
    }

    public boolean hasSameAncestor(String person1, String person2){
        ArrayList<ArrayList<String>> allRelations = allRelations();
        int i = 0;
        int j = 0;
        String name1 = person1;
        String name2 = person2;
        String parent1;
        String parent2;
        for(i = 0, parent1 = ""; i < allRelations.size(); i++){
            if(name1.equals(allRelations.get(i).get(1))){
                parent1 = allRelations.get(i).get(0);
                for(j = 0, name2 = person2, parent2 = ""; j < allRelations.size(); j++){
                    if(name2.equals(allRelations.get(j).get(1))){
                        parent2 = allRelations.get(j).get(0);
                        if(parent2.equals(parent1)){
                            return true;
                        }
                        else{
                            name2 = parent2;
                            j = 0;
                        }
                    }
                }
                name1 = parent1;
                i = 0;
            }
        }
        return false;
    }
}

测试用例

package test;
import static org.junit.Assert.*;
import test.Test1;

import org.junit.Test;


public class Test1Test {

    @Test
    public void testHasSameAncestor(){
        Test1 test1 = new Test1("John Doe , Mary Smith" + "\n" + "Brian William , John Doe" + "\n" + "Brian William ,Robert Andrew" + "\n" + "Mary Smith , Max Jackson");
        assertEquals(true, test1.hasSameAncestor("Max Jackson", "Robert Andrew"));
    }
}

- user1835156

---

为什么你这么生气...我只是想得到一些帮助..我运行了它。单元测试告诉我实际结果是false而不是预期的true...然而，调试对我来说没有显示任何有意义的东西...所以我无法弄清楚为什么。 - user1835156

请提供allRelations()方法或返回所有关系的示例数据，或许allRelations()方法存在一些错误？ - Yusuf K.

如果您希望我们调试您的代码并找到解决方案，您必须提供完整可运行的代码。这样我就可以将其复制粘贴到我的Eclipse中，并找到并帮助您 :) - Yusuf K.

我发现了你算法中的错误，很快会发布。 - Yusuf K.

盯着代码看并不是一种有效的调试方法。我写了一个替代方案：http://www.patriciashanahan.com/debug - Patricia Shanahan

Answer 1

首先找到两个人的基础祖先，然后进行比较。请检查一下 :)

public boolean hasSameAncestor(String person1, String person2) {
        ArrayList<ArrayList<String>> allRelations = allRelations();
        int i = 0;
        String name1 = person1;
        String name2 = person2;
        String parent1;
        String parent2;

        //Find first person's ancestor
        for (i = 0, parent1 = ""; i < allRelations.size(); i++) {
            if (name1.equals(allRelations.get(i).get(1))) {
                parent1 = allRelations.get(i).get(0);
                name1 = parent1;
                i = -1; // because i will increase before start new loop
            }
        }

        //Find second person's ancestor
        for (i = 0, parent2 = ""; i < allRelations.size(); i++) {
            if (name2.equals(allRelations.get(i).get(1))) {
                parent2 = allRelations.get(i).get(0);
                name2 = parent2;
                i = -1;
            }
        }
        System.out.println(parent1);
        System.out.println(parent2);
        if (parent1.equals(parent2)) {
            return true;
        }
        return false;
    }

祝一切顺利。

- Yusuf K.

Answer 2

首先，您正在使用的数据结构对于这种应用程序来说非常糟糕。您应该构建一个实际的数据结构来表示您的家谱，而不是将所有内容打包成一个字符串，然后在双重循环中拆分字符串并进行处理。

在信息学中，树是您想要用于此任务的一种结构。树有两种不同类型的对象：

1) A Node, which has two children, that are also Nodes.
2) A Leaf, which has no children.

您可以使用这些节点来建立您的家谱，然后应用已知的众多树算法之一。（类似问题请参考两个二叉搜索树的交集）

更具体地说：您模型中的每个人都将有另外两个人被定义为他们的父母。一个叶子是一个没有（已知）父母的人。然后，您可以运行一个计算两个二叉树的交集的算法。如果交集为空，则它们没有共同的祖先。

- zhujik

---

输入格式是由我的老师给定的...我自己真的不想把它们打包成这样的字符串...但是...作业... - user1835156

你可以使用输入字符串一次性构建你的数据结构，我不认为你的老师会对此抱怨（否则我会质疑这个人的能力）。 - zhujik

Answer 3

"Max Jackson"和"Robert Andrew"有不同的祖先。 "John Doe"和"Robert Andrew"有相同的祖先。 请按照下面所示更改您的条件并检查。

assertEquals(false, format.hasSameAncestor("Max Jackson", "Robert Andrew"));
assertEquals(true, format.hasSameAncestor("John Doe", "Robert Andrew"));

- Shan

---

祖先不仅指父母，也可以是祖父母或者更高的级别。 - user1835156

Answer 4

你的关系是从右到左的，对吧？

所以Max和Mary有关系，Mary和John也有关系。Robert只和Brian有关系，他不在右边。但你也想检查另一个方向，对吗？所以Brian也和John有关系，他们都有同一个祖先。但这很不寻常。

使用哈希表和从左到右的递归搜索来检查这个解决方案：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class Test {

    private String test;
    private HashMap<String, String> allRelations;
    private ArrayList<String> ancestors;
    public Test(String test){
        this.test = test;
        allRelations = allRelations();
        ancestors= new ArrayList<String>();
    }

    private ArrayList<String> lineRelations(){
        int i;
        ArrayList<String> lineRelations = new ArrayList<String>();
        String[] lines = test.split("\n");
        for(i = 0; i < lines.length; i++){
            lineRelations.add(lines[i]);
        }
        return lineRelations;
    }

    private HashMap<String, String> allRelations(){
        int i;
        HashMap<String, String> allRelations = new HashMap<String, String>();
        ArrayList<String> lineRelations = lineRelations();
        for(i = 0; i < lineRelations.size(); i++){
            allRelations.put(Arrays.asList(lineRelations.get(i).split("\\s*,\\s*")).get(0), Arrays.asList(lineRelations.get(i).split("\\s*,\\s*")).get(1));                      
        }
        return allRelations;
    }

    public boolean hasSameAncestor(String person1, String person2){
        if (allRelations.containsKey(person1)){
            if (ancestors.contains(allRelations.get(person1))){                                             
                if (allRelations.containsKey(person2)){
                    if (ancestors.contains(allRelations.get(person2))){
                        return true;
                    } else if (allRelations.containsKey(allRelations.get(person2))){
                        return hasSameAncestor(person1, allRelations.get(person2));
                    } else {
                        return false;
                    }
                } else {
                    return false;
                }
            } else {
                ancestors.add(allRelations.get(person1));
                if (allRelations.containsKey(allRelations.get(person1))){
                    return hasSameAncestor(allRelations.get(person1), person2);
                } else if (allRelations.containsKey(person2)) {
                    return hasSameAncestor(person1,allRelations.get(person2));
                } else {
                    return false;
                }
            }
        } else {
            return false;
        }       
    }
}

这将返回 true。

Test test1 = new Test("a1 , b1" + "\n" + "b1 , c1" + "\n" + "a2 , b2" + "\n" + "b2 , c1" + "\n" + "a3 , c3");
System.out.println(test1.hasSameAncestor("a1", "a2"));

并为假

System.out.println(test1.hasSameAncestor("a1", "a3"));

敬礼

- pyr0

Answer 5

你的内部循环总是从1开始。

在循环中将i = -1，j = -1而不是0将解决问题。

- Bo PENG

---

祖先不仅仅指父母，它可以是祖父母或更多。 - user1835156