Предполагая, что вы хотите равномерное распределение действительных перестановок:
Если вас не волнует память или сложность среды выполнения, вы можете сгенерировать все перестановки строки ( Генерация всех перестановок данной строки ), затем удалить все строки, имеющие соседние одинаковые буквы, и, наконец, выбрать случайный один из этого списка.
Если вы заботитесь об оптимизации памяти или времени выполнения, см. Похожие вопросы, связанные.
Некоторые другие подходы, если вам не нужно равное распределение, но все же есть шанс найти любую действительную перестановку:
- Вы можете создать строку путем случайного выбора из оставшихся букв (аналогично тому, что вы сделали) и возврата , когда вы зашли в тупик (не осталось действительной буквы). См. Перестановка Python с использованием обратного отслеживания
- Вы можете создать строку, в которой вы выбираете случайные буквы из входных данных, не заботясь о смежных повторениях, а затем итерационно меняйте местами случайную начальную точку swap-shuffle (см. Алгоритм Heap), пока результат не будет соответствовать вашему состоянию (или пока вы не вернетесь). к началу).
Решение по возврату
Здесь я выбираю случайный nextChar и пытаюсь создать случайную строку, которая не начинается с этого символа. Если это не помогло, попробуйте другой. По рекурсии это в конечном итоге пробует все комбинации в случайном порядке, пока не будет найдена действительная.
private static final Random RANDOM = new Random();
public static void main(String[] args) {
System.out.println(randomPerm("aaabcc"));
}
public static String randomPerm(String str) {
Map<Character, Long> counts = str
.chars()
.mapToObj(c -> (char) c)
.collect(groupingBy(Function.identity(), Collectors.counting()));
return restPerm(null, counts);
}
public static String restPerm(Character previous, Map<Character, Long> leftover) {
List<Character> leftKeys = new ArrayList<>(leftover.keySet());
while (!leftKeys.isEmpty()) {
Character nextChar = leftKeys.get(RANDOM.nextInt(leftKeys.size()));
leftKeys.remove(nextChar);
if (nextChar.equals(previous) || leftover.get(nextChar) == 0) {
continue; // invalid next char
}
// modify map in place, reduce count by one
Long count = leftover.compute(nextChar, (ch, co) -> co - 1);
if (leftover.values().stream().noneMatch(c -> c > 0)) {
return nextChar.toString(); // last char to use
}
String rest = restPerm(nextChar, leftover); // recurse
if (rest != null) {
return nextChar + rest; // solution found
}
leftover.put(nextChar, count + 1);
}
return null;
}
Это решение, скорее всего, найдет результаты, где в начале результата используются редкие символы, поэтому распределение не будет равным. В качестве примера вход «aaaaaaabbbbbc» будет иметь c чаще слева, чем справа, как «acabababababa» в 50% случаев. Но он использует ограниченную память и может завершить работу перед вычислением всех перестановок, и это несколько похоже на ваш подход.