Created
October 26, 2018 10:46
-
-
Save jiahaoliuliu/4220f41d5b123d831e66b17b640b9c6d to your computer and use it in GitHub Desktop.
Permutation using recursive on Java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package com.jiahaoliuliu.tools; | |
| import java.util.ArrayList; | |
| import java.util.List; | |
| import java.util.stream.Collectors; | |
| public class Permutations<T> { | |
| private List<List<T>> generatePermutations(List<T> seedLists) { | |
| return generatePermutations(new ArrayList<>(), seedLists); | |
| } | |
| private List<List<T>> generatePermutations( | |
| List<T> existingPermutations, List<T> remainSeeds) { | |
| List<List<T>> result = new ArrayList<>(); | |
| // A simple optimization | |
| if (!existingPermutations.isEmpty()) { | |
| // Safe copy | |
| result.add(new ArrayList<>(existingPermutations)); | |
| } | |
| // Stop condition | |
| if (remainSeeds.isEmpty()) { | |
| return result; | |
| } | |
| for (int i = 0; i < remainSeeds.size(); i++) { | |
| List<T> existingPermutationsCopy = new ArrayList<>(existingPermutations); | |
| existingPermutationsCopy.add(remainSeeds.get(i)); | |
| result.addAll( | |
| generatePermutations( | |
| existingPermutationsCopy, | |
| remainSeeds.subList(i+1, remainSeeds.size()))); | |
| } | |
| return result; | |
| } | |
| public static void main(String... args) { | |
| test1(); | |
| test2(); | |
| test3(); | |
| } | |
| private static void test1() { | |
| Permutations<Character> permutations = new Permutations(); | |
| String word = "a"; | |
| List<Character> characterList = word.chars() | |
| .mapToObj(i -> (char)i).collect(Collectors.toList()); | |
| // [a] | |
| System.out.println(permutations.generatePermutations(characterList)); | |
| } | |
| private static void test2() { | |
| Permutations<Character> permutations = new Permutations(); | |
| String word = "ab"; | |
| List<Character> characterList = word.chars() | |
| .mapToObj(i -> (char)i).collect(Collectors.toList()); | |
| // [a, ab, b] | |
| System.out.println(permutations.generatePermutations(characterList)); | |
| } | |
| private static void test3() { | |
| Permutations<Character> permutations = new Permutations(); | |
| String word = "abc"; | |
| List<Character> characterList = word.chars() | |
| .mapToObj(i -> (char)i).collect(Collectors.toList()); | |
| //[a, ab, abc, ac, b, bc, c] | |
| System.out.println(permutations.generatePermutations(characterList)); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment