11
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Everything you said is correct. $\endgroup$ – MJD Apr 8 '17 at 12:08
  • 1
    $\begingroup$ I didn't want to add the actual question since I don't want my assignment question answered for me :) I just want to know whether my understanding of shuffle is correct, and it seems to be. Edit: this was an answer to a comment that was deleted, I think $\endgroup$ – Kitalda Apr 8 '17 at 12:17
  • 5
    $\begingroup$ The term "permutation" has different interpretations, in one sense we can think of them as being active functions or passive arrangements (the Wikipedia article covers this distinction well). In this case, we can think of a shuffle as a realization of a permutation applied to a string. $\endgroup$ – benguin Apr 8 '17 at 12:18
  • 3
    $\begingroup$ @PhillipHamilton: That sounds like a really roundabout way to react to a simple trouble with understanding how the exercise says. $\endgroup$ – Henning Makholm Apr 8 '17 at 12:36
  • 2
    $\begingroup$ In the study of formal languages, shuffle is often used to denote an operation that combines two words into one. By extension, the shuffle of two languages $L_1$ and $L_2$ consists of words that are the shuffles of pairs of words: one from $L_1$ and the other from $L_2$. Using shuffle to denote the result of applying a permutation is not standard and, although legitimate, not the best choice of nomenclature. $\endgroup$ – Fabio Somenzi Apr 8 '17 at 13:22
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I would just like to remark that you are absolutely right in that I was overthinking it - since it was sort of a trick question! It was an exercise meant to find out which students would see through the more cumbersome notation and which would not ;) This class is more used to the combinatorics understanding of permutation - we had the same lecturer last semester in a combinatorics class. $\endgroup$ – Kitalda Apr 16 '17 at 12:50
7
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ Although your answer is really nice and interesting, it was in fact not what I asked about. But thank you for writing a nice answer, and I did indeed make an algorithm along the lines of what you describe. $\endgroup$ – Kitalda Apr 16 '17 at 12:52
6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The point of this exercise turned out to be that it was worded far more formally than necessary, especially for this course. $\endgroup$ – Kitalda Apr 16 '17 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.