通过递归从两个列表中创建一组列表

Question

我已经在此网站上搜索了许多问题，这些问题有些相似的基础概念，但是在之后，尝试解决此问题的我自己有问题并审查我仍然迷路。如果还有另一个问题回答这个问题，我将很乐意让它看看。

最终我想创建一个递归方法，以便访问两个列表并返回A 一组字符串列表：

//Example of such a function definition
private static Set<List<String>> myRecursiveMethod(List<String> listOne, 
List<String> listTwo) {
}

当我说"字符串列表"时，我的意思是特别以下：(注意：" ad" ==" da"(

// if the two following lists are INPUTTED into myRecursiveMethod();
// listOne = ["A","B"]
// listTwo = ["C","D"]
// the following set is OUTPUTTED: [["AC","BD"],["AD","BC"]] 

这样，如果ListOne和ListTwo都有三个元素，则该集合中将有六个元素。即：

// listOne = ["A","B","C"]
// listTwo = ["D","E","F"]
// OUTPUTTED: [["AD","BE","CF"],["AD","BF","CE"],["BD","AE","CF"],
// ["BD","AF","CE"],["CD","AE","BF"],["CD","AF","BE"]] 

我尝试使用双重增强循环编写本文，以便我可以理解逻辑。我的循环方法很糟糕，唯一的适用于list.Size((== 2的硬编码限制。

// Create Lists and append elements 
List<String> listOne = new ArrayList<String>();
listOne.add("A");
listOne.add("B");
List<String> listTwo = new ArrayList<String>();
listTwo.add("C");
listTwo.add("D");
// List One = ["A","B"]
// List Two = ["C","D"]
// Create new List
List<List<String>> newList = new ArrayList<List<String>>();
Integer counter = 0;
    for (String s : listOne) {
        counter++;
        for (String p : listTwo) {
            // A HARD-CODED bad implementation of this method
            if (counter < 3) {
                List<String> newListTwo = new ArrayList<String>();
                newListTwo.add(s.concat(p));
                newList.add(newListTwo);
            } else if (!(counter % 2 == 0)) {
                newList.get(1).add(s.concat(p));
            } else {
                newList.get(0).add(s.concat(p));
            }
        }
    }
    System.out.println(newList); // = [["AC","BD"],["AD","BC"]] 

您还可以注意，我定义了列表＆lt; lt; string＆gt;＆gt;而不是 set＆lt; list＆lt; string＆gt;＆gt;。这是由于我的编码不好的尝试，该试图依赖于list.get((方法。

所以我当前的递归方法如下：

private static Set<List<String>> myRecursiveMethod(List<String> listOne, 
List<String> listTwo) 
{
    //Base Case:
    if (listOne.isEmpty){
        return new HashSet<List<String>>;
    }
    //Recursive Case:
    else {
        String listOneFirst = listOne.get(0);
        String listTwoFirst = listTwo.get(0);
        List<String> sampleList = new ArrayList<String>();
        sampleList.add(listOneFirst+listTwoFirst);
        Set<List<String>> newSet = new HashSet<List<String>>(myRecursiveMethod())
        newSet.add(sampleList);
        return newSet;
    }
}

此方法目前仅采用这种方式：

输入：

• 列表一= [" a"，" b"]
• 列表两个= [" C"，" D"]

输出：

• [[" ac"] [" bd"]]

所需的输出：

• [[" ac"，" bd"]，[ad'，" bc"]]

编辑：

审查了我的班级的W.I.P代码后：

private static Set<List<String>> myRecursiveMethod(List<String> listOne,
        List<String> listTwo) {
    //Backup Case (user enters an empty list)
    if (listOne.isEmpty()){
        return new HashSet<List<String>>();
    }
    // Base Case:
    if (listOne.size() == 1) {
        List<String> mergedStrings = new ArrayList<>();
        for (String s : listTwo) {
            mergedStrings.add(listOne.get(0).concat(s));
        }
        Set<List<String>> builtHashSet = new HashSet<List<String>();
        builtHashSet.add(mergedStrings);
        return builtHashSet;
    }
    // Recursive Case:
    else {
        // Ensure original list values arn't changed.
        List<String> newListOne = new ArrayList<String>(listOne);
        List<String> newListTwo = new ArrayList<String>(listTwo);
        //first two elements...I don't think this is correct
        String listOneFirst = newListOne.get(0);
        String listTwoFirst = newListTwo.get(0);
        List<String> sampleList = new ArrayList<String>();
        sampleList.add(listOneFirst + listTwoFirst);
        //used for making recursive case smaller
        newListOne.remove(0);
        // Calls recursion
        Set<List<String>> newSet = new HashSet<List<String>>(
                myRecursiveMethod(newListOne, newListTwo));
        newSet.add(sampleList);
        return newSet;
    }
}

Answer 1

我认为问题在这里：

if (listOne.isEmpty){
    return new HashSet<List<String>>;
}

您是正确的，在某个时候，您的递归必须 END ，并且您必须启动 building 所需的输出。但是所需的输出是不是带有空列表的集合。这是一个包含一些内容的列表的集合。因此：不要等到ListOne为空。而是：

if (listOne.size() == 1) {
  List<String> mergedStrings = new ArrayList<>();
  mergedStrings = ... merge the ONE listOne entry with all listTwo entries
  Set<List<String>> rv = new HashSet<>();
  rv.add(mergedStrings);
  return rv;
}

换句话说：您使用递归将第一个列表的长度缩小一个。当该列表中只剩下一个元素时，是时候在第二个列表中合并了。

现在让我们研究如何"使用"该方法(以简洁的方式调用方法rec(；放下一些伪代码以显示我们需要的步骤：

rec([a, b], [c,d]) -->
rec([a], [c,d]) X rec([b], [c, d]) -->
<[ac, ad]> X <[bc, bd]> -->
<[ac, ad], [bc, bd]>

" x"含义"加入"递归调用的两个结果；应该像：

一样容易

Set<List<String>> rec1 = rec(...);
return rec1.addAll(rec2 ...