Как случайным образом переставить строку без смежных равных элементов - PullRequest
Новая
       41

Как случайным образом переставить строку без смежных равных элементов

1 голос
/ 29 мая 2019

Итак, у меня есть пример строки типа «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;
    }

Я застрял при попытке сделать это случайным образом с помощью этого алгоритма.Результат, который я хотел, - это динамический вывод, как я описал выше.Спасибо

1 Ответ

1 голос
/ 29 мая 2019

Предполагая, что вы хотите равномерное распределение действительных перестановок: Если вас не волнует память или сложность среды выполнения, вы можете сгенерировать все перестановки строки ( Генерация всех перестановок данной строки ), затем удалить все строки, имеющие соседние одинаковые буквы, и, наконец, выбрать случайный один из этого списка.

Если вы заботитесь об оптимизации памяти или времени выполнения, см. Похожие вопросы, связанные.

Некоторые другие подходы, если вам не нужно равное распределение, но все же есть шанс найти любую действительную перестановку:

  • Вы можете создать строку путем случайного выбора из оставшихся букв (аналогично тому, что вы сделали) и возврата , когда вы зашли в тупик (не осталось действительной буквы). См. Перестановка 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% случаев. Но он использует ограниченную память и может завершить работу перед вычислением всех перестановок, и это несколько похоже на ваш подход.

...