fork download
copy 
  1. import math
  2.  
  3.  
  4. def num_smaller(m, p, i):
  5.   count = 0
  6.   for j in range(i):
  7.     count += int(m > p[j])
  8.   return count
  9.  
  10.  
  11. def num_preceding_permutations(n, k, m, p, i):
  12.   num_unused_preceding = m - 1 - num_smaller(m, p, i)
  13.   return (
  14.       math.factorial(n - i - 1)
  15.       / math.factorial(n - k)
  16.   ) * num_unused_preceding
  17.  
  18.  
  19. def rank(p, n):
  20.   k = len(p)
  21.   return int(sum(
  22.     num_preceding_permutations(n, k, m, p, i)
  23.     for i, m in enumerate(p)))
  24.  
  25.  
  26. def unrank(index, n, k):
  27.   p = []
  28.   j = index
  29.   for i in range(k):
  30.     m = 0
  31.     while (num_preceding_permutations(n, k, m + 1, p, i)
  32.            <= j):
  33.       m += 1
  34.     p.append(m)
  35.     j -= num_preceding_permutations(n, k, m, p, i)
  36.   return p
  37.  
  38.  
  39. ps = [
  40.   ([3, 4], 4),
  41.   ([3, 2, 4], 4),
  42.   ([34, 2, 18, 27, 10], 38)
  43. ]
  44.  
  45. for p, n in ps:
  46.   rank_p = rank(p, n)
  47.   print((p, rank_p, unrank(rank_p, n, len(p)) == p))
Success #stdin #stdout 0.1s 14084KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
([3, 4], 8, True)
([3, 2, 4], 15, True)
([34, 2, 18, 27, 10], 52370344, True)
https://ideone.com/XSL0fK
language:
Python 3 (python  3.12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!