How to return a list of combinations of a list of items in Java starting with a specific item?

Question

For example, if I have an array list like the following:

String[] fruits = {"apple", "banana", "strawberry", "kiwi", "grape"};

and I want to return a list of lists that contain combination of items in fruits starting from "banana" such as:

 ["banana"]
 ["banana","apple"]
 ["banana", "apple","strawberry",]
 ["banana", "apple","strawberry","kiwi"]
 ["banana", "apple","strawberry","kiwi", "grape"]
 ["banana", "strawberry"]
 ........
 

What is the fastest way and cleanest way to return the list of lists of combination?

Answer 1

Here is an Iterative solution

Why Iterative?

• Faster than a recursive approach
• No stack overflow.

Why not ArrayList?

• ArrayLists internally uses an array so extra space is reserved.

Why Generic Method?

• It can now work with any data type which will reduce code redundancy

import java.util.LinkedList;
import java.util.List;

public class TestPractice {
    public static void main(String[] args) {
        String[] x = {"apple", "banana", "strawberry", "kiwi", "grape"};
        System.out.println(subsets(x));
    }

    public static<E> List<LinkedList<E>> subsets(E[] x) {
        LinkedList<LinkedList<E>> subsets = new LinkedList<>();
        subsets.add(new LinkedList<>());
        
        for(E s: x) {
            LinkedList<LinkedList<E>> temp = new LinkedList<>();
            for(LinkedList<E> l1: subsets) {
                LinkedList<E> l2 = new LinkedList<>(l1);
                l2.add(s);
                temp.add(l2);
            }
            subsets.addAll(temp);
        }

        subsets.remove(0);
        return subsets;
    }
    
}

Output (List of Lists)

[[apple], 
[banana], 
[apple, banana], 
[strawberry], 
[apple, strawberry], 
[banana, strawberry], 
[apple, banana, strawberry], 
[kiwi], 
[apple, kiwi], 
[banana, kiwi], 
[apple, banana, kiwi], 
[strawberry, kiwi], 
[apple, strawberry, kiwi], 
[banana, strawberry, kiwi], 
[apple, banana, strawberry, kiwi], 
[grape], 
[apple, grape], 
[banana, grape], 
[apple, banana, grape], 
[strawberry, grape], 
[apple, strawberry, grape], 
[banana, strawberry, grape], 
[apple, banana, strawberry, grape], 
[kiwi, grape], [apple, kiwi, grape], 
[banana, kiwi, grape], 
[apple, banana, kiwi, grape], 
[strawberry, kiwi, grape], 
[apple, strawberry, kiwi, grape], 
[banana, strawberry, kiwi, grape], 
[apple, banana, strawberry, kiwi, grape]]

Answer 2

This should do what you asked for:

import java.util.*;

public class Main {
    public static String[] fruits = {"apple", "banana", "strawberry", "kiwi", "grape"};
    
    public static void combs(Deque<String> curr, int index){
        if(index == fruits.length){
            if(curr.size() == 0) return;
            System.out.print("[");
            for (Iterator itr = curr.iterator(); itr.hasNext();) {
                System.out.print("\"" + itr.next() + "\""); 
                if(itr.hasNext()) System.out.print(", ");
            }
            System.out.println("]");
        
        }
        else{
            curr.addLast(fruits[index]);
            combs(curr, index + 1);
            curr.removeLast();
            combs(curr, index + 1);
        }
    }
    
    public static void main(String[] args) {
        combs(new ArrayDeque<String>(), 0);
    }
}

OUTPUT:

["apple", "banana", "strawberry", "kiwi", "grape"]
["apple", "banana", "strawberry", "kiwi"]
["apple", "banana", "strawberry", "grape"]
["apple", "banana", "strawberry"]
["apple", "banana", "kiwi", "grape"]
["apple", "banana", "kiwi"]
["apple", "banana", "grape"]
["apple", "banana"]
["apple", "strawberry", "kiwi", "grape"]
["apple", "strawberry", "kiwi"]
["apple", "strawberry", "grape"]
["apple", "strawberry"]
["apple", "kiwi", "grape"]
["apple", "kiwi"]
["apple", "grape"]
["apple"]
["banana", "strawberry", "kiwi", "grape"]
["banana", "strawberry", "kiwi"]
["banana", "strawberry", "grape"]
["banana", "strawberry"]
["banana", "kiwi", "grape"]
["banana", "kiwi"]
["banana", "grape"]
["banana"]
["strawberry", "kiwi", "grape"]
["strawberry", "kiwi"]
["strawberry", "grape"]
["strawberry"]
["kiwi", "grape"]
["kiwi"]
["grape"]

Answer 3

import java.util.ArrayList;
import java.util.List;

/**
 *
 *
 *
 *
 *
 *
 * @author shikai.liu
 * @version 1.0
 * @since JDK1.7
 */
public class Teaaa {

    public static void main(String[]args){
        String[] fruits = { "apple", "banana", "strawberry", "kiwi", "grape" };
        List<List<String>> allList = new ArrayList<>();
        List<String> list = new ArrayList<>();
        list.add("banana");
        allList.add(new ArrayList<>(list));
        for (int j = 0; j < fruits.length; j++) {
            list.clear();
            list.add("banana");
            if (!fruits[j].equals("banana"))
                list.add(fruits[j]);
            for (int i = j + 1; i < fruits.length; i++) {
                if (!fruits[i].equals("banana"))
                    list.add(fruits[i]);
                allList.add(new ArrayList<String>(list));
            }
        }
        System.out.println(allList);
    }
}

the output is : [[banana], [banana, apple], [banana, apple, strawberry], [banana, apple, strawberry, kiwi], [banana, apple, strawberry, kiwi, grape], [banana, strawberry], [banana, strawberry, kiwi], [banana, strawberry, kiwi, grape], [banana, strawberry, kiwi], [banana, strawberry, kiwi, grape], [banana, kiwi, grape]]

Answer 4

Why reinvent the wheel. If you are allow to use Guava you can take advantage of its Sets class and Sets.combinations(Set<E> set, int size) method:

String[] fruits = {"apple", "banana", "strawberry", "kiwi", "grape"};

Set<String> set = Set.of(fruits);

List<List<String>> combinations = IntStream.rangeClosed(1, set.size()).boxed()
        .flatMap(i -> Sets.combinations(set, i).stream().map(List::copyOf))
        .collect(Collectors.toList());

combinations.forEach(System.out::println);

Output

[banana]
[apple]
[grape]
[kiwi]
[strawberry]
[banana, apple]
[banana, grape]
[apple, grape]
[banana, kiwi]
[apple, kiwi]
[grape, kiwi]
[banana, strawberry]
[apple, strawberry]
[grape, strawberry]
[kiwi, strawberry]
[banana, apple, grape]
[banana, apple, kiwi]
[banana, grape, kiwi]
[apple, grape, kiwi]
[banana, apple, strawberry]
[banana, grape, strawberry]
[apple, grape, strawberry]
[banana, kiwi, strawberry]
[apple, kiwi, strawberry]
[grape, kiwi, strawberry]
[banana, apple, grape, kiwi]
[banana, apple, grape, strawberry]
[banana, apple, kiwi, strawberry]
[banana, grape, kiwi, strawberry]
[apple, grape, kiwi, strawberry]
[banana, apple, grape, kiwi, strawberry]

Answer 5

Run this :

class Combination {
    static void permutingArray(List<String> list, int element) {
        for (int i = element; i < list.size(); i++) {
            java.util.Collections.swap(list, i, element);
            permutingArray(list, element + 1);
            java.util.Collections.swap(list, element, i);
        }
        if (element == list.size() - 1) {
            System.out.println(java.util.Arrays.toString(list.toArray()));
        }
    }

    public static void main(String[] args) {
        String[] fruits = {"apple", "banana", "strawberry", "kiwi", "grape"};
        Combination
        .permutingArray(java.util.Arrays.asList(fruits), 0);
    }
}

Output :

[apple, banana, strawberry, kiwi, grape]
[apple, banana, strawberry, grape, kiwi]
[apple, banana, kiwi, strawberry, grape]
[apple, banana, kiwi, grape, strawberry]
[apple, banana, grape, kiwi, strawberry]
[apple, banana, grape, strawberry, kiwi]
[apple, strawberry, banana, kiwi, grape]
[apple, strawberry, banana, grape, kiwi]
[apple, strawberry, kiwi, banana, grape]
[apple, strawberry, kiwi, grape, banana]
[apple, strawberry, grape, kiwi, banana]
[apple, strawberry, grape, banana, kiwi]
[apple, kiwi, strawberry, banana, grape]
[apple, kiwi, strawberry, grape, banana]
[apple, kiwi, banana, strawberry, grape]
[apple, kiwi, banana, grape, strawberry]
[apple, kiwi, grape, banana, strawberry]
[apple, kiwi, grape, strawberry, banana]
[apple, grape, strawberry, kiwi, banana]
[apple, grape, strawberry, banana, kiwi]
[apple, grape, kiwi, strawberry, banana]
[apple, grape, kiwi, banana, strawberry]
[apple, grape, banana, kiwi, strawberry]
[apple, grape, banana, strawberry, kiwi]
[banana, apple, strawberry, kiwi, grape]
[banana, apple, strawberry, grape, kiwi]
[banana, apple, kiwi, strawberry, grape]
[banana, apple, kiwi, grape, strawberry]
[banana, apple, grape, kiwi, strawberry]
[banana, apple, grape, strawberry, kiwi]
[banana, strawberry, apple, kiwi, grape]
[banana, strawberry, apple, grape, kiwi]
[banana, strawberry, kiwi, apple, grape]
[banana, strawberry, kiwi, grape, apple]
[banana, strawberry, grape, kiwi, apple]
[banana, strawberry, grape, apple, kiwi]
[banana, kiwi, strawberry, apple, grape]
[banana, kiwi, strawberry, grape, apple]
[banana, kiwi, apple, strawberry, grape]
[banana, kiwi, apple, grape, strawberry]
[banana, kiwi, grape, apple, strawberry]
[banana, kiwi, grape, strawberry, apple]
[banana, grape, strawberry, kiwi, apple]
[banana, grape, strawberry, apple, kiwi]
[banana, grape, kiwi, strawberry, apple]
[banana, grape, kiwi, apple, strawberry]
[banana, grape, apple, kiwi, strawberry]
[banana, grape, apple, strawberry, kiwi]
[strawberry, banana, apple, kiwi, grape]
[strawberry, banana, apple, grape, kiwi]
[strawberry, banana, kiwi, apple, grape]
[strawberry, banana, kiwi, grape, apple]
[strawberry, banana, grape, kiwi, apple]
[strawberry, banana, grape, apple, kiwi]
[strawberry, apple, banana, kiwi, grape]
[strawberry, apple, banana, grape, kiwi]
[strawberry, apple, kiwi, banana, grape]
[strawberry, apple, kiwi, grape, banana]
[strawberry, apple, grape, kiwi, banana]
[strawberry, apple, grape, banana, kiwi]
[strawberry, kiwi, apple, banana, grape]
[strawberry, kiwi, apple, grape, banana]
[strawberry, kiwi, banana, apple, grape]
[strawberry, kiwi, banana, grape, apple]
[strawberry, kiwi, grape, banana, apple]
[strawberry, kiwi, grape, apple, banana]
[strawberry, grape, apple, kiwi, banana]
[strawberry, grape, apple, banana, kiwi]
[strawberry, grape, kiwi, apple, banana]
[strawberry, grape, kiwi, banana, apple]
[strawberry, grape, banana, kiwi, apple]
[strawberry, grape, banana, apple, kiwi]
[kiwi, banana, strawberry, apple, grape]
[kiwi, banana, strawberry, grape, apple]
[kiwi, banana, apple, strawberry, grape]
[kiwi, banana, apple, grape, strawberry]
[kiwi, banana, grape, apple, strawberry]
[kiwi, banana, grape, strawberry, apple]
[kiwi, strawberry, banana, apple, grape]
[kiwi, strawberry, banana, grape, apple]
[kiwi, strawberry, apple, banana, grape]
[kiwi, strawberry, apple, grape, banana]
[kiwi, strawberry, grape, apple, banana]
[kiwi, strawberry, grape, banana, apple]
[kiwi, apple, strawberry, banana, grape]
[kiwi, apple, strawberry, grape, banana]
[kiwi, apple, banana, strawberry, grape]
[kiwi, apple, banana, grape, strawberry]
[kiwi, apple, grape, banana, strawberry]
[kiwi, apple, grape, strawberry, banana]
[kiwi, grape, strawberry, apple, banana]
[kiwi, grape, strawberry, banana, apple]
[kiwi, grape, apple, strawberry, banana]
[kiwi, grape, apple, banana, strawberry]
[kiwi, grape, banana, apple, strawberry]
[kiwi, grape, banana, strawberry, apple]
[grape, banana, strawberry, kiwi, apple]
[grape, banana, strawberry, apple, kiwi]
[grape, banana, kiwi, strawberry, apple]
[grape, banana, kiwi, apple, strawberry]
[grape, banana, apple, kiwi, strawberry]
[grape, banana, apple, strawberry, kiwi]
[grape, strawberry, banana, kiwi, apple]
[grape, strawberry, banana, apple, kiwi]
[grape, strawberry, kiwi, banana, apple]
[grape, strawberry, kiwi, apple, banana]
[grape, strawberry, apple, kiwi, banana]
[grape, strawberry, apple, banana, kiwi]
[grape, kiwi, strawberry, banana, apple]
[grape, kiwi, strawberry, apple, banana]
[grape, kiwi, banana, strawberry, apple]
[grape, kiwi, banana, apple, strawberry]
[grape, kiwi, apple, banana, strawberry]
[grape, kiwi, apple, strawberry, banana]
[grape, apple, strawberry, kiwi, banana]
[grape, apple, strawberry, banana, kiwi]
[grape, apple, kiwi, strawberry, banana]
[grape, apple, kiwi, banana, strawberry]
[grape, apple, banana, kiwi, strawberry]
[grape, apple, banana, strawberry, kiwi]