问题描述
在大多数国家，有大量不同的彩票游戏供投机者选择。彩票的规则由两个整数（choices和blanks）及两个布尔型变量（sorted和unique）定义。choices代表你可以使用在你的彩票上的最高有效数。（所有在1到choices之间的整数，包括choices，是有效数并可以使用在你的彩票上。）blanks代表你可以插入的数字的数量。
sorted和unique变量表明你可创建的彩票的限制条件。若sorted被设为true，那么彩票上的数字必须被写为非降序的。若sorted被设为false，那么彩票上就可以任意写。同样的，若unique被设为true，那么你所写的数字都必须是唯一的。若unique被设为false，那就可以写重复数了。 下面有几个彩票的示例，其中choices=15然后blanks=4：{3,7,12,14} -- 这个彩票绝对是可以的。
{13,4,1,9} -- 因为这组数字并不是顺序的，所以必须是sorted=false才合法。 {8,8,8,15} -- 因为有数字重复，所以必须当unique=false时才合法。 {11,6,2,6} -- 这组数字必须当sorted=false且unique=false时才合法。给你一列彩票和对应的规则，返回一列彩票的名字并以获胜的难易程度来排序。获胜的几率=(1/合法的彩票数量)。最容易获胜的彩票需要出现在列表的最前面。Ties should be broken alphabetically
定义
Class: Lottery
Method: sortByOdds Parameters: String[] Returns: String[] Method signature: String[] sortByOdds(String[] rules) (确定你的method是public)约束
- 规则将包含0到50个元素，包括0和50.
- 每一个规则元素将包含11到50个字符，包括11和50 - 所有规则元素将按这样的格式"<NAME>:_<CHOICES>_<BLANKS>_<SORTED>_<UNIQUE>"（quotes for clarity）。下划线代表一个空格。 - <NAME>包含1到40个字符，包括1和40，而且仅由大写字母('A'-'Z')和空格(' ')组成，前后均无空格。 - <CHOICES>是10到100的整数，包括10和100，最前面没有0。 - <BLANKS>是1到8的整数，包括1和8，最前面没有0。 - <SORTED>会是'T'(true)或'F'(false)中的一个。 - <UNIQUE>会是'T'(true)或'F'(false)中的一个。 - 规则里没有重名的元素例子
0)
{"PICK ANY TWO: 10 2 F F"
,"PICK TWO IN ORDER: 10 2 T F" ,"PICK TWO DIFFERENT: 10 2 F T" ,"PICK TWO LIMITED: 10 2 T T"}返回：
{ "PICK TWO LIMITED", "PICK TWO IN ORDER", "PICK TWO DIFFERENT", "PICK ANY TWO" }"PICK ANY TWO"中所有空格可以是1到10的数字。那么，就会有10*10种可能的彩票，所以你赢的概率为1/100
"PICK TWO IN ORDER"显示第一个数字不能比第二个数字更大。这就排除了45种可能性，只剩下55种合法彩票。那么赢得概率就是1/55. "PICK TWO DIFFERENT"只是不允许彩票中第一个数字和第二个数字一样。这里有10个这样的彩票，那么赢得概率就变为1/90。 最后，"PICK TWO LIMITED"在"PICK TWO IN ORDER"不允许的45个彩票的基础上又增加了另外10个。所以现在概率变为1/45。1)
{"INDIGO: 93 8 T F",
"ORANGE: 29 8 F T", "VIOLET: 76 6 F F", "BLUE: 100 8 T T", "RED: 99 8 T T", "GREEN: 78 6 F T", "YELLOW: 75 6 F F"}返回：
Returns: { "RED", "ORANGE", "YELLOW", "GREEN", "BLUE", "INDIGO", "VIOLET" }需要注意：INDIGO和BLUE是同样的概率（1/186087894300）。按字母排序，所以BLUE在INDIGO前面。
2)
{}
返回：
{ }为空的情况
解析
1 规则
choices 最高有效数 1到choices
blanks 有效数个数 sorted 是否降序 true必须升序 false无限制 unique 是否必须唯一 true必须唯一 false无限制2 计算方法
这实际上是一个排序问题（参考人教版新课标选修2-3,1.2节排列与组合 http://www.gaokao.com/zyk/dzkb/sxkb/rxsx2_3/）
1）sorted=false；unique=true
从m个不同元素中，抽取n个元素的排列，不可重复，无需顺序排列。
结果：A(m,n)2）sorted=true；unique=true
从m个不同元素中，抽取n个元素的排列，不可重复，需顺序排列。
结果：C(m,n)3）sorted=false；unique=false
从m个不同元素中，抽取n个元素的排列，可重复，无需顺序排列。
分析： n个空格的中的任意一个，可抽取的元素个数都为m，故其排列共有：n个m相乘 结果： m^n4）sorted=true；unique=false
从m个不同元素中，抽取n个元素的排列，可重复，需顺序排列。
结果：C(m+n-1,n) （说不清楚为什么。。。）| Choices | Blanks | Sorted | Unique | 计算公式 |
| m | n | False | False | m^n |
| m | n | False | True | A(m,n) |
| m | n | True | False | C(m+n-1,n) |
| m | n | True | True | C(m,n) |
注1：A(m,n)=m*(m-1)*(m-2).....(m-n+1), 如A(4,3)=4*3*2
注2：C(m,n)=A(m,n)/A(n,n)，如C(4,3)=4*3*2/3*2*13 边界
从原文中我们知道m始终大于n，故不用考虑边界问题。
解答
1 实现A(m,n)
//A(m,n)未考虑边界问题 public int Arrangement(int m,int n) { int result = 1; for (int i = 0; i < n; i++) { result = result * m; m = m - 1; } return result; } 2 实现C(m,n)
//C(m,n)=A(m,n)/A(n,n) public int Combination(int m, int n) { int result = 1; result = Arrangement(m, n) / Arrangement(n, n); return result; } 3 实现m^n
//m^n public int PowerOf(int m, int n) { int result = 1; for (int i = 0; i < n; i++) { result = result * m; } return result; } 4 根据规则计算出排列组合数
//根据规则计算出排列组合数 public int Analysis(string rule) { string[] term; term = Detach(rule); //使用正则表达式将规则分拆 int m = int.Parse(term[0]); int n = int.Parse(term[1]); string sorted = term[2]; string unique = term[3]; if ( sorted == "F" && unique == "F") { //m^n return PowerOf(m, n); } if (sorted == "F" && unique == "T") { //A(m,n) return Arrangement(m, n); } if (sorted == "T" && unique == "F") { //C(m+n-1,n) return Combination(m + n - 1, n); } if (sorted == "T" && unique == "T") { //C(m,n) return Combination(m, n); } return 0; } //使用正则表达式将规则分拆 public string[] Detach(string rule) { string[] result = new string[4]; MatchCollection mc; Regex r = new Regex("\\w{1,3}"); mc = r.Matches(rule); for (int i = 0; i < result.Length; i++) { result[i] = mc[i].ToString(); } return result; } 5 将rules的规则按条解开
//将rules中的规则按条解开 public string[] sortByOdds(string[] rules) { string[] result1 = new string[0]; List resultList = new List (); string[] oneRule; if (rules == null || rules.Length <= 0) { //result[0] = " "; return result1; } for (int i = 0; i < rules.Length; i++) { oneRule = Cut(rules[i]);//将规则名和规则内容切开 oneRule[1] = Analysis(oneRule[1]).ToString();//将规则转换为组合数 resultList.Add(oneRule);//保存解析后的结果 } //使用冒泡法对结果进行排序 resultList = Sort(resultList); //保存结果 string[] result2 = new string[resultList.Count]; for (int i = 0; i < resultList.Count; i++) { result2[i] = resultList[i][0]; } return result2; } //使用冒泡法对结果进行排序 public List Sort(List ruleList) { if (ruleList.Count<=1) { return ruleList; } //遍历list for (int i = 0; i < ruleList.Count-1; i++) { for (int j = i+1; j < ruleList.Count; j++) { long ri = long.Parse(ruleList[i][1]); long rj = long.Parse(ruleList[j][1]); if (ri > rj)//将较小的数向前挪 { string[] rule = new string[2]; rule = ruleList[j]; ruleList[j] = ruleList[i]; ruleList[i] = rule; } else if (ri == rj)//若两数一样大，则按首字母排序。若首字母也一样，则不动 { char ci = ruleList[i][0][0]; char cj = ruleList[j][0][0]; if (ci > cj) { string[] rule = new string[2]; rule = ruleList[j]; ruleList[j] = ruleList[i]; ruleList[i] = rule; } } } } return ruleList; } 6 将规则名和规则内容切开
//将规则名和规则内容切开 public string[] Cut(string rule) { string[] result = new string[2]; int point = rule.IndexOf(':'); result[0] = rule.Substring(0, point);//规则名 result[1] = rule.Substring(point+1, rule.Length-point-1);//规则内容 return result; }