Combinations and Permutations

Author: Jacob Park

Generating Combinations ($O(2^n)$)

In [1]:
package recursive_algorithms.generating_combinations;

import java.util.*;

class GeneratingCombinations {

    public static void generateCombinations(
            List<Integer> list, 
            List<List<Integer>> results, 
            Deque<Integer> buffer) {
        results.add(new ArrayList<>(buffer));
        
        for (int index = 0; index < list.size(); index++) {
            final List<Integer> tailList = list.subList(index + 1, list.size());
            
            buffer.addLast(list.get(index));
            generateCombinations(tailList, results, buffer);
            buffer.removeLast();
        }
    }
    
}
Out[1]:
recursive_algorithms.generating_combinations.GeneratingCombinations
In [2]:
package recursive_algorithms.generating_combinations;

import java.util.*;

final List<Integer> list = new ArrayList(Arrays.asList(0, 1, 2));
final List<List<Integer>> results = new ArrayList<>();
final Deque<Integer> buffer = new ArrayDeque<>();

GeneratingCombinations.generateCombinations(list, results, buffer);

results.forEach(combination -> {
    System.out.println(combination.toString());
});

[]
[0]
[0, 1]
[0, 1, 2]
[0, 2]
[1]
[1, 2]
[2]
Out[2]:
null

Generating Permutations ($O(n!)$)

In [3]:
package recursive_algorithms.generating_permutations;

import java.util.*;

class GeneratingPermutations {

    public static void generatePermutations(
            List<Integer> list, 
            List<List<Integer>> results, 
            Deque<Integer> buffer) {
        if (list.size() == 0) {
            results.add(new ArrayList<>(buffer));
            return;
        }
        
        for (int index = 0; index < list.size(); index++) {
            final List<Integer> splicedList = new ArrayList<>(list);
            splicedList.remove(index);
            
            buffer.addLast(list.get(index));
            generatePermutations(splicedList, results, buffer);
            buffer.removeLast();
        }
    }
    
}
Out[3]:
recursive_algorithms.generating_permutations.GeneratingPermutations
In [4]:
package recursive_algorithms.generating_permutations;

import java.util.*;

final List<Integer> list = new ArrayList(Arrays.asList(0, 1, 2));
final List<List<Integer>> results = new ArrayList<>();
final Deque<Integer> buffer = new ArrayDeque<>();

GeneratingPermutations.generatePermutations(list, results, buffer);

results.forEach(permutation -> {
    System.out.println(permutation.toString());
});

[0, 1, 2]
[0, 2, 1]
[1, 0, 2]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]
Out[4]:
null

Generating k-Combinations

In [5]:
package recursive_algorithms.generating_combinations_k;

import java.util.*;

class GeneratingCombinationsK {
    
    public static void generateCombinationsK(
            List<Integer> list, 
            List<List<Integer>> results, 
            Deque<Integer> buffer,
            int k) {
        if (buffer.size() == k) {
            results.add(new ArrayList<>(buffer));
            return;
        }
        
        for (int index = 0; index < list.size(); index++) {
            final List<Integer> tailList = list.subList(index + 1, list.size());
            
            buffer.addLast(list.get(index));
            generateCombinationsK(tailList, results, buffer, k);
            buffer.removeLast();
        }
    }
    
}
Out[5]:
recursive_algorithms.generating_combinations_k.GeneratingCombinationsK
In [6]:
package recursive_algorithms.generating_combinations_k;

import java.util.*;

final List<Integer> list = new ArrayList(Arrays.asList(0, 1, 2));
final List<List<Integer>> results = new ArrayList<>();
final Deque<Integer> buffer = new ArrayDeque<>();

GeneratingCombinationsK.generateCombinationsK(list, results, buffer, 2);

results.forEach(combination -> {
    System.out.println(combination.toString());
});

[0, 1]
[0, 2]
[1, 2]
Out[6]:
null

Generating k-Permutations

In [7]:
package recursive_algorithms.generating_permutations_k;

import java.util.*;

class GeneratingPermutationsK {
    
    public static void generatePermutationsK(
            List<Integer> list, 
            List<List<Integer>> results, 
            Deque<Integer> buffer,
            int k) {
        if (buffer.size() == k) {
            results.add(new ArrayList<>(buffer));
            return;
        }
        
        for (int index = 0; index < list.size(); index++) {
            final List<Integer> splicedList = new ArrayList<>(list);
            splicedList.remove(index);

            buffer.addLast(list.get(index));
            generatePermutationsK(splicedList, results, buffer, k);
            buffer.removeLast();
        }
    }
    
}
Out[7]:
recursive_algorithms.generating_permutations_k.GeneratingPermutationsK
In [8]:
package recursive_algorithms.generating_permutations_k;

import java.util.*;

final List<Integer> list = new ArrayList<>(Arrays.asList(0, 1, 2));
final List<List<Integer>> results = new ArrayList<>();
final Deque<Integer> buffer = new ArrayDeque<>();

GeneratingPermutationsK.generatePermutationsK(list, results, buffer, 2);

results.forEach(permutation -> {
    System.out.println(permutation.toString());
});

[0, 1]
[0, 2]
[1, 0]
[1, 2]
[2, 0]
[2, 1]
Out[8]:
null

Generating Unique Combinations

In [9]:
package recursive_algorithms.generating_unique_combinations;

import java.util.*;

public class GeneratingUniqueCombinations {

    public static List<List<Integer>> generateUniqueCombinations(List<Integer> list) {
        final List<List<Integer>> results = new LinkedList<>();
        final Deque<Integer> buffer = new ArrayDeque<>();

        Collections.sort(list);

        generateUniqueCombinations(list, results, buffer);

        return results;
    }

    private static void generateUniqueCombinations(
            List<Integer> list,
            List<List<Integer>> results,
            Deque<Integer> buffer) {
        results.add(new ArrayList<>(buffer));

        for (int index = 0; index < list.size(); index++) {
            if (index > 0 && list.get(index) == list.get(index - 1)) {
                continue;
            }

            final List<Integer> tailList = list.subList(index + 1, list.size());

            buffer.addLast(list.get(index));
            generateUniqueCombinations(tailList, results, buffer);
            buffer.removeLast();
        }
    }
    
}
Out[9]:
recursive_algorithms.generating_unique_combinations.GeneratingUniqueCombinations
In [10]:
package recursive_algorithms.generating_unique_combinations;

import java.util.*;

final List<Integer> list = new ArrayList(Arrays.asList(0, 0, 1, 2));

final List<List<Integer>> results =
    GeneratingUniqueCombinations.generateUniqueCombinations(list);

results.forEach(combination -> {
    System.out.println(combination.toString());
});

[]
[0]
[0, 0]
[0, 0, 1]
[0, 0, 1, 2]
[0, 0, 2]
[0, 1]
[0, 1, 2]
[0, 2]
[1]
[1, 2]
[2]
Out[10]:
null

Generating Unique Permutations

In [11]:
package recursive_algorithms.generating_unique_permutations;

import java.util.*;

public class GeneratingUniquePermutations {

    public static List<List<Integer>> generateUniquePermutations(List<Integer> list) {
        final List<List<Integer>> results = new LinkedList<>();
        final Deque<Integer> buffer = new ArrayDeque<>();

        Collections.sort(list);

        generateUniquePermutations(list, results, buffer);

        return results;
    }

    private static void generateUniquePermutations(
            List<Integer> list,
            List<List<Integer>> results,
            Deque<Integer> buffer) {
        if (list.size() == 0) {
            results.add(new ArrayList<>(buffer));
            return;
        }

        for (int index = 0; index < list.size(); index++) {
            if (index > 0 && list.get(index) == list.get(index - 1)) {
                continue;
            }

            final List<Integer> splicedList = new ArrayList<>(list);
            splicedList.remove(index);

            buffer.addLast(list.get(index));
            generateUniquePermutations(splicedList, results, buffer);
            buffer.removeLast();
        }
    }

}
Out[11]:
recursive_algorithms.generating_unique_permutations.GeneratingUniquePermutations
In [12]:
package recursive_algorithms.generating_unique_permutations;

import java.util.*;

final List<Integer> list = new ArrayList(Arrays.asList(0, 0, 1, 2));

final List<List<Integer>> results =
    GeneratingUniquePermutations.generateUniquePermutations(list);

results.forEach(permutation -> {
    System.out.println(permutation.toString());
});

[0, 0, 1, 2]
[0, 0, 2, 1]
[0, 1, 0, 2]
[0, 1, 2, 0]
[0, 2, 0, 1]
[0, 2, 1, 0]
[1, 0, 0, 2]
[1, 0, 2, 0]
[1, 2, 0, 0]
[2, 0, 0, 1]
[2, 0, 1, 0]
[2, 1, 0, 0]
Out[12]:
null