Christian - 1 year ago 54
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));
}
}
``````

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<>();

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
} 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) {
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