Upper bound on the number of permutations in a set during an algorithm Fix $n\geq 2$ and let $S_n$ be the symmetric group on $n$ letters with identity $e$. We consider elements of $S_n$ to be bijections $[n]\to [n]$ as well as sequences (one line notation). For $1\leq i<n$, let $s_i$ be the transposition exchanging $i$ and $i+1$. Consider the following algorithm that successively constructs subsets $A_N\subseteq S_n$.


*

*Let $A_0=\{e\}$.

*At step $K$, remove the least element from $A_K$ in lexicographical order, say $f\in A_K$, and for each subset $B\subseteq [n-1]$ such that if $B=\{b_1,\ldots,b_m\}$, then $|b_i-b_j|\geq 2$ for all $i\neq j$ and $f(b_i)<f(b_{i}+1)$ for all $i$, add the permutation $fs_{b_1}s_{b_2}\cdots s_{b_m}$ to $A_K$. (In weak order, this will add all maximal elements of Boolean algebra intervals with minimal element $f$). After this one removal and all such additions we obtain the set $A_{K+1}$.


Step 2 is repeated until the ultimate set is empty. The penultimate set will contain only the longest element, the reversal permutation.
I'm interested in estimating the number $M_n$ defined by
$$M_n=\max_{K}{|A_K|}$$
We have
$$M_5\leq 0.32\cdot 5!$$
$$M_6\leq  0.3125\cdot 6!$$
$$M_7\leq 0.294\cdot 7!$$
$$M_8\leq 0.292\cdot 8!$$
$$M_9\leq 0.282\cdot 9!$$
$$M_{10}\leq 0.2811\cdot 10!$$
$$M_{11}\leq 0.2753\cdot 11!$$
$$M_{12}\leq 0.2749\cdot 12!$$
This will be the amount of space required in my algorithm for computing the sequence http://oeis.org/A006245. To me it seems $M_n$ is just as hard to compute as this sequence, which is why I'm looking for an estimate. I'm mostly interested in $n=16$, since this is the first unknown value. If $M_{16}$ is around $0.27\cdot 16!$, then it's not feasible at the moment to do the computation, whereas if it's $0.2\cdot 16!$ it might be.
 A: I have bad news.  The (constant for large n for your) upper bound will never drop below 1/4.  Thus my prediction in a comment above will hold.
A key observation is that every permutation sits in one of the A_k, and so you will run through this n factorial times. One way to see this is that  by induction every permutation of the smaller elements is generated, and then take up to n-1 steps to move the largest element in position.  If I had known this yesterday, I could have answered sooner.
With this observation, we can see a key property.  Setting m =(n-1)!, we process all the permutations beginning with 1 so that A_m has exactly those permutations with second element 1.  One can then conclude the nature of A_jm: It is all permutations with first element larger than j and second element j or less. This gives a lower bound on the constant of (n-j)*j/(n(n-1)), which is bounded from below by 1/4 when j is floor(n/2).
You can extend this to analyze A_(jm +r) where r is a multiple of a smaller factorial.  For a Starbucks card I might extend the analysis for you, especially if the sequence is algebraically related to M_n. For programming purposes, the idea that the upper bound is not far from 1/4 (maybe 1/4 times (1 + 1/(n-2)?) should suffice for your planning.
Gerhard "Proofreads For Starbucks Cards Too" Paseman, 2017.12.01.
