  Given integers $k\geq 2$ and $a_1,\ldots,a_k\geq 1$, let
$\boldsymbol{a}:=(a_1,\ldots,a_k)$ and $n:=a_1+\cdots+a_k$. An
$\boldsymbol{a}$-multiset permutation is a string of length $n$ that contains
exactly $a_i$ symbols $i$ for each $i=1,\ldots,k$. In this work we consider the
problem of exhaustively generating all $\boldsymbol{a}$-multiset permutations
by star transpositions, i.e., in each step, the first entry of the string is
transposed with any other entry distinct from the first one. This is a
far-ranging generalization of several known results. For example, it is known
that permutations ($a_1=\cdots=a_k=1$) can be generated by star transpositions,
while combinations ($k=2$) can be generated by these operations if and only if
they are balanced ($a_1=a_2$), with the positive case following from the middle
levels theorem. To understand the problem in general, we introduce a parameter
$\Delta(\boldsymbol{a}):=n-2\max\{a_1,\ldots,a_k\}$ that allows us to
distinguish three different regimes for this problem. We show that if
$\Delta(\boldsymbol{a})<0$, then a star transposition Gray code for
$\boldsymbol{a}$-multiset permutations does not exist. We also construct such
Gray codes for the case $\Delta(\boldsymbol{a})>0$, assuming that they exist
for the case $\Delta(\boldsymbol{a})=0$. For the case
$\Delta(\boldsymbol{a})=0$ we present some partial positive results. Our proofs
establish Hamilton-connectedness or Hamilton-laceability of the underlying flip
graphs, and they answer several cases of a recent conjecture of Shen and
Williams. In particular, we prove that the middle levels graph is
Hamilton-laceable.
