What is the difference between a shuffle and a permutation?

A shuffle is defined (at least in my class) as:

Let $x = x_1x_2 \cdots x_k$ and $y = y_1 y_2 \cdots y_k$ be words over the same alphabet $\Sigma$. We say that $x$ is a shuffle of $y$ (denoted $x \sim y$) if there exists a permutation $\pi$ of $\{1, 2, \ldots , k\}$ such that $x_{\pi(j)} = y_j$ for $j = 1, 2, \ldots, k$.

Isn't this simply saying that $x \sim y$ if $y$ is a permutation of $x$?

I'm asking because the way the question is asked, it would seem that I need to actually use a $\pi$ to check whether $x \sim y$, but wouldn't such a $\pi$ always exist if $y$ is a permutation of $x$?

I need to describe a Turing machine that recognizes the language $S = \{x,y \mid x \sim y \}$, and the question makes it sound like I need to use a TM that creates permutations over $1$ to $k$ given $k$, and that it's hard to make a polynomial time TM for recognizing $S$. But if it's just permutations, then I have a TM that decides it in $O(n^2)$ time.

Solution 1:

You're right, but it also looks like you're overthinking it:

First: As has already been said in comments, "permutation" has subtly different meanings in different fields. In combinatorics it is common to use the word "permutation" for just an arrangement of things in a linear order, whereas in abstract algebra, a "permutation" is almost always a bijective function from a set -- usually $\{1,2,3,\ldots,n\}$ to itself.

These two concepts are closely related, of course -- a permutation-as-function can describe how to move things around to pass from one permutation-as-arrangement to another, and on the other hand once you decide on a "standard" arrangement of things, you can describe every arrangement by giving the permutation-as-function that will make the standard arrangement into the one you're thinking of. (This will be a unique description of the arrangement if and only if the things you arrange are all different, which is not necessarily the case for your application here).

The exercise seems to be written by or for people who are more comfortable with the abstract-algebra sense of "permuation", and therefore it uses more words to describe the concept that in combinatorics we would just call "one string is a permutation of the other".

Second: Remember that the success criterion for your Turing machine is just that it must give the correct answer. How it finds that answer is up to you. Even though the definition of the problem is in term of quantifying over all permutations, there's no requirement that your machine needs to find the answer by checking the permutations one by one. If you have a faster way to reach an answer that you can prove will be be the same answer as the definition leads to, then it is completely allowed to use the smarter way.

Solution 2:

First I want to amplify on a comment of @Phillip Hamilton, which I think gives the most mathematically precise take on the problem. (It is not necessary to be so precise and some may think it is overly fastidious to do so for the intended application...but this is what the OP asked about, I think.)

For an alphabet $\Sigma$ and a positive integer $k$, let $S(\Sigma,k)$ be the set of strings of length $k$ in the alphabet $\Sigma$. For $x,y \in S(\Sigma,k)$, we are defining an equivalence relation $x \sim y$, called y is a shuffle of x, that is defined in terms of getting from $x$ to $y$ by applying some permutation $\pi \in S_k$. So "Is a shuffle the same as a permutation?" No, because if the strings are e.g.

$x = aaabaaa$

and

$y= aabaaaa$

there is a permutation $\pi$ that takes one to the other, but there is more than one such permutation $\pi$.

This can be most precisely understood in the language of group actions. There is a natural -- permutation! -- action of the symmetric group $S_k$ on $S(\Sigma,k)$. Whenever a group $G$ acts on a set $X$, it determines a partition of the set into orbits under the group: that is, for $x \in X$, the orbit is $\{ g \cdot x \mid g \in G\}$. The corresponding equivalence relation is $x \sim y$ if $y = g \cdot x$ for some $g \in X$. Taking here $G = S_k$ and $X = S(\Sigma,k)$ we get exactly the definition of "$y$ is a shuffle of $x$."

Now suppose $x$ and $y$ are in the same orbit of $G$: thus there is $g_0 \in G$ such that $g_0 \cdot x = y$. If we put $H_x = \{h \in x \mid h \cdot x = x\}$, the stabilizer of $x$ in $G$, then

$\{g \in G \mid g \cdot x = y\} = g_0 H_x$,

i.e., it is a coset of the stabilizer.

So in the present case, there is more than one permutation inducing the same shuffle from $x$ to $y$ precisely when there is a nontrivial permutation $\pi$ such that $\pi \cdot x= x$. In the example above, there are many such permutations: in the example I gave above, the stabilizer of $x$ is a copy of $S_6$: you can freely permute all the $a$'s.

Second: I think the above is helpful in clarifying that to determine whether $y$ is a shuffle of $x$ one need not apply all permutations to $x$ to see if one gets $y$ (which would take time at least $k!$). Indeed $y$ is a shuffle of $x$ precisely when each "letter" in $\Sigma$ appears the same number of times in $x$ as it does in $y$.

There is an obvious algorithm for this: count the number of times the letter $x_1$ appears in $y$. If they are different, $y$ is not a shuffle of $x$. Now move on to $x_2$, and so forth. There are some obvious ways to speed this up (e.g. by recording when a letter appears in $x$ and not counting instances of the same letter more than once!), but this is already of time $O(k^2)$.

Solution 3:

The narrow short answer to your question

Isn't this simply saying that x∼y if y is a permutation of x?

is "yes".

What may be relevant in your particular problem is that there may be more than one permutation that maps a word to an equivalent word, because letters can repeat in words. For example, AAB∼BAA. Two of the six permutations in $S_3$ map one to the other.

A thought about an algorithm: to decide when one word is a shuffle of another you probably want to start with the words, not with the possible permutations.

Solution 4:

The quoted text implicitly distinguishes between an element, which it calls a permutation, of a group, in this case the symmetric group on k elements, and the image, which it calls a shuffle, of an element of a representation of that group, in this case the vector space generated by words over Σ, obtained by applying that element of the group. That is, the permutation is a group element and the shuffle is the result of its action on a particular word. One can debate whether this is a good use of terminology (it seems reasonable to me), but that is the distinction being made. It reflects a quite formal mathematical point of view.