# Arrange StakExchangePuzzling [closed]

Find the total number of permutations of the word STAKEXCHANGEPUZZLING such that the letters STAK always stay together.

Rules:

• For every odd pair of adjacent consonants - first letter must be alphabetically smaller than the second.
• For every even pair of adjacent consonants - the opposite (first letter must be alphabetically bigger than the second).

What is odd and even pair - let's say we have hnanh - hn is the first ( odd ) consonants pair, nh is the second ( even ) pair.

• Added in end of question. – Kradec na kysmet Apr 10 '19 at 22:32
• Thank you for that. So "even" refers to the 2nd, 4th etc pair, not to the index within the word? – Weather Vane Apr 10 '19 at 22:32
• I can't find any words at all - even stack is unacceptable becaus both sets of consonant pairs are in alphabetical order. – Weather Vane Apr 10 '19 at 22:39
• Unless you have a definitive list of every rearrangement of letters that fits your ruleset, comprised of "words" taken from some definitive authoritative word list, and you intend to give a checkmark to the first person who reproduces your definitive "Find all the words" solution... I think you may need to reformulate what you're asking. Usually these types of questions make poor puzzles (there's nothing to solve, just a search for pattern matches to arbitrary rules), and nothing that makes one answer more "right" than another, so any answer is equally valid. Maybe a way to "keep score"? – Rubio Apr 10 '19 at 22:40
• It's solved by programming and a lexicon. By "words" do you mean dictionary words or some other definition? – Weather Vane Apr 10 '19 at 22:43

So far:

The first attempt to solve it by brute force for the given conditions is still running.
It will quite likely still be running next week...
So thinking through a strategic solution:

There are 6 vowels and 14 consonants in STAKEXCHANGEPUZZLING.
There cannot be any double vowels, or triple consonants.
So if v=vowel and c=consonant, the arrangement must be
ccvccvccvccvccvccvcc

The letters STAK must be adjacent.
The 1st, 3rd, 5th and 7th consonant pair must be in alphabetical sequence, so one of
STAKcvccvccvccvccvcc
ccvccvSTAKcvccvccvcc
ccvccvccvccvSTAKcvcc

The 2nd, 4th and 6th consonant pair must be in reverse alphabetical sequence.
So K must be followed by C, G or H, now one of
STAKCvccvccvccvccvcc
STAKGvccvccvccvccvcc
STAKHvccvccvccvccvcc
ccvccvSTAKCvccvccvcc
ccvccvSTAKGvccvccvcc
ccvccvSTAKHvccvccvcc
ccvccvccvccvSTAKCvcc
ccvccvccvccvSTAKGvcc
ccvccvccvccvSTAKHvcc

The number of ways to arrange the remaining 5 vowels, with 1 duplicate, is
$$\frac{5!}{2!} = 60$$
So the next task is to permute consonant pairs leaving out the vowels,
and them multiply the result by $$60$$.

Edit (continued):

There are 3 sets of 10 consonants to permute in pairs with the given restrictions.
There are some duplicated consonants, and by brute force I found $$74340$$ unique perms.
Each of the STAKC, STAKG and STAKH can be in $$3$$ positions.

$$74340 \times 3 \times 60 =$$

13381200 solutions.

Edit 2: thanks to @PiIsNot3 observation about double letters.

The revised number of unique consonant perms is $$42660$$.
$$42660\times 3 \times 60 =$$

7678800 solutions.

• I don't think brute force will do it this year to be honest :P – Kradec na kysmet Apr 11 '19 at 8:17
• I gave up on that, but for finding the number of consonant pair perms took a fraction of a second. – Weather Vane Apr 11 '19 at 9:51

$$\text{STAKG_CG_HL_NZ_NP_XZ}$$ Call each group of 2 consonants (excluding the STAKG substring that must exist together) a cluster. There are $$2^5$$ distributions of the consonants such that each cluster contains the same consonants in the same locations. For example, in the example above, an equivalent distribution of consonants with the same clusters would be:
$$\text{STAKG_GC_HL_ZN_PN_XZ}$$ However, only one of these distributions satisfies the constraints of the problem statement, namely this one:
$$\text{STAKG_CG_LH_NZ_PN_XZ}$$ Thus, to count the total number of valid consonant distributions, we only need to count the number of valid cluster distributions, then divide by $$2^5.$$