Christian - 11 months ago 42

Java Question

Let's say I have

`ABCDEF`

- 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.

`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 Source

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
```