1 #include <iostream>  2 #include <vector>  3 #include <string>  4 #include <sstream>  5 #include <algorithm>  6   7 class Lottery  8 {  9 public: 10     std::vector<std::string> sortByOdds(std::vector<std::string> rules) 11     { 12         std::vector<std::string> name; 13         std::vector<int> choice; 14         std::vector<int> blank; 15         std::vector<std::string> sorted; 16         std::vector<std::string> unique; 17         long long n[rules.size()]; 18  19         for (int i = 0; i != rules.size(); i++) { 20             int posColon = rules[i].find(":"); 21             std::string s = rules[i]; 22             std::string iName = s.substr(0,posColon); 23             std::string iPara = s.substr(posColon+2, s.size()); 24             std::cout << iPara << std::endl; 25             name.push_back(iName); 26  27             std::stringstream ss(iPara); 28             std::string buf; 29             std::vector<std::string> tokens; 30             while (ss >> buf) { 31                 tokens.push_back(buf); 32             } 33             choice.push_back(stoi(tokens[0])); 34             blank.push_back(stoi(tokens[1])); 35             sorted.push_back(tokens[2]); 36             unique.push_back(tokens[3]); 37         } 38  39         for (int i = 0; i != rules.size(); i++) { 40             n[i] = compute_odds(choice[i],blank[i],sorted[i],unique[i]); 41             std::cout << n[i] << std::endl; 42         } 43  44         sort_result(name,n); 45  46         return name; 47     } 48  49 private: 50     long long compute_odds(int n, int k, std::string s, std::string u) { 51         long long p; 52         bool isSorted = s == "T" ? true : false; 53         bool isUnique = u == "T" ? true : false; 54  55         if (isSorted && isUnique) 56             p = nchoosek(n,k); 57         else if (isSorted && !isUnique) 58             p = nchoosek(n+k-1,k); 59         else if (!isSorted && !isUnique) 60             p = pow(n,k); 61         else if (!isSorted && isUnique) 62             p = nchoosek(n,k) * factorial(k); 63  64         return p; 65     } 66  67  68     long long pow(int n, int k) { 69         long long p = 1; 70         for (int i = 1; i <= k; i++) { 71             p *= n; 72         } 73         return p; 74     } 75  76  77     long long factorial(int k) { 78         long long p = 1; 79         for (int i = 1; i <= k; i++) { 80             p *= i; 81         } 82         return p; 83     } 84  85  86     long long factorial(int n, int k) { 87         long long p = 1; 88         for (int i = n; i > n-k; i--) { 89             p *= i; 90         } 91         return p; 92     } 93  94  95     long long nchoosek(int n, int k) { 96         long long p = factorial(n,k) / factorial(k); 97         return p; 98     } 99 100 101     void sort_result(std::vector<std::string> & name, long long *n) {102         // bubble sort103         for (int i = 0; i != name.size()-1; i++) {104             bool swapped = false;105             for (int j = 0; j != name.size()-1; j++) {106                 if (n[j] > n[j+1] || (n[j] == n[j+1] && name[j] > name[j+1])) {107                     swap(name[j], name[j+1]);108                     swap(n[j], n[j+1]);109                     swapped = true;110                 }111             }112             if (swapped == false) {113                 break;114             }115         }116     }117 118     template <class T> void swap(T &a, T &b) {119         T c(a);120         a = b;121         b = c;122     }123 124 };125 126 127 int main(int argc, char** argv)128 {129     std::vector<std::string> test1;130     test1.push_back("PICK ANY TWO: 10 2 F F");131     test1.push_back("PICK TWO IN ORDER: 10 2 T F");132     test1.push_back("PICK TWO DIFFERENT: 10 2 F T");133     test1.push_back("PICK TWO LIMITED: 10 2 T T");134     std::vector<std::string> test2;135     test2.push_back("INDIGO: 93 8 T F");136     test2.push_back("ORANGE: 29 8 F T");137     test2.push_back("VIOLET: 76 6 F F");138     test2.push_back("BLUE: 100 8 T T");139     test2.push_back("RED: 99 8 T T");140     test2.push_back("GREEN: 78 6 F T");141     test2.push_back("YELLOW: 75 6 F F");142     Lottery lot;143     std::vector<std::string> res = lot.sortByOdds(test2);144 145     for (int i = 0; i != res.size(); i++) {146         std::cout << res[i] << std::endl;147     }148 149     return 0;150 }