<br />
<br />
<br />
#include "Permutation.h"<br />
<br />
/* In-place Permutations <br />
<br />
permute: OUT[i] = IN[perm[i]] i = 0 .. N-1<br />
invpermute: OUT[perm[i]] = IN[i] i = 0 .. N-1<br />
<br />
PERM is an index map, i.e. a Vector which contains a permutation of<br />
the integers 0 .. N-1.<br />
<br />
From Knuth "Sorting and Searching", Volume 3 (3rd ed), Section 5.2<br />
Exercise 10 (answers), p 617<br />
<br />
*/<br />
<br />
void permute(const int * p, double * data, const int n)<br />
{<br />
int k, pk;<br />
<br />
for (int i = 0; i < n; i++)<br />
{<br />
k = p[i];<br />
<br />
while (k > i) <br />
k = p[k];<br />
<br />
if (k < i)<br />
continue ;<br />
<br />
/* Now have k == i, i.e the least in its cycle */<br />
<br />
pk = p[k];<br />
<br />
if (pk == i)<br />
continue ;<br />
<br />
/* shuffle the elements of the cycle */<br />
<br />
{<br />
double t = data[i];<br />
<br />
while (pk != i)<br />
{<br />
double r1 = data[pk];<br />
data[k] = r1;<br />
k = pk;<br />
pk = p[k];<br />
};<br />
<br />
data[k] = t;<br />
}<br />
}<br />
<br />
}<br />
<br />