Как случайным образом переставить строку без соседних равных элементов
Итак, у меня есть пример строки, такой как «aaabbbc», я хотел бы перетасовать ее случайным образом, но в результате не должно быть двух последовательных букв. Вывод должен быть "abababc" или "cbababa" или "abacbab" и т.д.
Я пробовал код, использующий PriorityQueue, он решает проблему, но только один способ не случайным образом генерировать множество способов перетасовать мою строку без двух последовательных. Ниже приведен код, который я использовал.
int n = str.length();
int[] count = new int[MAX_CHAR];
for (int i = 0; i < n; i++) {
count[str.charAt(i) - 'a']++;
}
PriorityQueue<Key> pq = new PriorityQueue<>(new KeyComparator());
for (char c = 'a'; c <= 'z'; c++) {
int val = c - 'a';
if (count[val] > 0) {
pq.add(new Key(count[val], c));
}
}
str = "";
Key prev = new Key(-1, '#');
while (pq.size() != 0) {
Key k = pq.peek();
pq.poll();
str = str + k.ch;
if (prev.freq > 0) {
pq.add(prev);
}
(k.freq)--;
prev = k;
}
if (n != str.length()) {
return "";
} else {
return str;
}
Я застрял, пытаясь сделать это случайным образом по этому алгоритму. Результат, который я хотел, - это динамический вывод, как я описал выше. Спасибо
Пожалуйста, опишите ваши требования. Например, вам нужно генерировать случайные строки на основе комбинации букв, которая соответствует исходной строке? Если нет, вы можете использовать guid.
@NicholasK, если у вас есть другая техника, пожалуйста, направьте меня. Но в этом случае у меня уже была строка для генерации без двух последовательных.
@AliRezaDehdar В этом случае у меня уже была строка, и я бы не стал делать ее двумя подряд. Я закончил с этим, но мне нужно сделать его динамичным. Я знаю гида, но это не то, что я ищу. Спасибо
Связанные: stackoverflow.com/questions/5899274/…, stackoverflow.com/questions/25285792/…
Также: stackoverflow.com/questions/39170398/…
Случайное перетасовывание без повторения — сложная задача. Смотрите похожие вопросы, на которые я ссылался. Существуют разные подходы к решению, но я думаю, что тот, который вы начали, не может быть расширен для работы. Поэтому я бы посоветовал вам закрыть этот вопрос и начать сначала, прочитав решения в соответствующих ответах.
Будь осторожен. Проблема может не иметь решения: например, «aaaaaaaabc». Какой бы алгоритм вы ни использовали, он должен сначала проверить, существует ли решение, иначе вы можете оказаться в опасности бесконечного бесконечного цикла.
Ответы 1
Предполагая, что вы хотите равное распределение допустимых перестановок: Если вас не волнует сложность памяти или времени выполнения, вы можете сгенерировать все перестановки строки (Генерация всех перестановок заданной строки), затем удалить все строки, которые имеют соседние одинаковые буквы, и, наконец, выбрать случайную из этого списка.
Если вы заботитесь об оптимизации памяти или времени выполнения, см. похожие вопросы по ссылке.
Некоторые другие подходы, если вам не нужно равное распределение, но все же есть шанс найти любую допустимую перестановку:
- Вы можете построить строку, выбирая случайным образом из оставшихся букв (аналогично тому, что вы делали) и отступление, когда вы зашли в тупик (не осталось подходящей буквы для выбора). См. Перестановка Python с использованием поиска с возвратом
- Вы можете создать строку, в которой вы выбираете случайные буквы из ввода, не заботясь о соседних повторениях, а затем перетасовываете местами (см. Алгоритм кучи) эту случайную начальную точку итеративно, пока результат не будет соответствовать вашему условию (или пока вы не вернетесь к началу ).
Решение для возврата
Здесь я выбираю случайный 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% случаев. Но он использует ограниченную память и может завершиться до вычисления всех перестановок, и это чем-то похоже на ваш подход.
Вам нужно Только использовать
PriorityQueue?