Hi @DominicCavenagh and welcome to the SAS Support Communities!
I think this task (as I understand it) can be viewed as a problem in graph theory (which I don't know much about, unfortunately): The four-letter combinations can be thought of as the vertices of a graph and an edge connects two vertices if (and only if) the combinations differ by exactly one permutation of two neighboring letters.
While the entire graph with its 26**4=456976 vertices is huge, it can be decomposed into small disjoint components ("subgraphs") comprising only 24 or fewer vertices. This is because switching two letters doesn't change the choice of the letters. The components are
- comb(26,4) = 14950 combinations of four different letters (with 24 possible permutations each)
- comb(26,3)*3 = 7800 combinations of three different letters one of which occurs twice (with 12 possible permutations each)
- comb(26,2)*2 = 650 combinations of two different letters one of which occurs three times (with 4 possible permutations each)
- comb(26,2) = 325 combinations of two different letters both of which occur twice (with 6 possible permutations each)
- 26 combinations consisting of four equal letters.
(14950*24 + 7800*12 + 650*4 + 325*6 + 26 = 456976)
Each of the above five classes of components can be investigated separately, based on an arbitrarily selected single element of the class (because a one-to-one mapping of the letters doesn't change the structure of a combination). The connection rule implies that a vertex of this particular graph can have at most three edges.
Let's start with the easiest case: class 5. Obviously, all of the 26 constituent combinations AAAA, BBBB, ..., ZZZZ can be selected as "valid" because they are isolated points in the graph.
Class 4: The components of this class can be represented by a subgraph like this:
ABBA
/ \
AABB──ABAB BABA──BBAA
\ /
BAAB
Now you see that some selections are more favorable than others: For example, if you selected ABAB and BABA, you would end up with only these two elements -- the other four elements would then be invalid. However, the selection AABB, ABBA, BAAB, BBAA yields four valid strings -- there is no direct connection (edge) between any two of these four permutations in the graph. It's easy to see that you can't get more than four valid elements out of those six. So, if you want to obtain as many valid four-letter strings as possible, you need to find "optimum" selections like this, i.e., with the maximum number of valid elements, for each class.
[Continuation #1]
Class 3: The representatives of this class have a simple chain structure:
ABBB──BABB──BBAB──BBBA
Obviously, there are three possible "optimum" selections: {ABBB, BBAB}, {ABBB, BBBA} and {BABB, BBBA}.
Class 2: Using the letter choice A, B, C, C, the representative of this class has the below structure:
ACBC──ABCC──BACC──BCAC
/ \ / \
ACCB CABC────────CBAC BCCA
\ / \ /
CACB──CCAB──CCBA──CBCA
The subset of the six permutations highlighted in bold constitutes one of the "optimum" selections (one of two, as it turns out). While this statement seems plausible, it's not obvious (to me). So, let's try to prove it (using SAS):
A "better" selection than the above must contain seven or more out of the twelve permutations. If we can show that a selection of seven would always contain an invalid element, there couldn't be more than seven a fortiori.
%let n=12;
%let k=7;
data test;
array x[&n] $4 ('ABCC' 'ACBC' 'ACCB' 'BACC' 'BCAC' 'BCCA' 'CABC' 'CACB' 'CBAC' 'CBCA' 'CCAB' 'CCBA');
do i=1 to comb(&n, &k);
rc=allcomb(i, &k, of x[*]);
f=0;
do j=1 to &k-1 until(f);
do k=j+1 to &k until(f);
if compged(x[j],x[k])=20 then f=1;
end;
end;
if ~f then output;
end;
run; /* --> 0 observations */
Apparently, each of the comb(12, 7)=792 subsets of 7 out of the 12 permutations in the array creates one or more pairs with generalized edit distance 20 (which in this case is equivalent to a "SWAP", i.e., a transposition of two neighboring letters). The same code with k=6 yields two observations: the two optimum selections. (The second one being the complement of the first, i.e., comprising the six non-bold permutations in the graph above.)
[Continuation #2]
Class 1: Using the letter choice A, B, C, D, the representative of this class has the below structure:
____________________
/ \
ABDC ACBD──ACDB ADBC
/ \ / │ │ \ / \
BADC ABCD │ │ ADCB DABC
/ \ / │ │ \ / \
│ BACD CABD──CADB DACB │
│ │ / \ │ │
│ │ CBAD CDAB │ │
│ │ / \ / \ │ │
│ BCAD CBDA──CDBA DCAB │
│ \ / \ / │
│ BCDA DCBA │
│ \ / │
\ BDCA──DBCA /
\ │ │ /
\ │ │ /
\ │ │ /
\──────BDAC──DBAC─────/
Actually it's rotational symmetric ... Each vertex is linked to exactly three others (as it should, with four different letters, considering the connection rule). We can use almost the same code as above to create the optimum selections (two again) -- each comprising 12 out of the 24 permutations -- and to prove that selecting more than 12 valid elements is impossible. One of the optimum selections is shown above in boldface. The other one is just the complement of it, i.e., the non-bold permutations.
%let n=24;
%let k=12;
data test2;
array c[4] $1 ('A' 'B' 'C' 'D');
array x[&n] $4;
do p=1 to &n;
rc=allperm(p, of c[*]);
x[p]=cat(of c[*]);
end;
do i=1 to comb(&n, &k);
rc=allcomb(i, &k, of x[*]);
f=0;
do j=1 to &k-1 until(f);
do k=j+1 to &k until(f);
if compged(x[j],x[k])=20 then f=1;
end;
end;
if ~f then output;
end;
run; /* --> 2 observations */
Again, with k=13 this step results in 0 observations. Either way the run time was only a few seconds on my workstation.
Given the above results, it should be feasible to select a subset of the original 26**4 four-letter combinations with the maximum possible number of valid elements. And this number should be
14950*12 + 7800*6 + 650*2 + 325*4 + 26 = 228826.
Just translate one of the optimum selections given for each of the five classes to each of the 14950, 7800, 650, 325 and 26 letter combinations, respectively (e.g., by replacing A, B, C, D with K, R, W, Y, etc.). I can help you with that tomorrow (CEST) if needed.
(And if a graph theory adept in the forum recognizes this as something for which a standard solution is known, please chime in.)
Click image to register for webinar
