Permutations/Rank of a permutation: Difference between revisions

Content added Content deleted

Inline

@@ Line 450: / Line 450: @@
 =={{header|EasyLang}}==
 <syntaxhighlight>
-proc nextperm . a[] .
-   n = len a[]
-   if n = 0
-      return
-   .
-   k = n - 1
-   while k >= 1 and a[k + 1] <= a[k]
-      k -= 1
-   .
-   if k = 0
-      a[] = [ ]
-      return
-   .
-   l = n
-   while a[l] <= a[k]
-      l -= 1
-   .
-   swap a[l] a[k]
-   k += 1
-   while k < n
-      swap a[k] a[n]
-      k += 1
-      n -= 1
-   .
-.
 func[] init n .
    for i to n
@@ Line 480: / Line 455: @@
    .
    return r[]
+.
+func fac n .
+   f = 1
+   for i to n
+      f *= i
+   .
+   return f
 .
 func[] getperm n r .
    perm[] = init n
-   for i = 1 to r
+   fa = fac n
-      nextperm perm[]
+   for i = n downto 1
+      fa /= i
+      d = r div fa + 1
+      r = r mod fa
+      r[] &= perm[d]
+      for j = d to i - 1
+         perm[j] = perm[j + 1]
+      .
    .
-   return perm[]
+   return r[]
 .
 func getrank n p[] .
    perm[] = init n
-   repeat
+   fa = fac n
-      if perm[] = p[]
+   for i = n downto 1
-         return i
+      fa /= i
+      h = p[n - i + 1]
+      d = 1
+      while perm[d] <> h
+         d += 1
+      .
+      r += fa * (d - 1)
+      for j = d to i - 1
+         perm[j] = perm[j + 1]
       .
-      nextperm perm[]
-      until perm[] = [ ]
-      i += 1
    .
-   return -1
+   return r
 .
 proc show . .
@@ Line 504: / Line 498: @@
       h[] = getperm 3 i
       print i & " -> " & h[] & " -> " & getrank 3 h[]
+   .
+   print ""
+   for i to 4
+      r = random fac 12 - 1
+      write r & " -> "
+      h[] = getperm 12 r
+      write h[]
+      print " -> " & getrank 12 h[]
    .
 .
 show
-func fac n .
-   f = 1
-   for i to n
-      f *= i
-   .
-   return f
-.
-print ""
-for i to 4
-   r = random fac 12 - 1
-   write r & " -> "
-   print getperm 12 r
-.
 </syntaxhighlight>
 {{out}}
@@ Line 530: / Line 519: @@
 -> [ 2 1 0 ] -> 5
-368494427 -> [ 9 2 6 5 1 11 8 10 3 7 4 0 ]
+381502760 -> [ 9 6 1 3 10 11 8 5 2 4 0 7 ] -> 381502760
-244949381 -> [ 6 1 7 0 3 2 8 11 4 10 9 5 ]
+205815418 -> [ 5 1 9 2 7 4 10 6 3 11 0 8 ] -> 205815418
-378494158 -> [ 9 5 3 0 4 1 6 11 10 8 2 7 ]
+229356067 -> [ 5 9 2 0 6 3 1 8 11 4 10 7 ] -> 229356067
-181506774 -> [ 4 7 0 2 9 3 10 6 5 1 8 11 ]
+421960570 -> [ 10 6 2 9 3 4 5 0 7 11 1 8 ] -> 421960570
 </pre>