5

I notice in my R console that x=sample(1:n); all(order(order(x)) == x) always evaluates TRUE, for any n. Just to assure you I'm not on the wrong SE site here, I know exactly what the code means, but this still makes my brain hurt. Can anyone draw a picture or give an explanatory proof to show what's going on?

Programming background

In R, sample scrambles a sequence, sampling without replacement, and order gives indices such that x[order(x)] is ascending. == does element-wise comparison, returning a vector of logical values. all returns TRUE for a list that's all TRUE and FALSE if the list contains any FALSE elements.

eric_kernfeld
  • 145
  • 8

2 Answers2

1

In general, when $x$ is a list of $n$ elements, $\text{order}(x)$ is a permutation of $\{1,2,\ldots,n\}$ such that $x_{\text{order}(x)_i} \le x_{\text{order}(x)_j}$ whenever $i<j$. (The elements of $x$, taken in the order given by $\text{order}(x)$, are non-decreasing.) When $x$ is itself a permutation of $\{1,2,\ldots,n\}$, this constraint uniquely defines the order function, and indeed we can say that $x_{\text{order}(x)_i}=i$. (The elements of a permutation of $\{1,2,\ldots,n\}$, taken in non-decreasing order, are just $1,2,\ldots,n$.)

So, in the group of permutations under the composition operator, $\text{order}(x)=x^{-1}.$ But this immediately gives the desired result: $$ \text{order}(\text{order}(x))=\text{order}(x)^{-1}=\left(x^{-1}\right)^{-1}=x. $$

mjqxxxx
  • 41,358
  • Wait a minute. order() is not a member of that permutation group because it selects among many different permutations depending on the input. order(1:4) uses the identity permutation; order(c(2,3,4,1)) uses the permutation y ==> y[c(4, 1, 2, 3)]. – eric_kernfeld Oct 06 '20 at 14:45
  • 1
    Are you saying order() is not a single member of that group but rather the map from a given element to its inverse? – eric_kernfeld Oct 06 '20 at 14:46
  • If I understand right, I really like the answer, but I think it would be clearer if it stated up front that it helps to view every list x as a way of representing the permutation y ==> y[x]. Do you mind if I edit to try to expand on that point, and you can roll back if I screw it up? – eric_kernfeld Oct 06 '20 at 14:51
-1

any is a quantifying operator. If test whether one sequence is identic independent of order to the other. So x=sample(1:n); any(order(order(x)) == x) has always to be true. order() is idempotent. That is, if applied once there is no more change in the next application of order() to the sequence it is applied to.

From order You get the information the order() has the argument decreasing. Per default that is set to FALSE. To invert the order the command has to be

x=sample(1:n); order(order(x),decreasing=TRUE) == x)

Then the any() is obsolete. any implements "Are Some Values True?". So in x=sample(1:n); any(order(order(x)) == x) the identity check == is applied elementwise on the cross of the two lists x and order(order(x)) and then the complete misses are discarded in favor of the few matches.

So

x=sample(1:n); order(order(x)) == order(x) is TRUE always verifying the idempotence of order().

Steffen Jaeschke
  • 867