java - 家谱祖先查找算法

Question

我的方法无法通过单元测试。我徒劳地盯着它看了5个小时。有人可以帮我看看它有什么问题吗？

PS：我下面代码中的 getAllRelations() 方法是将格式化的输入分隔为字符串 ArrayList 的数组列表，例如，如果我有这样的格式化输入（我在无法通过的测试用例中使用它）

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

在每一行中，第一个人是第二个人的父母。getAllRelations() 方法会将这些格式化的字符串拆分为数组列表，其中每个列表仅包含每行中的两个名称字符串（名称前后没有空格）作为其元素。例如 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"));
    }
}

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;
    }

最好的祝愿。

Answer 2

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

在循环中使 i = -1, j = -1 而不是 0 将解决。

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"));

Answer 4

首先，您使用的数据结构对于这种应用程序来说是可怕的。您应该为您的家谱构建一个实际的数据结构，而不是将所有内容打包成一个字符串，然后将字符串拆分并在双循环中处理它。

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

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

您可以使用此节点对您的家谱进行建模，然后应用已知的众多树算法之一。（与此类似的问题是Intersection of 2 binary search trees）

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

Answer 5

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

所以 Max 与 Mary 相关，而 Mary 与 John 相关。罗伯特只与布莱恩有关。他不在右手边。但是您也想检查另一个方向（？），所以 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"));

问候