SRM144 DIV1 550

排列组合的问题，对于不同的情况分别考虑即可，引入定义：

P(n,r) n个元素集合的r-排列的个数

C(n,r) n个元素集合的r-组合的个数

M(k,r) k种元素多重集的r-组合个数, M(k,r) = C(r+k-1,r)

共有4种情况

sorted	unique	总数
true	true	C(choices,blanks)
true	false	M(choices,blanks)
false	true	P(choices,blanks)
false	false	choices^blanks(乘方)

剩下的就是排序等基本的程序操作了，注意精度问题

 1 class Lottery:
 2     def sortByOdds(self, rules):
 3         l = [self._processRule(rule) for rule in rules]
 4         l = sorted(l, key = lambda x: x)
 5         l = [x[1] for x in l]
 6         return tuple(l)
 7 
 8     def _p(self, n, r):
 9         total = 1
10         for i in range(n-r+1, n+1):
11             total = total * i
12         return total
13 
14     def _c(self, n, r):
15         total = 1
16         for i in range(n-r+1, n+1):
17             total = total * i
18         for i in range(1, r+1):
19             total = total / i
20         return int(total)
21 
22     def _m(self, k, r):
23         return self._c(k+r-1, r)
24 
25     def _result(self, name, choices, blanks, _sorted, unique):
26         if _sorted and unique:
27             total = self._c(choices, blanks)
28         elif _sorted and not unique:
29             total = self._m(choices, blanks)
30         elif not _sorted and unique:
31             total = self._p(choices, blanks)
32         else:
33             total = 1
34             for i in range(0,blanks):
35                 total = total * choices
36         return (total, name)
37 
38     def _processRule(self, rule):
39         splits = rule.split(':')
40         name = splits[0]
41 
42         splits = splits[1].split(' ')
43         choices = int(splits[1])
44         blanks = int(splits[2])
45         _sorted = splits[3] == 'T'
46         unique = splits[4] == 'T'
47         return self._result(name, choices, blanks, _sorted, unique)
48         
49         
50 
51 
52 
53 
54 # test
55 o = Lottery()
56 assert(o._c(5, 2) == 10)
57 
58 # test1
59 assert(o.sortByOdds(("PICK ANY TWO: 10 2 F F"
60 ,"PICK TWO IN ORDER: 10 2 T F"
61 ,"PICK TWO DIFFERENT: 10 2 F T"
62 ,"PICK TWO LIMITED: 10 2 T T")) ==
63        ( "PICK TWO LIMITED",
64   "PICK TWO IN ORDER",
65   "PICK TWO DIFFERENT",
66   "PICK ANY TWO" ))
67 
68 # test: 空值
69 assert(o.sortByOdds(()) == ())

View Code