Create a Set of lists from two lists through recursion

Question

I've searched through many questions on this site with somewhat similar underlying concepts, however after many hours of attempting to solve this problem myself and reviewing I am still lost. If there is another question that answers this I will be more than happy to give it a look over.

Ultimately I want to create a recursive method such that it takes two lists and returns a Set of String lists:

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

When I say "Set of String lists" I mean specifically the following: (Note:"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"]] 

Such that if there were three elements in both listOne and listTwo, there would be SIX elements in the set. i.e:

// 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"]] 

I tried writing this using a double enhanced FOR loop so I could understand the logic. My FOR loop approach is terrible and only works for the HARD-CODED limit of 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"]] 

Also you can note that I defined List<List<String>> Rather than Set<List<String>>. This was due to my badly coded attempted which relies on the list.get() method.

So my current recursive method is as follows:

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

This method only acts like this currently:

INPUT:

• List One = ["A","B"]
• List Two = ["C","D"]

OUTPUT:

• [["AC"]["BD"]]

DESIRED OUTPUT:

• [["AC","BD"],["AD","BC"]]

EDIT:

After reviewing responses my W.I.P code for the class:

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

I think the problem is here:

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

You are correct, at some point your recursion has to end, and you have to start building the desired output. But the desired output is not a Set with an empty list. It is a Set containing some lists with some content. Thus: don't wait until listOne is empty. Instead:

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

In other words: you use recursion to reduce the length of the first list by one. And when only one element is left in that list, it is time to merge in the second list.

Now lets look into how to "use" that (calling the method rec for brevity); putting down some pseudo code to show the steps we need:

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

"X" meaning "joining" two results from recursive calls; should be as easy as:

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