The challenge
In this challenge, you have to create all permutations of an input string and remove duplicates if present. This means you have to shuffle all letters from the input in all possible orders.
Examples:
Permutations.singlePermutations("a") // ["a"]
Permutations.singlePermutations("ab") // ["ab", "ba"]
Permutations.singlePermutations("aabb") // ["aabb","abab","abba","baab","baba","bbaa"]
The order of the permutations doesn’t matter.
The solution in Java code
Option 1:
import static java.util.Collections.singletonList;
import static java.util.stream.Collectors.toList;
import java.util.List;
class Permutations {
public static List<String> singlePermutations(final String s) {
return permute("", s);
}
private static List<String> permute(final String prefix, final String s) {
return s.isEmpty()
? singletonList(prefix)
: s.chars()
.distinct()
.mapToObj(i -> (char) i)
.map(c -> permute(prefix + c, takeOut(s, c)))
.flatMap(List::stream)
.collect(toList());
}
static String takeOut(final String s, final char c) {
final int i = s.indexOf(c);
return s.substring(0, i) + s.substring(i + 1);
}
}
Option 2:
import java.util.*;
class Permutations {
public static List<String> singlePermutations(String s) {
return permutate("",s,new ArrayList<String>());
}
public static List<String> permutate(String permute, String s, List<String> listed) {
if (s.isEmpty() && !listed.contains(permute + s)) {
listed.add(permute + s);
} else {
for (int i = 0; i < s.length(); i++) {
permutate(permute + s.charAt(i), s.substring(0,i) + s.substring(i+1,s.length()), listed);
}
}
return listed;
}
}
Option 3:
import java.util.ArrayList;
import java.util.List;
import java.util.HashSet;
class Permutations {
static void fill(String s,String output,HashSet<String> h) {
if(s.length()==0) h.add(output);
for(int i=0;i<s.length();i++){
char c= s.charAt(i);
String ns=s.substring(0, i)+s.substring(i+1);
fill(ns, output+c, h);
}
}
public static List<String> singlePermutations(String s){
HashSet<String> h = new HashSet<String>();
fill(s,"",h);
return new ArrayList<String>(h);
}
}
Test cases to validate our solution
import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;
import java.util.*;
import java.util.stream.*;
public class SolutionTest {
@Test public void example1() {
assertEquals( new ArrayList<String>(Arrays.asList("a")),
Permutations.singlePermutations("a").stream().sorted().collect(Collectors.toList()) );
}
@Test public void example2() {
assertEquals( new ArrayList<String>(Arrays.asList("ab","ba")),
Permutations.singlePermutations("ab").stream().sorted().collect(Collectors.toList()) );
}
@Test public void example3() {
assertEquals( new ArrayList<String>(Arrays.asList("aabb", "abab", "abba", "baab", "baba", "bbaa")),
Permutations.singlePermutations("aabb").stream().sorted().collect(Collectors.toList()) );
}
}
