Algorithms

DQNOK wrote:

which of course requires a small $ outlay

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

template <class BidirectionalIterator>
bool next_combination(BidirectionalIterator first,
                      BidirectionalIterator k,
                      BidirectionalIterator last);

int main()
{

   std::vector<int> v;
   v.push_back(7);
   v.push_back(8);
   v.push_back(12);
   v.push_back(3);
   v.push_back(4);

   int target = 15;
   int combination_count = 0;

   std::sort(v.begin(),v.end());

   for(unsigned int i = 1; i <= v.size(); ++i)
   {
      std::vector<int> tmp;
      std::copy(v.begin(),v.end(),std::back_inserter(tmp));
      do
      {
         if (std::accumulate(tmp.begin(),tmp.begin() + i, 0) == target)
         {
            std::cout << ++combination_count << "] ";
            for(unsigned int j = 0; j < i; ++j)
            {
               std::cout << tmp[j] << (j < (i-1) ? "+" : "\n");
            }
         }
      }
      while(next_combination(tmp.begin(),tmp.begin() + i,tmp.end()));
   }

   if (0 == combination_count)
   {
      std::cout << "No combinations found." < std::endl;
   }
   return 0;
}


/*
   Credits: Mark Nelson http://marknelson.us/
*/
template <class BidirectionalIterator>
bool next_combination(BidirectionalIterator first,
                      BidirectionalIterator k,
                      BidirectionalIterator last)
{
   if ((first == last) || (k == first) || (k == last)) return false;
   BidirectionalIterator i = first;
   BidirectionalIterator ii = last;
   ++i;
   if (i == last) return false;
   i = last;
   --i;

   i = k;
   --ii;
   while (i != first)
   {
      if (*--i < *ii)
      { // Search down to find first comb entry less than final entry
         BidirectionalIterator j = k;
         while(!(*i < *j)) j++; // Find swap position [good-1-high|good-2-low]
         iter_swap(i,j); // Swap [good-2-high|good-1-low]
         i++;j++;ii=k; // Move to rotation positions
         rotate(i,j,last); // Rotate [good-2-low-high-good-1]
         while(j!=last){ ++j; ++ii;} // Find high good position
         rotate(k,ii,last); // Rotate [good-2-(low/high>|good-1-<low/high)]
         return true;
      }
   }
   rotate (first,k,last);
   return false;
}

    class SubsetSummer<br />
    {<br />
        static IEnumerable< long> SubsetSumCore(IList< int> values, int target)<br />
        {<br />
            long mask = (1 << values.Count);<br />
<br />
            while(mask-- > 0)<br />
            {<br />
                int total = 0;<br />
                for(int bit = 0; bit< values.Count; bit++)<br />
                {<br />
                    if ((mask & 1 << bit) > 0) total += values[bit];<br />
                }<br />
                   <br />
                if (total == target) yield return mask;<br />
            }<br />
        }<br />
<br />
        static IEnumerable< List< int>> SubsetSum(IList< int> values, int target)<br />
        {<br />
            foreach (var resultMask in SubsetSumCore(values,target))<br />
            {<br />
                var results = new List< int>();<br />
                for (int bit = 0; bit < values.Count; bit++)<br />
                {<br />
                    if ((resultMask & 1 << bit) > 0) results.Add(values[bit]);<br />
                }<br />
                yield return results;<br />
            }<br />
        }<br />
<br />
        static void Main(string[] args)<br />
        {<br />
            var values = new []{7, 8, 12, 3, 4};<br />
<br />
            foreach (var result in SubsetSum(values, 15))<br />
            {<br />
                Console.WriteLine(string.Join(" + ", result.ConvertAll(i => i.ToString()).ToArray()));<br />
            }<br />
        }<br />
    }

class SubsetSummer
{
   static void Main(string[] args)
   {
      Console.WriteLine("3 + 4 + 8");
      Console.WriteLine("3 + 12");
      Console.WriteLine("7 + 8");
   }
}

softdev_sup wrote:

any Suggestion