Print Out All Possible Combinations of an Arraylist<Arraylist<String>> Recursively

Generate all combinations from multiple lists

You need recursion:

Let's say all your lists are in lists, which is a list of lists. Let result be the list of your required permutations. You could implement it like this:

void generatePermutations(List<List<Character>> lists, List<String> result, int depth, String current) {
    if (depth == lists.size()) {
        result.add(current);
        return;
    }

    for (int i = 0; i < lists.get(depth).size(); i++) {
        generatePermutations(lists, result, depth + 1, current + lists.get(depth).get(i));
    }
}

The ultimate call will be like this:

generatePermutations(lists, result, 0, "");

Java recursion to find all the possible permutations & combinations in Arraylist quits too early

Note: Using ArrayLists like this for alphabets, along with for-loop and recursion is not optimal and extremely expensive in term of resources. This solution is only to illustrate the concept of recursion as mentioned in the question.

---

As you are looking for the recursive solution, to understand the concept, here it is.

The primary idea is that as you keep removing an alphabet from the ArrayList, keep adding them to another list so that they don't get lost and use both the lists to find all the possible combinations.

Code:

static ArrayList<String> permutations = new ArrayList<String>();

public static void main(String[] args) {
    ArrayList<String> letterArray = new ArrayList<String>();
    letterArray.add("w");
    letterArray.add("h");
    letterArray.add("a");
    letterArray.add("t");
    wordFinder(new ArrayList<String>(), letterArray);
    System.out.println(Arrays.asList(permutations));
}

public static void wordFinder(ArrayList<String> sub,
        ArrayList<String> letterArray) {
    permutations.add(sub.toString());
    if (letterArray.size() != 0) {
        for (int i = 0; i < letterArray.size(); i++) {
            ArrayList<String> prefix = new ArrayList<String>(sub);
            prefix.add(letterArray.get(i));
            ArrayList<String> postfix = new ArrayList<String>(letterArray);
            postfix.remove(i);
            wordFinder(prefix, postfix);
        }
    }
}

Java - Permutation of objects in Arraylist within an Arraylist

I think the keyword to your question is cartesian product rather than permutation. You can try something like this:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.BinaryOperator;
import java.util.function.Supplier;
import java.util.stream.Stream;

class Test{
    public static void main(String[] args){
        List<List<String>> totalList = new ArrayList<>();
        totalList.add(Arrays.asList("1.1","1.2","1.3"));
        totalList.add(Arrays.asList("2.1"));
        totalList.add(Arrays.asList("3.1","3.2"));
        Supplier<Stream<String>>[] sup = new Supplier[totalList.size()];

        for(int i = 0; i<totalList.size();i++){
            final int j = i;
            sup[i]= () -> totalList.get(j).stream();
        }

        Stream<String> result = cartesian((a, b) -> a+"|"+b, sup);
        result.forEach(System.out::println);
    }

    private static <T> Stream<T> cartesian(BinaryOperator<T> aggregator, Supplier<Stream<T>>... streams) {
    return Arrays.stream(streams)
        .reduce((s1, s2) -> 
            () -> s1.get().flatMap(t1 -> s2.get().map(t2 -> aggregator.apply(t1, t2))))
        .orElse(Stream::empty).get();
    }
}

See this other SO questions for more information:
Cartesian product of streams in Java 8 as stream (using streams only)

Cartesian product of arbitrary sets in Java

Get ArrayList of all possible permutations of an ArrayList

Here's one way to do it:

public static void permutation(List<coordinate> nums) {
    List<List<coordinate>> accum = new ArrayList<List<coordinate>>();
    permutation(accum, Arrays.<coordinate>asList(), nums);
    System.out.println(accum);
}

private static void permutation(List<List<coordinate>> accum, List<coordinate> prefix, List<coordinate> nums) {
    int n = nums.size();
    if (n == 0) {
        accum.add(prefix);
    } else {
        for (int i = 0; i < n; ++i) {
            List<coordinate> newPrefix = new ArrayList<coordinate>();
            newPrefix.addAll(prefix);
            newPrefix.add(nums.get(i));
            List<coordinate> numsLeft = new ArrayList<coordinate>();
            numsLeft.addAll(nums);
            numsLeft.remove(i);
            permutation(accum, newPrefix, numsLeft);
        }
    }
}

Combinations of Map<Object, List<Object>>

Here's a recursive solution:

public static void main(String[] args) {

    // your data map
    Map<GC, List<RR>> map;

    // the map entry set as list, which will help
    // combining the elements
    //
    // note this is a modifiable list

    List<Map.Entry<GC, List<RR>>> mapEntryList =
            new ArrayList<Map.Entry<GC, List<RR>>>(map.entrySet());

    // the combinations list, which will store
    // the desired results

    List<RR> combinations = new ArrayList<RR>();

    doRecursion(mapEntryList, combinations);
}

private static void doRecursion(
        List<Map.Entry<GC, List<RR>>> mapEntryList,
        List<RR> combinations) {

    // end of recursion

    if (mapEntryList.isEmpty()) {

        // do what you wish
        //
        // here i print each element of the combination

        for (RR rr : combinations) {

            System.out.println(rr);
        }

        System.out.println();

        return;
    }

    // remove one GC from the entry list,
    // then for each RR from the taken GC
    //     put RR in the combinations list,
    //     call recursion
    //     the remove RR from the combinations list
    // end for each
    // then put GC back into its list

    Map.Entry<GC, List<RR>> entry = mapEntryList.remove(0);

    List<RR> entryValue = new ArrayList<RR>(entry.getValue());

    while (!entryValue.isEmpty()) {

        RR rr = entryValue.remove(0);

        combinations.add(rr);

        doRecursion(mapEntryList, combinations);

        combinations.remove(combinations.size() - 1);
    }

    mapEntryList.add(0, entry);
}

Create a list of combinations recursively

A recursive implementation of any algorithm is comprised of two parts:

• base case - a condition that terminates a branch of recursive calls and represents an edge case for which result is known in advance;
• recursive case - a part where the logic resides and the recursive calls are made.

For this task a base case will be a situation when size of the combination equals to a target size (denoted as r in your code, in the code below I gave it a name targetSize).

Explanation of the recursive logic:

• Every method call tracks its own combination;
• Every combination unless it reaches the targetSize is used as a blue-print for other combinations;
• Each item from the source of data can be used only once, hence when it's being added to a combination it must be removed from the source.

The type ArrayList<Integer[]> which you are using to store the combination isn't a good choice. Arrays and generics do not play well together. List<List<Integer>> will be more appropriate for this purpose.

Also in my code List is used as a source of data instead of an array, which isn't a complicated conversion and can be achieved easily.

Pay attention to the comments in the code.

    private List<List<Integer>> createCombination(List<Integer> source, List<Integer> comb, int targetSize) {
        if (comb.size() == targetSize) { // base condition of the recursion
            List<List<Integer>> result = new ArrayList<>();
            result.add(comb);
            return result;
        }

        List<List<Integer>> result = new ArrayList<>();
        Iterator<Integer> iterator = source.iterator();
        while (iterator.hasNext()) {
            // taking an element from a source
            Integer item = iterator.next();
            iterator.remove(); // in order not to get repeated the element has to be removed

            // creating a new combination using existing as a base
            List<Integer> newComb = new ArrayList<>(comb);
            newComb.add(item); // adding the element that was removed from the source
            result.addAll(createCombination(new ArrayList<>(source), newComb, targetSize)); // adding all the combinations generated
        }
        return result;
    }

For the input

    createCombination(new ArrayList<>(List.of(1, 2, 3)), new ArrayList<>(), 2));

It'll produce the output

[[1, 2], [1, 3], [2, 3]]

Finding all possible combinations of numbers to reach a given sum

This problem can be solved with a recursive combinations of all possible sums filtering out those that reach the target. Here is the algorithm in Python:

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        print "sum(%s)=%s" % (partial, target)
    if s >= target:
        return  # if we reach the number why bother to continue
    
    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [n]) 
   

if __name__ == "__main__":
    subset_sum([3,9,8,4,5,7,10],15)

    #Outputs:
    #sum([3, 8, 4])=15
    #sum([3, 5, 7])=15
    #sum([8, 7])=15
    #sum([5, 10])=15

This type of algorithms are very well explained in the following Stanford's Abstract Programming lecture - this video is very recommendable to understand how recursion works to generate permutations of solutions.

Edit

The above as a generator function, making it a bit more useful. Requires Python 3.3+ because of yield from.

def subset_sum(numbers, target, partial=[], partial_sum=0):
    if partial_sum == target:
        yield partial
    if partial_sum >= target:
        return
    for i, n in enumerate(numbers):
        remaining = numbers[i + 1:]
        yield from subset_sum(remaining, target, partial + [n], partial_sum + n)

Here is the Java version of the same algorithm:

package tmp;

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

class SumSet {
    static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) {
       int s = 0;
       for (int x: partial) s += x;
       if (s == target)
            System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target);
       if (s >= target)
            return;
       for(int i=0;i<numbers.size();i++) {
             ArrayList<Integer> remaining = new ArrayList<Integer>();
             int n = numbers.get(i);
             for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j));
             ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
             partial_rec.add(n);
             sum_up_recursive(remaining,target,partial_rec);
       }
    }
    static void sum_up(ArrayList<Integer> numbers, int target) {
        sum_up_recursive(numbers,target,new ArrayList<Integer>());
    }
    public static void main(String args[]) {
        Integer[] numbers = {3,9,8,4,5,7,10};
        int target = 15;
        sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target);
    }
}

It is exactly the same heuristic. My Java is a bit rusty but I think is easy to understand.

C# conversion of Java solution: (by @JeremyThompson)

public static void Main(string[] args)
{
    List<int> numbers = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
    int target = 15;
    sum_up(numbers, target);
}

private static void sum_up(List<int> numbers, int target)
{
    sum_up_recursive(numbers, target, new List<int>());
}

private static void sum_up_recursive(List<int> numbers, int target, List<int> partial)
{
    int s = 0;
    foreach (int x in partial) s += x;

    if (s == target)
        Console.WriteLine("sum(" + string.Join(",", partial.ToArray()) + ")=" + target);

    if (s >= target)
        return;

    for (int i = 0; i < numbers.Count; i++)
    {
        List<int> remaining = new List<int>();
        int n = numbers[i];
        for (int j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);

        List<int> partial_rec = new List<int>(partial);
        partial_rec.Add(n);
        sum_up_recursive(remaining, target, partial_rec);
    }
}

Ruby solution: (by @emaillenin)

def subset_sum(numbers, target, partial=[])
  s = partial.inject 0, :+
# check if the partial sum is equals to target

  puts "sum(#{partial})=#{target}" if s == target

  return if s >= target # if we reach the number why bother to continue

  (0..(numbers.length - 1)).each do |i|
    n = numbers[i]
    remaining = numbers.drop(i+1)
    subset_sum(remaining, target, partial + [n])
  end
end

subset_sum([3,9,8,4,5,7,10],15)

Edit: complexity discussion

As others mention this is an NP-hard problem. It can be solved in exponential time O(2^n), for instance for n=10 there will be 1024 possible solutions. If the targets you are trying to reach are in a low range then this algorithm works. So for instance:

subset_sum([1,2,3,4,5,6,7,8,9,10],100000) generates 1024 branches because the target never gets to filter out possible solutions.

On the other hand subset_sum([1,2,3,4,5,6,7,8,9,10],10) generates only 175 branches, because the target to reach 10 gets to filter out many combinations.

If N and Target are big numbers one should move into an approximate version of the solution.

Writing Combinations Recursively using ArrayList of Integers in Java

You're clearing preArr before you're done with that set of permutations. You probably want to remove the last element instead.

---

Related Topics