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

Question

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

Hmm, let's do a rough estimate. Given a random perm on n letters, the probability that two particular letters are next to one another is 2(n-1)/(n(n-1)) = 2/n. Since we have n-1 of these constraints, a hand-wavy independence assumption says that a random perm is valid with probability about (1-2/n)^(n-1) ≈ 1/e^2 ≈ 0.135 for large n. If this is a reasonable estimate, then you can't hope for large gains -- there are too many valid perms (one in seven or eight)! — David Eisenstat, Nov 12 '16 at 16:27
Hmm, here is the actual equation used to derive how many such permutations there are: "The probability that neighbors remain neighbors after random rearrangements", Amer. Math. Monthly 87 (1980), 122-124 — , Nov 12 '16 at 16:54
Same formula. Good to know there's a formal derivation (but I'm not at all surprised). — David Eisenstat, Nov 12 '16 at 16:58

Kaidul · Answer 1 · 2016-11-12T17:32:02.230

The typical O(n!) pseudo-code of algorithm to generate all permutations of a string of length n:

function permute(String s, int left, int right)
{
   if (left == right)
     print s
   else
   {
       for (int i = left; i <= right; i++)
       {
          swap(s[left], s[i]);
          permute(s, left + 1, right);
          swap(s[left], s[i]); // backtrack
       }
   }
}

The corresponding recursion tree for string ABC looks like [image taken from internet]:

Just before swapping, check whether you can swap satisfying the given constraint (checking new previous and new next characters of both s[left] and s[i]). This will cut many branches off of the recursion tree too.

Can you please add a concrete example? It would help make the answer much more whole. Thank you! :) — , Nov 12 '16 at 19:52

score 0 · Accepted Answer · answered Nov 12 '16 at 20:37

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

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

2 Answers2