Использование операций Set для моделирования «выборов в зависимости от других выборов» намного проще для понимания зависимых перестановок
При зависимой перестановке доступные варианты выбора уменьшаются, поскольку позиции заполняются выбранными символами слева направо. Терминальное условие для рекурсивных вызовов состоит в том, чтобы проверить, является ли набор доступных выборов пустым. Когда условие терминала выполнено, перестановка завершена, и она сохраняется в списке «результатов».
public static List<String> stringPermutation(String s) {
List<String> results = new ArrayList<>();
Set<Character> charSet = s.chars().mapToObj(m -> (char) m).collect(Collectors.toSet());
stringPermutation(charSet, "", results);
return results;
}
private static void stringPermutation(Set<Character> charSet,
String prefix, List<String> results) {
if (charSet.isEmpty()) {
results.add(prefix);
return;
}
for (Character c : charSet) {
Set<Character> newSet = new HashSet<>(charSet);
newSet.remove(c);
stringPermutation(newSet, prefix + c, results);
}
}
Код можно обобщить, чтобы найти перестановки для набора объектов. В этом случае я использую набор цветов.
public enum Color{
ORANGE,RED,BULE,GREEN,YELLOW;
}
public static List<List<Color>> colorPermutation(Set<Color> colors) {
List<List<Color>> results = new ArrayList<>();
List<Color> prefix = new ArrayList<>();
permutation(colors, prefix, results);
return results;
}
private static <T> void permutation(Set<T> set, List<T> prefix, List<List<T>> results) {
if (set.isEmpty()) {
results.add(prefix);
return;
}
for (T t : set) {
Set<T> newSet = new HashSet<>(set);
List<T> newPrefix = new ArrayList<>(prefix);
newSet.remove(t);
newPrefix.add(t);
permutation(newSet, newPrefix, results);
}
}
Код для испытаний.
public static void main(String[] args) {
List<String> stringPerm = stringPermutation("abcde");
System.out.println("# of permutations:" + stringPerm.size());
stringPerm.stream().forEach(e -> System.out.println(e));
Set<Color> colorSet = Arrays.stream(Color.values()).collect(Collectors.toSet());
List<List<Color>> colorPerm = colorPermutation(colorSet);
System.out.println("# of permutations:" + colorPerm.size());
colorPerm.stream().forEach(e -> System.out.println(e));
}