1 files changed, 194 insertions, 0 deletions
diff --git a/gsl-1.9/permutation/canonical.c b/gsl-1.9/permutation/canonical.c
new file mode 100644
index 0000000..080c8ee
--- /dev/null
+++ b/gsl-1.9/permutation/canonical.c
@@ -0,0 +1,194 @@
+/* permutation/permutation.c
+ * 
+ * Copyright (C) 2001, 2002 Nicolas Darnis
+ * 
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or (at
+ * your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/* Modified for GSL by Brian Gough.
+ * Use in-place algorithms, no need for workspace
+ * Use conventions for canonical form given in Knuth (opposite of Sedgewick)
+ */
+
+#include <config.h>
+#include <gsl/gsl_errno.h>
+#include <gsl/gsl_permutation.h>
+
+int
+gsl_permutation_linear_to_canonical (gsl_permutation * q,
+                                     const gsl_permutation * p)
+{
+  const size_t n = p->size;
+  size_t i, k, s;
+  size_t t = n;
+
+  const size_t *const pp = p->data;
+  size_t *const qq = q->data;
+
+  if (q->size != p->size)
+    {
+      GSL_ERROR ("size of q does not match size of p", GSL_EINVAL);
+    }
+
+  for (i = 0; i < n; i++)
+    {
+
+      k = pp[i];
+      s = 1;
+
+      while (k > i)
+        {
+          k = pp[k];
+          s++;
+        }
+
+      if (k < i)
+        continue;
+
+      /* Now have k == i, i.e the least in its cycle, and s == cycle length */
+
+      t -= s;
+
+      qq[t] = i;
+
+      k = pp[i];
+      s = 1;
+
+      while (k > i)
+        {
+          qq[t + s] = k;
+          k = pp[k];
+          s++;
+        }
+
+      if (t == 0)
+        break;
+    }
+
+  return GSL_SUCCESS;
+}
+
+int
+gsl_permutation_canonical_to_linear (gsl_permutation * p,
+                                     const gsl_permutation * q)
+{
+  size_t i, k, kk, first;
+  const size_t n = p->size;
+
+  size_t *const pp = p->data;
+  const size_t *const qq = q->data;
+
+  if (q->size != p->size)
+    {
+      GSL_ERROR ("size of q does not match size of p", GSL_EINVAL);
+    }
+
+  for (i = 0; i < n; i++)
+    {
+      pp[i] = i;
+    }
+
+  k = qq[0];
+  first = pp[k];
+
+  for (i = 1; i < n; i++)
+    {
+      kk = qq[i];
+
+      if (kk > first)
+        {
+          pp[k] = pp[kk];
+          k = kk;
+        }
+      else
+        {
+          pp[k] = first;
+          k = kk;
+          first = pp[kk];
+        }
+    }
+
+  pp[k] = first;
+
+  return GSL_SUCCESS;
+}
+
+
+size_t
+gsl_permutation_inversions (const gsl_permutation * p)
+{
+  size_t count = 0;
+  size_t i, j;
+  const size_t size = p->size;
+
+  for (i = 0; i < size - 1; i++)
+    {
+      for (j = i + 1; j < size; j++)
+        {
+          if (p->data[i] > p->data[j])
+            {
+              count++;
+            }
+        }
+    }
+
+  return count;
+}
+
+size_t
+gsl_permutation_linear_cycles (const gsl_permutation * p)
+{
+  size_t i, k;
+  size_t count = 0;
+  const size_t size = p->size;
+
+  for (i = 0; i < size; i++)
+    {
+
+      k = p->data[i];
+
+      while (k > i)
+        {
+          k = p->data[k];
+        }
+
+      if (k < i)
+        continue;
+
+      count++;
+    }
+
+  return count;
+}
+
+size_t
+gsl_permutation_canonical_cycles (const gsl_permutation * p)
+{
+  size_t i;
+  size_t count = 1;
+  size_t min = p->data[0];
+
+  for (i = 0; i < p->size; i++)
+    {
+      if (p->data[i] < min)
+        {
+          min = p->data[i];
+          count++;
+        }
+    }
+
+  return count;
+}
+