3 partitions of equal sum

[lastchance]

Well, open to criticism now. This is what I tried for (a) back-tracking; (b) dynamic programming.

Pardon my code: I think like an engineer, not a computer scientist.

Backtracking:

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <ctime>
#include <cstdlib>
using namespace std;


//=============


vector<int> generateTest()             // Does what it says on the can
{
   // Some test vectors for debugging
// vector<int> T = { 2, 2, 3, 5 };
   vector<int> T = { 1, 2, 3, 4, 4, 5, 8 };
// vector<int> T = { 1, 1, 1, 2, 2, 2 };
// vector<int> T( 20, 12 );   T[0] = 9;

   // Or generate something random
// int SIZE = 1000;                    // Number of elements
// const int MAX = 30;                 // Maximum element value
// vector<int> T(SIZE);
// for ( int i = 0; i < SIZE; i++ ) T[i] = 1 + rand() % MAX;

   return T;
}


//=============


bool partition( int N, vector<int> &T, vector< vector<int> > &P )     // Partition T into N parts with equal sums
{
   int sumT = accumulate( T.begin(), T.end(), 0 );
   if ( sumT % N )                               // Fast check that the total actually divides by N
   {
      cout << "Not divisible by " << N << '\n';
      return false;
   }
   int sumTN = sumT / N;                         // Target size for each partition
   int Tsize = T.size();

   vector<int> sumP(N,0);                        // Sums of the partitions
   vector<int> Tpart( Tsize );                   // Partition number that each element is in

   sort( T.begin(), T.end(), []( int a, int b ){ return a > b; } );  // Reverse-sorting T eliminates impossible cases quickly

   int pos = 0;                                  // Initialise index of element in T to be placed
   int part = 0;                                 // Initialise index of partition to try to place it in.

   while ( pos < T.size() )                      // Loop round trying to place successive elements of T
   {
      int value = T[pos];                        // Value to be placed
      while( part < N )                          // Loop round the remaining untried partitions for this value
      {
         if ( sumP[part] + value <= sumTN )      // If there is room to place it in this partition ...
         {
            P[part].push_back( value );          // ... put it in that partition
            sumP[part] += value;                 // ... and update the sum
            Tpart[pos] = part;                   // ... and record which partition you've put it in
            part = 0;                            // Then for the next value to be placed, we can start again at first partition
            pos++;                               // Next position to be placed
            break;
         }
         else
         {
            part++;                              // Otherwise try next partition
         }
      }

      // If unplaced, have to BACK-TRACK by 1 and work from previous
      if ( part == N )                           // i.e. wasn't placed
      {
         pos--;                                  // So back up one position in T
         if ( pos < 0 ) return false;            // No more possibilities of placement, so impossible
         part = Tpart[pos];                      // The partition that element is currently in ...
         P[part].pop_back();                     // ... remove it
         sumP[part] -= T[pos];                   // ... and reduce that partition's sum
         part++;                                 // Try to place in NEXT partition
      }
   }

   return true;
}


//=============


template<typename T> ostream &operator << ( ostream &strm, const vector<T> &V )
{
   for ( auto e : V ) strm << e << " ";
   return strm;
}


//=============


int main()
{
   srand( time( 0 ) );                                     // Only needed for random inputs
   const int N = 3;                                        // Number of partitions

   vector<int> T = generateTest();
   cout << "Original vector: " << T << '\n';

   vector< vector<int> > P(N);

   clock_t start = clock();
   bool ok = partition( N, T, P );
   clock_t end = clock();

   if ( ok )
   {
      cout << "Partitions:\n";
      for ( auto &part : P ) cout << part << '\n';
   }
   else
   {
      cout << "Impossible\n";
   }

   cout << "Time taken = " << 1000.0 * ( end - start ) / CLOCKS_PER_SEC << " ms\n";
}


//====================================================================== 

Dynamic programming:

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <ctime>
#include <cstdlib>
using namespace std;


//=============


vector<int> generateTest()             // Does what it says on the can
{
   // Some test vectors for debugging
// vector<int> T = { 2, 2, 3, 5 };
   vector<int> T = { 1, 2, 3, 4, 4, 5, 8 };
// vector<int> T = { 1, 1, 1, 2, 2, 2 };
// vector<int> T( 20, 12 );   T[0] = 9;

   // Or generate something random
// int SIZE = 1000;                    // Number of elements
// const int MAX = 30;                 // Maximum element value
// vector<int> T(SIZE);
// for ( int i = 0; i < SIZE; i++ ) T[i] = 1 + rand() % MAX;

   return T;
}


//=============


bool isPartition( int N, const vector<int> &T, int i, vector<int> &sum, vector< vector<int> > &P )
{
   // Base case
   bool zero = true;
   for ( int e : sum )
   {
      if ( e != 0 )
      {
         zero = false;
         break;
      }
   }
   if ( zero ) return true;                      // Finished successfully


   // Recursion
   int value = T[i];                             // Value to put in some partition
   for ( int p = 0; p < N; p++ )
   {
      if ( sum[p] >= value )                     // If there is still space in the pth partition
      {
         // Try putting it into the pth partition
         sum[p] -= value;
         P[p].push_back( value );

         // Can we go forward with this in the pth partition
         if ( isPartition( N, T, i - 1, sum, P ) ) 
         {
            return true;                         // Leave it there
         }
         else
         {
            sum[p] += value;                     // Or take it out again
            P[p].pop_back();
         }
      }
   }

   return false;
}


//=============


bool partition( int N, const vector<int> &T, vector< vector<int> > &P )        // Partition T into N parts with equal sums
{
   int sumT = accumulate( T.begin(), T.end(), 0 );
   if ( sumT % N )                                                   // Fast check 
   {
      cout << "Not divisible by " << N << '\n';
      return false;
   }

   vector<int> sum( N, sumT / N );                                   // Set target sums for each of the N partitions
   return isPartition( N, T, T.size() - 1, sum, P );                 // Try to achieve this partition
}


//=============


template<typename T> ostream &operator << ( ostream &strm, const vector<T> &V )
{
   for ( auto e : V ) strm << e << " ";
   return strm;
}


//=============


int main()
{
   srand( time( 0 ) );
   const int N = 3;

   vector<int> T = generateTest();
   cout << "Original vector: " << T << '\n';

   vector< vector<int> > P(N);

   clock_t start = clock();
   bool ok = partition( N, T, P );
   clock_t end = clock();

   if ( ok )       
   {
      cout << "Partitions:\n";
      for ( auto &part : P ) cout << part << '\n';
   }
   else
   {
      cout << "Impossible\n";
   }
   cout << "Time taken = " << 1000.0 * ( end - start ) / CLOCKS_PER_SEC << " ms\n";
}

[tpb]

Your "dynamic programming" solution looks like plain old recursion. DP uses a table and tends to avoid recursion. That's where it gets its efficiency.

I tried fixing up my code and ended up breaking it, or possibly fixing it, actually, since it no longer works with your 1,1,1,2,2,2 input. I couldn't understand how it worked with that in the first place, but I'll have to look at it a little more before I can post it. I'm pretty sure it's not really a solution, though, but I'll post it anyway.

I need to crack that 3D table solution. I'm sure it's doable.

[tpb]

So my old solution was definitely not really a solution. However, I figured out the 3-partition table but it takes a ridiculous amount of memory for "large" problems (the table has about Sum*Sum*N elements, where Sum is the sum we want each partition to have and N is the number of elements in the input sequence). It seems to have a lot of symmetry, though, so I think it could be made quite a bit smaller. And instead of using vector<bool>, which may not be optimized (i.e., each bool may not be one bit), I could switch to boost::dynamic_bitset to ensure each bool is one bit (or make my own dynamic bitset).

For random problems of size N with values from 1 to High:

N   High
100  100:  0.8s
200   50:  1.5s
300   50:  4.7s
500   10:  1.1s
500   20:  3.6s

It solves the 20:1002,1:999 problem (no solution) and the 18:1002,3:999 problem (solution) in about in 3.3 seconds.

But it doesn't show the actual partitions. I haven't figured out how to extract them from the table yet, but I think it's possible.

It takes some command line arguments:

-p means print the sequence (must be first)
-s means shuffle given problem
partition [-p] N High                    # random problem
partition [-p] [-s] 1,2,3,4,4,5,8        # given problem
partition [-p] [-s] 18:1002,3:999    # given problem with multiples

Two longer runs:

$ time ./partition -s 210:102,12:99
sum: 22608    third: 7536
Solvable.

real	0m41.697s
user	0m41.068s
sys	0m0.612s


$ time ./partition -s 210:102,11:99
sum: 22509    third: 7503
No solution.

real	0m41.009s
user	0m40.396s
sys	0m0.588s

#include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <random>
#include <sstream>
#include <vector>
#include <cstdlib>

#define MAX_TABLE_MEMORY 2000000000

int main(int argc, char **argv) {
    int N = 100, High = 100; // defaults
    bool Print = false, Shuffle = false;
    std::vector<int> n(1); // alg needs a zero in first position
    int sum = 0;
    auto seed = std::chrono::high_resolution_clock::
                    now().time_since_epoch().count();
    std::default_random_engine rng(seed);

    if (argc > 1 && argv[1][0]=='-' && argv[1][1]=='p') {
        Print = true; argc--; argv++;
    }
    if (argc > 1 && argv[1][0]=='-' && argv[1][1]=='s') {
        Shuffle = true; argc--; argv++;
    }
    if (argc == 3) {
        N = std::atoi(argv[1]);
        High = std::atoi(argv[2]);
    }

    if (argc == 2) { // argv[1] contains input sequence
        N = 0;
        std::istringstream iss(argv[1]);
        int x;
        while (iss >> x) {
            char ch = '\0';
            iss >> ch;
            if (ch == ':') {
                int y;
                iss >> y;
                for (int i = 0; i < x; i++) n.push_back(y);
                N += x;
                sum += x * y;
                iss >> ch;
            }
            else {
                n.push_back(x);
                N++;
                sum += x;
            }
        }
        if (Shuffle) std::shuffle(n.begin()+1, n.end(), rng);
    }
    else { // random problem
        std::uniform_int_distribution<> dis(1, High);
        for (int i = 0; i < N; i++) {
            int x = dis(rng);
            n.push_back(x);
            sum += x;
        }
        if (sum % 3 != 0) {
            std::uniform_int_distribution<> dis(1, N);
            int i;
            if (sum % 3 == 1) { // sum is one too high
                do i = dis(rng); while (n[i] <= 1);
                --n[i];
                --sum;
            }
            else { // sum is one too low
                do i = dis(rng); while (n[i] >= High);
                ++n[i];
                ++sum;
            }
        }
    }

    if (n.size() < 3) {
        std::cout << "No solution (less than 3 elements)\n";
        return 0;
    }
    if (sum % 3 != 0) {
        std::cout << "No solution (not divisible by 3)\n";
        return 0;
    }

    if (Print) {
        for (int i = 1; i <= N; i++) std::cout << n[i] << ' ';
        std::cout << '\n';
    }

    std::cout << "sum: " << sum << "    third: " << sum / 3 << '\n';
    sum /= 3;   // this is the sum we want to achieve

    // If the 3D table is too big, bail
    if ((long long)N * sum * sum > MAX_TABLE_MEMORY) {
        std::cout << "Problem size too large\n";
        return 0;
    }

    using VB   = std::vector<bool>;
    using VVB  = std::vector<VB>;
    using VVVB = std::vector<VVB>;
    VVVB t(n.size(), VVB(sum+1, VB(sum+1)));
    for (int ni = 0; ni < int(n.size()); ni++) t[ni][0][0] = true;
    for (int ni = 1; ni < int(n.size()); ni++)
        for (int s1 = 0; s1 <= sum; s1++)
            for (int s2 = 0; s2 <= sum; s2++)
                t[ni][s1][s2] =     t[ni-1][s1]      [s2]        ||
                    (s1-n[ni]>=0 && t[ni-1][s1-n[ni]][s2]      ) ||
                    (s2-n[ni]>=0 && t[ni-1][s1]      [s2-n[ni]]);

    if (t[n.size()-1][sum][sum])
        std::cout << "Solvable.\n";
    else
        std::cout << "No solution.\n";
}

[lastchance]

You may want to look at
http://www.techiedelight.com/3-partition-problem/
It may not look like it, bcause I coded for an arbitrary N partitions, but I drew on that a lot for my second programme. It doesn't do well on the "difficult" non-partitionable problems, though.

That coder has memoised the recursion rather than using a table. I didn't do that because I couldn't work out how you would be able to store the partitions along the way.

I found that the one thing going for back-tracking (apart from its low memory and simplicity) was that neither time nor memory scaled on the sum (and hence the size of elements), whereas creating a table, as in your 2-partition method, did.

With hindsight, I could have simplified my programmes by not storing the partitions in a 2-d vector, but just a vector of which partition each index of T had gone to: the partitions could be reassembled from that later.

The link that you gave first did say that the (tabular) method had costly memory requirements when generalised to more partitions.

It's a tough problem!

[JLBorges]

> Yes I know how to solve problem partitioning vector into two

That is the hard problem; once you know how to do that:

a. Compute S, the sum of all the numbers in the vector.

If S is a multiple of 3

b. Add a new number S/3 to the original vector.
c. Partition this vector into two equal sum subsets.
d. Remove S/3 from the subset that contains it.
e. Partition the other subset into two equal sum parts.

[lastchance]

Take a vector 2,2,2,1,1,1

(a) Sum is 9

(b) Add 3 to original vector:
2,2,2,1,1,1,3

(c) Partition in two:
2,2,2 and 1,1,1,3

(d) Remove the 3
2,2,2 and 1,1,1

(e) Can't do. First partition can't be split in half. Method fails.

[JLBorges]

Right. Thank you!

[lastchance]

Combined methods. Still irritating me.

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <ctime>
#include <cstdlib>
using namespace std;

enum METHOD{ BACKTRACK, RECURSE } method = BACKTRACK;      // Solution method


//======================================================================


vector<int> generateTest()                                 // Does what it says on the can
{
   // Some test vectors for debugging
// vector<int> V = { 2, 2, 3, 5 };                         // No solution
   vector<int> V = { 1, 2, 3, 4, 4, 5, 8 };                // Solution
// vector<int> V = { 1, 1, 1, 2, 2, 2 };                   // Solution
// vector<int> V( 21, 1002 );   V[0] = 999;                // Nasty case, no solution (optimisation up)
// vector<int> V( 21, 1002 );   V[0] = V[1] = V[2] = 999;  // Balanced solution, but large array

   // Or generate something random
// const int SIZE = 100;                                   // Number of elements
// const int MAX = 30;                                     // Maximum element value
// vector<int> V(SIZE);
// for ( int i = 0; i < SIZE; i++ ) V[i] = 1 + rand() % MAX;

   return V;
}


//======================================================================
                                                                                                          

template<typename T> ostream &operator << ( ostream &strm, const vector<T> &V )   // Output a vector
{
   for ( auto e : V ) strm << e << " ";
   return strm;
}


//======================================================================


bool backtrack( int N, const vector<int> &TEST, vector<int> &remainder, vector<int> &PART )
{
   int t = 0, p = 0;                             // t = index of element in TEST, p = partition number
   while ( t < TEST.size() )                     // Loop round trying to place successive elements of TEST
   {
      int value = TEST[t];                       // Value to be placed
      while( p < N )                             // Loop round the untried partitions for this value
      {
         if ( value <= remainder[p] )            // If there is room to place it in this partition ...
         {
            remainder[p] -= value;               // ... and update the sum
            PART[t] = p;                         // ... and record which partition you've put it in
            p = 0;                               // For next value, start again at first partition
            t++;                                 // Next position to be placed
            break;
         }
         else
         {
            p++;                                 // Otherwise try next partition
         }
      }

      // If unplaced, have to BACK-TRACK by 1 and work from previous
      if ( p == N )                              // i.e. wasn't placed
      {
         t--;                                    // So back up one position in T
         if ( t < 0 ) return false;              // No more possibilities of placement, so impossible
         p = PART[t];                            // The partition that element is currently in ...
         remainder[p] += TEST[t];                // ... remove from that partition
         p++;                                    // Try to place in NEXT partition
      }
   }

   return true;
}


//======================================================================


bool recurse( int N, const vector<int> &TEST, int t, vector<int> &remainder, vector<int> &PART )
{
   // Base case
   if ( all_of( remainder.begin(), remainder.end(), []( int a ) { return a == 0; } ) ) return true;   // Successful

   // Recursion
   int value = TEST[t];                          // Value to put in some partition
   for ( int p = 0; p < N; p++ )
   {
      if ( value <= remainder[p] )               // If there is still space in the pth partition
      {
         remainder[p] -= value;
         PART[t] = p;
         if ( recurse( N, TEST, t - 1, remainder, PART ) ) return true;   // Can we go on with this choice?
         else remainder[p] += value;                                      // If not, take it out again
      }
   }

   return false;
}


//======================================================================


bool split( int N, const vector<int> &TEST, vector< vector<int> > &P )    // Divide TEST into N partitions with equal sums
{
   int sumT = accumulate( TEST.begin(), TEST.end(), 0 );
   if ( sumT % N )                               // Fast check that the total actually divides by N
   {
      cout << "Not divisible by " << N << '\n';
      return false;
   }

   vector<int> PART( TEST.size() );                        // Partition that each element of TEST is in
   vector<int> remainder( N, sumT / N );                   // Remaining margin in each partition
   bool ok;

   if ( method == BACKTRACK ) ok = backtrack( N, TEST, remainder, PART );
   else                       ok = recurse( N, TEST, TEST.size() - 1, remainder, PART );

   // Assemble all partitions from PART into 2-d array P[][]
   P.clear();
   if ( ok )
   {
      for ( int t = 0; t < TEST.size(); t++ ) P[ PART[t] ].push_back( TEST[t] );
   }

   return ok;
}


//======================================================================


int main()
{
   srand( time( 0 ) );                                     // Only needed for random inputs
   const int N = 3;                                        // Number of partitions

   vector<int> TEST = generateTest();                      // Input or generate vector to test
   cout << "Original vector: " << TEST << '\n';

   vector< vector<int> > P(N);

   clock_t start = clock();
   bool ok = split( N, TEST, P );                          // Partition it (or not)
   clock_t end = clock();

   if ( ok )
   {
      cout << "Partitions:\n";
      for ( int p = 0; p < N; p++ ) cout << P[p] << '\n';
   }
   else
   {
      cout << "Impossible\n";
   }

   cout << "Time taken = " << 1000.0 * ( end - start ) / CLOCKS_PER_SEC << " ms\n";
}


//====================================================================== 

[tpb]

Here's a version that prints the sequences and uses less memory than the 3D boolean array and runs in about half the time. I feel I've really learned something about dynamic programming from this exercise!

Timings on some random problems:

N   High   Time
100  100   0.3s
200   50   0.6s
300   50   2.1s
500   10   0.4s
500   20   1.5s
500   50   9.7s
500  200   2m 7s
1000  10   3.5s
1000 100  4m 26s

The 20:1002,1:999 problem: not solvable, 0.47s.
The 18:1002,3:999 problem: solvable, 0.47s.

And solves the 1,1,1,2,2,2 problem that stumped my original pseudo-solution.

The code could be optimized a little more (e.g., the 2D array is actually just triangular but is allocated as a full square array, so we could trade off a little extra processing to save about half the memory).

It needs to make a 2-partition pass after the 3-partition algorithm (if you ask it to print the partitions) since the 3-partition table kind of scrambles the information about which values are in which of the 2 one-third partitions that it is calculating. So all I can get out of it is the third partition that didn't go into making the table. Then I remove those values from the sequence and do a 2-partition on that to split it up. I can explain how it works if anyone is interested.

#include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <vector>
#include <cstdint>
#include <cstdlib>

// Max 2 gig table size (2-bytes per element)
const long long MAX_TABLE_ELEMENTS = 1000000000;

const uint16_t nul = -1;

int init(int argc, char **argv, std::vector<int>& n, bool& Print);

bool partition_2(std::vector<int>& n, int sum, bool Print) {
    if (sum % 2 != 0)
        return false;
    int half = sum / 2;

    std::vector<uint16_t> t(half+1, nul);
    t[0] = 0;

    for (int i = 1; i < int(n.size()); ++i)
        for (int j = 0; j <= half; ++j)
            if (t[j] < i && j + n[i] <= half && t[j+n[i]] == nul)
                t[j + n[i]] = i;

    if (t[half] == nul)
        return false;

    if (!Print)
        return true;

    std::vector<bool> b(n.size());
    int i = half;
    while (i > 0) {
        b[t[i]] = true;
        i -= n[t[i]];
    }

    int sum2 = 0;
    for (int i = 1; i < int(b.size()); i++)
        if (b[i]) {
            std::cout << n[i] << ' ';
            sum2 += n[i];
        }
    std::cout << "\nsum: " << sum2 << '\n';

    sum2 = 0;
    for (int i = 1; i < int(b.size()); i++)
        if (!b[i]) {
            std::cout << n[i] << ' ';
            sum2 += n[i];
        }
    std::cout << "\nsum: " << sum2 << '\n';

    return true;
}

bool partition_3(std::vector<int>& n, int sum, bool Print) {
    if (sum % 3 != 0)
        return false;
    int third = sum / 3;

    using VU = std::vector<uint16_t>;
    std::vector<VU> t(third+1, VU(third+1, nul));
    t[0][0] = 0;

    for (int i = 1; i < int(n.size()); ++i)
        for (int r = 0; r <= third; ++r)
            for (int c = r; c <= third; ++c) // triangular array
                if (t[r][c] < i) {
                    if (c + n[i] <= third && t[r][c + n[i]] == nul)
                        t[r][c + n[i]] = i;
                    if (r + n[i] <= c && t[r + n[i]][c] == nul)
                        t[r + n[i]][c] = i;
                }

    if (t[third][third] == nul)
        return false;

    if (!Print)
        return true;

    std::vector<bool> b(n.size());
    int r = third, c = third;
    while (r > 0 || c > 0) {
        int x = t[r][c];
        b[x] = true;
        int y = n[x];
        if (r - y >= 0 && t[r - y][c] < x)
            r -= y;
        else
            c -= y;
    }

    std::vector<int> n2{0}; // must have zero as first element
    for (int i = 1; i < int(b.size()); i++)
        if (b[i]) n2.push_back(n[i]);
    
    if (!partition_2(n2, third*2, Print))
        return false;  // shouldn't happen

    int sum2 = 0;
    for (int i = 1; i < int(b.size()); i++)
        if (!b[i]) {
            std::cout << n[i] << ' ';
            sum2 += n[i];
        }
    std::cout << "\nsum: " << sum2 << '\n';

    return true;
}

int main(int argc, char **argv) {
    bool Print = false;
    std::vector<int> n{0}; // must have zero as first element

    int sum = init(argc, argv, n, Print);

    if (Print) {
        for (int i = 1; i < int(n.size()); i++) std::cout << n[i] << ' ';
        std::cout << '\n';
    }

    std::cout << "Sum: " << sum << '\n';
    if (sum % 3 == 0)
        std::cout << "Third sum: " << sum / 3 << '\n';

    if ((long long)(sum/3) * (sum/3) > MAX_TABLE_ELEMENTS) {
        std::cout << "Problem is too big\n";
        return 0;
    }

    if (partition_3(n, sum, Print))
        std::cout << "Solvable\n";
    else
        std::cout << "No solution\n";
}

void usage() {
    std::cout <<
        "partition [-p] N High                # random problem\n"
        "partition [-p] [-s] 1,2,3,4,4,5,8    # given problem\n"
        "partition [-p] [-s] 18:1002,3:999    # given problem with multiples\n"
        "-p means print sequences\n"
        "-s means shuffle given problem\n"
        "No spaces are allowed in the given problem inputs\n";
    std::exit(0);
}

bool check_flag(int& argc, char **argv, char ch) {
    for (int i = 1; i < argc; ++i)
        if (argv[i][0]=='-' && argv[i][1]==ch && !argv[i][2]) {
            // remove from argv list
            for (int j = i; j < argc; ++j) argv[j] = argv[j+1];
            --argc;
            return true;
        }
    return false;
}

int init(int argc, char **argv, std::vector<int>& n, bool& Print) {
    int N = 100, High = 100; // defaults
    int sum = 0;
    auto seed = std::chrono::high_resolution_clock::
                    now().time_since_epoch().count();
    std::default_random_engine rng(seed);

    if (check_flag(argc, argv, '?') || check_flag(argc, argv, 'h'))
        usage();
    Print = check_flag(argc, argv, 'p');
    bool Shuffle = check_flag(argc, argv, 's');

    if (argc == 3) { //  N  High
        std::istringstream iss(argv[1]);
        if (!(iss >> N)) usage();
        iss.clear();
        iss.str(argv[2]);
        if (!(iss >> High)) usage();
    }

    if (argc == 2) { // argv[1] contains input sequence
        std::istringstream iss(argv[1]);
        int x;
        while (iss >> x) {
            char ch = '\0';
            iss >> ch;
            if (ch == ':') { // multiple where x is repetitions
                int value;
                iss >> value;
                for (int i = 0; i < x; i++) n.push_back(value);
                sum += x * value;
                iss >> ch;
            }
            else {
                n.push_back(x);
                sum += x;
            }
        }
        if (Shuffle) std::shuffle(n.begin()+1, n.end(), rng);
    }
    else { // random problem
        std::uniform_int_distribution<> dis(1, High);
        for (int i = 0; i < N; i++) {
            int x = dis(rng);
            n.push_back(x);
            sum += x;
        }
        if (sum % 3 != 0) { // ensure divisibility by 3
            std::uniform_int_distribution<> dis(1, N);
            int i;
            if (sum % 3 == 1) { // sum is one too high
                do i = dis(rng); while (n[i] <= 1);
                --n[i];
                --sum;
            }
            else { // sum is one too low
                do i = dis(rng); while (n[i] >= High);
                ++n[i];
                ++sum;
            }
        }
    }

    return sum;
}