fork download 
  1. import math
  2.  
  3.  
  4. def rank_permutation(seq):
  5.     ref = sorted(seq)
  6.     if ref == seq:
  7.         return 0
  8.     else:
  9.         rank = 0
  10.         f = math.factorial(len(seq)-1)
  11.         for x in ref:
  12.             if x < seq[0]:
  13.                 rank += f
  14.             else:
  15.                 rank += rank_permutation(seq[1:]) if seq[1:] else 0
  16.                 return rank
  17.  
  18.  
  19. def unrank_permutation(n, k):
  20.     """
  21.     Generates the k-th permutation of size n.
  22.  
  23.     Args:
  24.         n: The size of the permutation.
  25.         k: The rank of the permutation (0-indexed).
  26.  
  27.     Returns:
  28.         A list representing the k-th permutation of size n.
  29.     """
  30.     if not (0 <= k < math.factorial(n)):
  31.         raise ValueError("Rank k is out of bounds.")
  32.  
  33.     items = list(range(n))
  34.     permutation = []
  35.     temp_k = k
  36.  
  37.     for i in range(n, 0, -1):
  38.         index = temp_k // math.factorial(i - 1)
  39.         temp_k %= math.factorial(i - 1)
  40.         permutation.append(items.pop(index))
  41.  
  42.     return permutation
  43.  
  44.  
  45. def binomial(n,k):
  46.     if n < 0 or k < 0 or k > n: return 0
  47.     b = 1
  48.     for i in range(k): b = b*(n-i)//(i+1)
  49.     return b
  50.  
  51.  
  52. def unchoose(n,S):
  53.     k = len(S)
  54.     if k == 0 or k == n: return 0
  55.     j = S[0]
  56.     if k == 1: return j
  57.     S = [x-1 for x in S]
  58.     if not j: return unchoose(n-1,S[1:])
  59.     return binomial(n-1,k-1)+unchoose(n-1,S)
  60.  
  61.  
  62. def choose(X,k):
  63.     n = len(X)
  64.     if k < 0 or k > n: return []
  65.     if not k: return [[]]
  66.     if k == n: return [X]
  67.     return [X[:1] + S for S in choose(X[1:],k-1)] + choose(X[1:],k)
  68.  
  69.  
  70. def unget(perm, n):
  71.   zipped = zip(perm, range(len(perm)))
  72.   return list(zipped)
  73.  
  74. print(unget([0, 2, 1], 4))
  75.  
Success #stdin #stdout 0.1s 14112KB
comments (?)
stdin 
Standard input is empty
stdout 
[(0, 0), (2, 1), (1, 2)]
https://ideone.com/VZPf5o
language:
Python 3 (python  3.12)
created:
7 days 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!