Christian Christian - 24 days ago 7
Java Question

Algorithm to generating all permutations of a string with no adjacent characters

Let's say I have

ABCDEF
. Then, there are 6! permutations of reordering that string. Now, I would like to only deal with the permutations in which there are no adjacent characters. That means, I want to look at all the permutations that satisfy these constraints:


  • B is not next to A or C

  • C is not next to B or D

  • D is not next to C or E

  • E is not next to D or F



My approach to this algorithm is the following pseudocode:

//generate all 6! permutations
//check all permutations and see where B is next to A || C
//remove all instances
//check all permutations and see where C is next to D
//remove all instances
//check all permutations and see where D is next to E
//remove all instances
//check all permutations and see where E is next to F
//remove all instances


However, these masking operations are becoming very inefficient and taking me much too long, especially if my string length is greater than 6. How can I do this more efficiently? I see these similar posts, 1, 2, and was hoping to extract some key ideas that might help me. However, this is also brute-force checking. I would like to actually generate only the unique patterns from the start and not have to generate everything and check one by one.

EDIT: Currently this is what I am using to generate all the permutations.

static String[] designs;
static int index;
protected static String[] generateDesigns(int lengthOfSequence, int numOfPermutations){
designs = new String[numOfPermutations];
StringBuilder str = new StringBuilder("1");
for(int i = 2; i <= lengthOfSequence; i++)
str.append(i);

genDesigns("", str.toString()); //genDesigns(6) = 123456 will be the unique characters
return designs;
}

//generate all permutations for lenOfSequence characters
protected static void genDesigns(String prefix, String data){
int n = data.length();
if (n == 0) designs[index++] = prefix;
else {
for (int i = 0; i < n; i++)
genDesigns(prefix + data.charAt(i), data.substring(0, i) + data.substring(i+1, n));
}
}

Answer

Here’s a fairly straightforward backtracking solution pruning the search before adding an adjacent character to the permutation.

public class PermutationsNoAdjacent {

    private char[] inputChars;
    private boolean[] inputUsed;
    private char[] outputChars;
    private List<String> permutations = new ArrayList<>();

    public PermutationsNoAdjacent(String inputString) {
        inputChars = inputString.toCharArray();
        inputUsed = new boolean[inputString.length()];
        outputChars = new char[inputString.length()];
    }

    private String[] generatePermutations() {
        tryFirst();
        return permutations.toArray(new String[permutations.size()]);
    }

    private void tryFirst() {
        for (int inputIndex = 0; inputIndex < inputChars.length; inputIndex++) {
            assert !inputUsed[inputIndex] : inputIndex;
            outputChars[0] = inputChars[inputIndex];
            inputUsed[inputIndex] = true;
            tryNext(inputIndex, 1);
            inputUsed[inputIndex] = false;
        }
    }

    private void tryNext(int previousInputIndex, int outputIndex) {
        if (outputIndex == outputChars.length) { // done
            permutations.add(new String(outputChars));
        } else {
            // avoid previousInputIndex and adjecent indices
            for (int inputIndex = 0; inputIndex < previousInputIndex - 1; inputIndex++) {
                if (!inputUsed[inputIndex]) {
                    outputChars[outputIndex] = inputChars[inputIndex];
                    inputUsed[inputIndex] = true;
                    tryNext(inputIndex, outputIndex + 1);
                    inputUsed[inputIndex] = false;
                }
            }
            for (int inputIndex = previousInputIndex + 2; inputIndex < inputChars.length; inputIndex++) {
                if (!inputUsed[inputIndex]) {
                    outputChars[outputIndex] = inputChars[inputIndex];
                    inputUsed[inputIndex] = true;
                    tryNext(inputIndex, outputIndex + 1);
                    inputUsed[inputIndex] = false;
                }
            }
        }
    }

    public static void main(String... args) {
        String[] permutations = new PermutationsNoAdjacent("ABCDEF").generatePermutations();
        for (String permutation : permutations) {
            System.out.println(permutation);
        }
    }

}

It prints 90 permutations of ABCDEF. I’ll just quote the beginning and the end:

ACEBDF
ACEBFD
ACFDBE
ADBECF
…
FDBEAC
FDBECA