java - 如何随机排列没有相邻相等元素的字符串

Question

所以，我有一个像“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;
    }

当我试图通过该算法随机生成它时，我被卡住了。我想要的结果是如上所述的动态输出。谢谢

Answer 1

假设您想要平均分配有效排列:如果您不关心内存或运行时的复杂性，您可以生成字符串的所有排列 ( Generating all permutations of a given string )，然后删除所有具有相邻相同字母的字符串，最后从该列表中随机选择一个。

如果您确实关心优化内存或运行时，请参阅链接的类似问题。

如果您不需要均等分布，但仍然有机会找到任何有效排列，则可以使用其他一些方法:

• 您可以通过从剩余的字母中随机挑选(类似于您所做的)来构建字符串，并在遇到死胡同时回溯(没有有效的字母可供挑选)。参见 Python permutation using backtracking
• 你可以创建一个字符串，从输入中随机选择字母而不关心相邻的重复，然后反复交换-洗牌(参见堆的算法)这个随机起点直到结果匹配你的条件(或者直到你回来开始)。

回溯解决方案

在这里，我选择了一个随机的 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，例如 50% 的情况下为“acabababababa”。但是它使用有限的内存并且可能在计算所有排列之前完成，并且它有点类似于您的方法。