How to randomly permutate string without adjacent equal elements

Question

So, I have an example string like "aaabbbc", i would like to shuffle it randomly but no two consecutive letters should be same in the result. The output should be "abababc" or "cbababa" or "abacbab" etc.

I've tried a code using PriorityQueue, its solve the problem, but only one way not randomly generate many ways to shuffle my string with no two consecutive. Below is code that i've used.

    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;
    }

I am stuck when trying to make it randomly by that algorithm. The result i wanted is dynamic output like i described above. Thanks

Please describe your requirements. In example, do you need to generate random strings based on a combination of letters that matches a seed string? If not, you can use guid. — Ali Reza Dehdar, May 29 '19 at 08:22
@NicholasK if you have another technique, please refer me. But in this case i already had a string to generate with no two consequtive. — madqori, May 29 '19 at 08:51
@AliRezaDehdar In this case, i already had a string and i would to make it no two consecutive. I've done with it, but i need to make it dynamic. I know guid, but that's not what im looking for. thanks — madqori, May 29 '19 at 08:52
Related: https://stackoverflow.com/questions/5899274/shuffle-list-with-some-conditions, https://stackoverflow.com/questions/25285792/generate-all-permutations-of-a-list-without-adjacent-equal-elements — tkruse, May 29 '19 at 08:54
Also: https://stackoverflow.com/questions/39170398/is-there-a-way-to-shuffle-an-array-so-that-no-two-consecutive-values-are-the-sam — tkruse, May 29 '19 at 09:03
Randomly shuffling without repetition is a difficult problem. See the similar questions to which I linked. There are different solution approaches, but I think the one you have started cannot be extended to work. So I would suggest you close this question, and start over after reading on the solutions in the related answers. — tkruse, May 29 '19 at 09:07
Be careful. The problem may not have a solution: "aaaaaaaabc" for instance. Whatever algorithm you use needs to first check if a solution exists, otherwise you might be in danger of a non-terminating infinite loop. — rossum, May 29 '19 at 14:47

tkruse · Accepted Answer · 2019-06-10T10:41:14.740

Assuming you want an equal distribution of the valid permutations: If you do not care about memory or runtime complexity, you can generate all permutations of the string (Generating all permutations of a given string), then remove all Strings which have adjacent same letters, and finally pick a random one from that list.

If you do care about optimizing memory or runtime, see the similar questions linked.

Some other approaches if you do not need an equal distribution, but still a chance for any valid permutation to be found:

You can build up the string by randomly picking from the remaining letters (similar as to what you did), and backtracking when you hit a dead end (no valid letter left to pick). See Python permutation using backtracking
You can make a string where you pick random letters from the input without caring about adjacent repetitions, and then swap-shuffle (see Heap's algorithm) this random starting point iteratively until the result matches your condition (or until you're back to the start).

Backtracking solution

Here I pick a random nextChar, and try to build a random String that does not start with that char. If that fails, try another one. By recursion, this eventually tries out all combinations in a random order, until a valid one is found.

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;
}

This solution will more likely find results where rare characters are used in the beginning of the result, so the distribution would not be equal. As an example input "aaaaaaabbbbbc" will have c more often on the left than on the right, like "acabababababa" in 50% of cases. But it uses limited memory and may complete before computing all permutations, and it is somewhat similar to your approach.

How to randomly permutate string without adjacent equal elements

1 Answers1

Backtracking solution