Find a subdistribution Let $\alpha$ be a composition of $n$ into nonzero parts and let $\mathcal L$ be a set of permutations of a finite multiset having $n$ elements, such that each element of $\mathcal L$ is constant on each part of $\alpha$.
For example, for $n=8$ we could have $\alpha=(3, 2, 1, 1, 1)$ and $\mathcal L = \{ A A A | B B | A | B | C | , B B B | A A | C | A | A \}$.
Is there a good algorithm to decide whether there is a non-trivial subset $S$ of the parts of $\alpha$ such that for all elements $w$ in $\mathcal L$, the multiset of corresponding elements in $w$ is the same?
In the example above, taking $S=\{1,2,4\}$ designates a non-trivial subdistribution, consisting of three $A$'s and three $B$'s.
More generally, can we efficiently find all subsets $S$ which are minimal with respect to inclusion?
As a further example, if all parts of $\alpha$ are equal to $1$ and $\mathcal L$ consists of the identity permutation of $\{1,\dots,n\}$ and another permutation $\pi$, then the subsets $S$ are precisely the indices of the elements in the cycles of $\pi$.  Thus, it admits a non-trivial subdistribution if and only if $\pi$ is not a cycle.
UPDATE: The special case where all parts of $\alpha$ are equal to $1$ would be equally interesting.
 A: You can solve the problem via integer linear programming as follows.  Let $a_{i,j,k}$ denote the number of times in permutation $i$ and part $j$ that letter $k$ appears. Let binary decision variable $x_j$ indicate whether part $j$ is selected.  Let nonnegative integer decision variable $y_k$ represent the number of times letter $k$ is selected in each permutation.  The problem is to minimize $\sum_j x_j$ subject to
\begin{align}
\sum_j a_{i,j,k} x_j &= y_k &&\text{for all $i$ and $k$}\tag1 \\
\sum_j x_j &\ge 1 \tag2
\end{align}
Constraint $(1)$ forces each permutation $i$ to have the same number of appearances of letter $k$ across all selected parts.
Constraint $(2)$ avoids the trivial zero solution.
For your sample data, an optimal solution is $x=(0,0,1,0,1)$ and $y=(1,0,1)$, which corresponds to $S=\{3,5\}$, with one $A$ and one $C$.
A: This problem is NP-complete because you can reduce a special version of 3DM to it, when every vertex is 3-regular (see (SP2) in Garey and Johnson).
Suppose that we are given a 3-uniform hypergraph $(V,E)$ as an input of 3DM.
The vertices of the hypergraph $V$ will correspond to the permutations of $\mathcal L$, such that each permutation will consist of singleton A's and B's, for example, A|B|B|A|A.
We pick $n=|E|$, the number of edges of the hypergraph.
If a vertex is incident to an edge, then we put a B to the corresponding part, otherwise an A.
The 3-regularity condition implies that every part has exactly 3 B's.
Note that whenever we pick an edge, it will contain at least one vertex, so the union of the parts has to contain at least one B.
It cannot contain 3 B's, because then it would need to contain every part.
If it contains 2 B's, then its complement would contain exactly one B.
Finally, if it contains exactly 1 B, then it is a 3DM.
From here it is straightforward to see that this has a solution if and only if the 3DM had one.
