java - Permutations with Restrictions

Question

In java, I'm trying to find a way to generate permutations based on restrictions. How can I generate the number of permutations (with the restrictions in mind), or at least know how many?

Edit: Simple Restriction Definition:

Possible values: A, B, C

Restrictions: a[0] == a[1] and a[0] != [2]

Example dataset:

AABA
AABB
AABC
AACA
AACB
AACC
BBAA
BBAB
BBAC
BBCA
BBCB
BBCC
CCAA
CCAB
CCAC
CCBA
CCBB
CCBC

I've tried generating all permutations and then subtracting the incompatible ones, this seems terribly inefficient. How can I do this efficiently? I only need to count the permutations, however it would be good to generate them all.

Answer 1

Strictly speaking, those are not permutations, but rather sequences over a finite domain.

A trivial algorithm is to generate all sequences, and only output those sequences that satisfy the restrictions. Generating all sequences of length n over a domain A is quite easy with recursion:

class SequenceGenerator {
    char[] domain;
    char[] sequence;
    int n;

    void generate(int i) {
        if (i == n) {
            System.out.println(new String(sequence));
        } else {
            for (char c : domain) {
                sequence[i] = c;
                generate(i + 1);
            }
        }
    }
}

A more refined algorithm would check partially formed sequences. For instance, if you know your sequence starts with AB, you already know it will not satisfy the restriction sequence[0] == sequence[1], so there is no point in filling in the remaining elements:

abstract class PickySequenceGenerator extends SequenceGenerator {

    @Override
    void generate(int i) {
        if (possible(i)) {
            super.generate(i);
        }
    }

    /** @return whether a sequence starting with the first i elements of {@link #sequence} can still satisfy all constraints */
    abstract boolean possible(int i);
}

For extra efficiency, you can assign values to the most constrained sequence elements first.

Answer 2

If you only want to count the sequences rather than generate them, then you can borrow some ideas from combinatorics. First note that without restrictions there are 3*3*3*3 4-character strings from the "alphabet" {A, B, C}. If we add the restriction that the first and second character must be the same, then there are 3*1*3*3 possible strings. If, on the other hand, we add the restriction that the first and third character cannot be the same, then there are 3*3*2*3 possibilities.

If the restrictions are part of the input to your program, then you can use these two examples to create a general solution by assigning the number of choices to each character in the string.

Answer 3

for (char a0='A'; a0<='C'; a0++) {
  char a1=a0;
  for (char a2='A'; a2<='C'; a2++) {
    if (a0 != a2) {
      for (char a3='A'; a3<='C'; a3++) {
         a.append(a0 + a1 + a2 + a3);
      }
    }
  }
}

(pseudocode, but I think you get the picture)