fork(1) download 
  1. //All combinations to get a number.
  2.  
  3. #include <vector>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <string>
  7. #include <sstream>
  8.  
  9. using namespace std;
  10.  
  11. typedef unsigned int uint;
  12.  
  13. vector<uint> g_summands;
  14.  
  15. typedef vector<uint> _CombinationContainer;
  16.  
  17. class Combination
  18. {
  19.     _CombinationContainer _cc;
  20.  
  21. public:
  22.     Combination(uint capacity = 0)
  23.     {
  24.         _cc.reserve(capacity);
  25.     }
  26.  
  27. public:
  28.     int Add(uint number)
  29.     {
  30.         _cc.push_back(number);
  31.         return _cc.size() - 1;
  32.     }
  33.     void Replace(_CombinationContainer::iterator pos, const Combination &c)
  34.     {
  35.         _cc.erase(pos);
  36.         _cc.insert(_cc.end(), c.begin(), c.end());
  37.         sort(_cc.begin(), _cc.end());
  38.         reverse(_cc.begin(), _cc.end());
  39.     }
  40.     uint Sum() const
  41.     {
  42.         uint r = 0;
  43.         for(_CombinationContainer::const_iterator it = _cc.begin(); it < _cc.end(); it++)
  44.         {
  45.             r += *it;
  46.         }
  47.         return r;
  48.     }
  49.     _CombinationContainer::iterator begin()
  50.     {
  51.         return _cc.begin();
  52.     }
  53.     _CombinationContainer::iterator end()
  54.     {
  55.         return _cc.end();
  56.     }
  57.     _CombinationContainer::const_iterator begin() const
  58.     {
  59.         return _cc.begin();
  60.     }
  61.     _CombinationContainer::const_iterator end() const
  62.     {
  63.         return _cc.end();
  64.     }
  65.     uint operator[](int index)
  66.     {
  67.         return _cc[index];
  68.     }
  69.     const uint operator[](int index) const
  70.     {
  71.         return _cc[index];
  72.     }
  73. };
  74.  
  75. ostream& operator <<(ostream& op1, const Combination &op2)
  76. {
  77.     bool addPlusSign = false;
  78.     for (_CombinationContainer::const_iterator it = op2.begin(); it < op2.end(); it++)
  79.     {
  80.         op1 << (addPlusSign ? " + " : (addPlusSign = true, "")) << (*it);
  81.     }
  82.     op1 << endl;
  83.     return op1;
  84. }
  85.  
  86. typedef vector<Combination> CombinationCollection;
  87.  
  88. CombinationCollection g_combinations;
  89.  
  90. //Decomposes a number in its minimum number of summands.
  91. bool DecomposeNumber(uint number, Combination &c)
  92. {
  93.     vector<uint>::const_iterator it = g_summands.begin();
  94.     while (it < g_summands.end() && (*it) >= number) it++;
  95.     if (it == g_summands.end()) return false;
  96.     uint n = number;
  97.     do
  98.     {
  99.         //cout << "DecomposeNumber n:  " << n << endl;
  100.         //cout << "DecomposeNumber (*it):  " << *it << endl;
  101.         for (uint i = 0; i < n / (*it); i++) c.Add((*it));
  102.         n -= (n / (*it)) * (*it);
  103.         it++;
  104.     } while (it < g_summands.end() && n);
  105.     /*cout << "DecomposeNumber Sum:  " << c.Sum() << endl;
  106.     if (c.Sum() == number)
  107.     {
  108.         cout << "DecomposeNumber Success:  " << c << endl;
  109.     }
  110.     else if (it >= g_summands.end())
  111.     {
  112.         cout << "DecomposeNumber Failure:  Iterator reached end of summands." << endl;
  113.     }
  114.     else
  115.     {
  116.         cout << "DecomposeNumber Failure:  " << n << endl;
  117.     }*/
  118.     return (c.Sum() == number);
  119. }
  120.  
  121. void GenerateCombinations(const Combination& c)
  122. {
  123.     uint prevNumber = 0;
  124.     for(_CombinationContainer::const_iterator it = c.begin(); it < c.end(); it++)
  125.     {
  126.         if ((*it) == prevNumber) continue;
  127.         Combination newC = c;
  128.         Combination newSubC;
  129.         if (DecomposeNumber(*it, newSubC))
  130.         {
  131.             newC.Replace(newC.begin() + std::distance(c.begin(), it), newSubC);
  132.             g_combinations.push_back(newC);
  133.             GenerateCombinations(newC);
  134.         }
  135.         prevNumber = *it;
  136.     }
  137. }
  138.  
  139. void StartGenerateCombinations(uint number)
  140. {
  141.     Combination firstC;
  142.     if (DecomposeNumber(number, firstC))
  143.     {
  144.         g_combinations.push_back(firstC);
  145.         GenerateCombinations(firstC);
  146.     }
  147. }
  148.  
  149. int main()
  150. {
  151.     cout << "Summands:  ";
  152.     string input;
  153.     getline(cin, input);
  154.     cout << input << endl;
  155.     istringstream in(input);
  156.     while (in.good())
  157.     {
  158.         uint summand;
  159.         in >> summand;
  160.         g_summands.push_back(summand);
  161.     }
  162.     sort(g_summands.begin(), g_summands.end());
  163.     reverse(g_summands.begin(), g_summands.end());
  164.     cout << "Summands input(" << g_summands.size() << "):  ";
  165.     bool addSep = false;
  166.     for (vector<uint>::const_iterator it = g_summands.begin(); it < g_summands.end(); it++)
  167.     {
  168.         cout << (addSep ? ", " : (addSep = true, "")) << (*it);
  169.     }
  170.     cout << endl;
  171.     cout << "Number to decompose:  ";
  172.     uint theNumber;
  173.     input.clear();
  174.     getline(cin, input);
  175.     cout << input << endl;
  176.     in.str(input);
  177.     in.clear();
  178.     in >> theNumber;
  179.     if (!in.fail())
  180.     {
  181.         cout << "Number input to decompose is " << theNumber << "." << endl;
  182.     }
  183.     else
  184.     {
  185.         cout << "Invalid number typed.  Correct input and try again." << endl;
  186.     }
  187.     StartGenerateCombinations(theNumber);
  188.     cout << "Total combinations:  " << g_combinations.size() << endl;
  189.     addSep = false;
  190.     for (CombinationCollection::const_iterator it = g_combinations.begin(); it < g_combinations.end(); it++)
  191.     {
  192.         cout << *it << endl;
  193.     }
  194.     return 0;
  195. }
  196.  
Success #stdin #stdout 0s 2872KB
comments (?)
stdin 
2 10
36
stdout 
Summands:  2 10
Summands input(2):  10, 2
Number to decompose:  36
Number input to decompose is 36.
Total combinations:  4
10 + 10 + 10 + 2 + 2 + 2

10 + 10 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2

10 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2

2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2
https://ideone.com/WffuF
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
secret

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!