Advertisement
Guest User

Untitled

a guest
Mar 26th, 2019
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.57 KB | None | 0 0
  1. # -*- coding: utf-8 -*-
  2.  
  3. # Napisz program wyznaczający podzbiór T o randze r w uporządkowaniu
  4. # leksykograficznym k-elementowych podzbiorów zbioru {1,...,n}.
  5.  
  6.  
  7. class SubsetFinder:
  8.  
  9.     def __init__(self, n, k, r):
  10.         self.n = n
  11.         self.k = k
  12.         self.rank = r
  13.         self.binomials = self.pascal_triangle()
  14.  
  15.     def pascal_triangle(self):
  16.         # zwraca listę kolejnych wierszy trójkąta Pascala
  17.         pt = []
  18.         pt.append([1])
  19.         currentline = [pt[0]]
  20.         for i in range(1, self.n):
  21.             newline = [1]
  22.             for j in range(1, len(currentline)):
  23.                 newline.append(currentline[j - 1] + currentline[j])
  24.             newline.append(1)
  25.             pt.append(newline)
  26.             currentline = newline
  27.         return pt
  28.  
  29.     def binomial(self, n, k):
  30.         # wyznacza z trójkąta Pascala współczynnik dwumianowy C(n, k)
  31.         return self.binomials[n][k]
  32.  
  33.     def unrank(self):
  34.         # wyznacza podzbiór na podstawie rangi
  35.         r = self.rank
  36.         subset = []
  37.         candidate = 1
  38.         for i in range(1, self.k + 1):
  39.             while (self.binomial(self.n - candidate, self.k - i) <= r and candidate < self.n):
  40.                 r -= self.binomial(self.n - candidate, self.k - i)
  41.                 candidate += 1
  42.             subset.append(candidate)
  43.             candidate += 1
  44.         return subset
  45.  
  46. class Main:
  47.  
  48.     n = int(raw_input("Podaj n: \n"))
  49.     k = int(raw_input("Podaj k: \n"))
  50.     r = int(raw_input("Podaj r: \n"))
  51.     sf = SubsetFinder(n, k, r)
  52.     print sf.unrank()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement