Challenge: Partitioning a set of integers

Question

dusktreader 137 Posting Whiz in Training

14 Years Ago

I ran into this particular problem at work and found it quite interesting. While implementing a multi-level image threshholding algorithm, I discovered that I needed to find all the ways I could partition a range of integers into some number of consecutive groups. I like my solution, but there may be better approaches. Here is the problem: given some set S of consecutive integers, find all possible partitions of S into M disjoint subsets of consecutive integers such that S is covered its subsets for example:
if N=7, M=4, and S=[0,1,2,3,4,5,6], all the valid partition sets are:

[[0], [1, 2, 3], [4], [5, 6]]
[[0, 1, 2, 3], [4], [5], [6]]
[[0, 1], [2], [3, 4, 5], [6]]
[[0, 1], [2, 3], [4, 5], [6]]
[[0, 1, 2], [3], [4], [5, 6]]
[[0], [1], [2], [3, 4, 5, 6]]
[[0, 1], [2, 3, 4], [5], [6]]
[[0, 1], [2, 3], [4], [5, 6]]
[[0, 1, 2], [3], [4, 5], [6]]
[[0], [1, 2, 3, 4], [5], [6]]
[[0], [1], [2, 3, 4, 5], [6]]
[[0], [1, 2, 3], [4, 5], [6]]
[[0], [1], [2, 3], [4, 5, 6]]
[[0, 1], [2], [3], [4, 5, 6]]
[[0, 1, 2], [3, 4], [5], [6]]
[[0], [1, 2], [3, 4, 5], [6]]
[[0], [1, 2], [3, 4], [5, 6]]
[[0], [1], [2, 3, 4], [5, 6]]
[[0], [1, 2], [3], [4, 5, 6]]
[[0, 1], [2], [3, 4], [5, 6]]

Good luck!

c++

5 Contributors
16 Replies
436 Views
6 Days Discussion Span
Latest Post 14 Years Ago Latest Post by dusktreader

NathanOliver 429 Veteran Poster

14 Years Ago

I think I have made a solution to this. How would you like to see my code. I didn't know if I should post it or let others have a chance.

VernonDozier 2,218 Posting Expert

14 Years Ago

Post it as a link or an attachments rather than the code in the post, I'd say. That way anyone who wants to try it on their own before looking at yours can do so.

I have one that I created a year and a half ago. But I think the OP should post his/her solution first, again as an attachment.

NathanOliver 429 Veteran Poster

14 Years Ago

Well to start things off i have be going a little STL crazy lately. I'm having fun playing around with all the things you can do so I decided to give this an entire STL approach. There is probably a faster way but this was fun and some good practice. I hope you guys enjoy this one.

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <sys/types.h>
#include <sys/timeb.h>


using namespace std;

vector< vector< vector<int> > > MakeSubsets(vector<int>, vector< vector<int> >, int);

vector< vector<int> > CalculatePossibleSets(int, int, int, int);

vector<int> CalculatePossibleSetSizes(int, int, int);

void Print(vector< vector< vector<int> > >);

int main()
{
	_timeb start, end;
	unsigned int milliseconds, setSize, numberOfSets, maxSubSetSize, minimumSubSetSize;
	cout << "This program will find all possible subsets of consecutive numbers";
	cout <<	"\nfor a given number of sets and a given range of numbers.";
	cout << "\nPlease enter how large you want the set to be: ";
	cin >> setSize;
	cout << "Please enter the number of subsets: ";
	cin >> numberOfSets;
	cin.get();
	_ftime(&start);
	maxSubSetSize = setSize - numberOfSets + 1;
	if (setSize % numberOfSets == 0)
		minimumSubSetSize = setSize / numberOfSets;
	else
		minimumSubSetSize = (setSize / numberOfSets) + 1;
	vector<int> numberSet;
	for (int i = 0; i < setSize; i++)
		numberSet.push_back(i);
	vector< vector<int> > permutations;
	vector< vector< vector<int> > > allSubSets;
	permutations = CalculatePossibleSets(setSize, maxSubSetSize, numberOfSets, minimumSubSetSize);
	allSubSets = MakeSubsets(numberSet, permutations, numberOfSets);
	Print(allSubSets);
	_ftime(&end);
	milliseconds = (end.time * 1000 + end.millitm) - (start.time * 1000 + start.millitm);
	cout << "\nToltal time was " << milliseconds << " ms";
	cin.get();
	return 0;
}

vector< vector<int> > CalculatePossibleSets(int totalLength, int maxSubSetSize, int numberOfSets, int minimumSubSetSize)
{
	vector< vector<int> > allSets;
	vector<int> oneSet;
	while (maxSubSetSize >= minimumSubSetSize)
	{
		oneSet = CalculatePossibleSetSizes(totalLength, maxSubSetSize, numberOfSets);
		allSets.push_back(oneSet);
		while(next_permutation(oneSet.rbegin(), oneSet.rend()))
			allSets.push_back(oneSet);
		maxSubSetSize--;
	}
	return allSets;
}

vector<int> CalculatePossibleSetSizes(int totalLength, int maxSubSetSize, int numberOfSets)
{
	vector<int> set(numberOfSets);
	int currentSpot = 1, tempMaxSubSetSize, totalVectorSize = numberOfSets;
	if (totalLength % maxSubSetSize == 0)
		fill(set.begin(), set.end(), maxSubSetSize);
	set.clear();
	while (true)
	{
		set.push_back(maxSubSetSize);
		numberOfSets--;
		totalLength -= maxSubSetSize;
		if (totalLength == numberOfSets)
		{
			set.resize(totalVectorSize);
			fill(set.begin() + currentSpot, set.end(), 1);
			return set;
		}
		tempMaxSubSetSize = totalLength - numberOfSets + 1;
		if (maxSubSetSize > tempMaxSubSetSize)
			maxSubSetSize = tempMaxSubSetSize;
		currentSpot++;
	}
	return set;
}

vector< vector< vector<int> > > MakeSubsets(vector<int> set, vector< vector<int> > permutations, int numberOfSets)
{
	vector< vector< vector<int> > > allSets;
	vector< vector<int> > oneSet;
	vector<int> subSet;
	vector< vector<int> >::iterator it = permutations.begin(), end = permutations.end();
	vector<int>::const_iterator setIt, setEnd, setStop;
	while (it != end)
	{
		setIt = set.begin();
		setEnd = set.end();
		for (int i = 0; i < numberOfSets; i++)
		{
			setStop = setIt + (*it)[i];
			while (setIt != setStop)
			{
				subSet.push_back(*setIt);
				setIt++;
			}
			oneSet.push_back(subSet);
			subSet.clear();
		}
		allSets.push_back(oneSet);
		oneSet.clear();
		it++;
	}
	return allSets;
}

void Print(vector< vector< vector<int> > > allSets)
{
	int firstDSize, secondDSize, thirdDSize;
	firstDSize = allSets.size();
	secondDSize = allSets[0].size();
	for (int i = 0; i < firstDSize; i++)
	{
		cout << "[";
		for (int j = 0; j < secondDSize; j++)
		{
			thirdDSize = allSets[i][j].size();
			cout << "[";
			for (int k = 0; k < thirdDSize; k++)
			{
				cout << allSets[i][j][k];
				if (k + 1 != thirdDSize)
					cout << ",";
			}
			if (j + 1 != secondDSize)
				cout << "], ";
			else
				cout << "]";
		}
		cout << "]";
		cout << endl;
	}
}

Edited 14 Years Ago by NathanOliver because: n/a

NathanOliver 429 Veteran Poster

14 Years Ago

alright I looked into it and i forgot to add a least case scenario since my algorithm for making the sets always found the largest set to make the permutations. Now I'm running my minimum value to 2 since i already have 1 covered in the largest first set. my machine is a little old running and only has a 500 MHz processor with 640 MB ram so my total time was 120 ms with L = 7 and M = 3. I also fixed another error in my code. I forgot to have a return if the set was evenly divisible by M.
my output was

[[0,1,2,3,4], [5], [6]]
[[0], [1,2,3,4,5], [6]]
[[0], [1], [2,3,4,5,6]]
[[0,1,2,3], [4,5], [6]]
[[0,1], [2,3,4,5], [6]]
[[0,1,2,3], [4], [5,6]]
[[0], [1,2,3,4], [5,6]]
[[0,1], [2], [3,4,5,6]]
[[0], [1,2], [3,4,5,6]]
[[0,1,2], [3,4,5], [6]]
[[0,1,2], [3], [4,5,6]]
[[0], [1,2,3], [4,5,6]]
[[0,1], [2,3], [4,5,6]]
[[0,1], [2,3,4], [5,6]]
[[0,1,2], [3,4], [5,6]]

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <sys/types.h>
#include <sys/timeb.h>


using namespace std;

vector< vector< vector<int> > > MakeSubsets(vector<int>, vector< vector<int> >, int);

vector< vector<int> > CalculatePossibleSets(int, int, int, int);

vector<int> CalculatePossibleSetSizes(int, int, int);

void Print(vector< vector< vector<int> > >);

int main()
{
	_timeb start, end;
	unsigned int milliseconds, setSize, numberOfSets, maxSubSetSize, minimumSubSetSize;
	cout << "This program will find all possible subsets of consecutive numbers";
	cout <<	"\nfor a given number of sets and a given range of numbers.";
	cout << "\nPlease enter how large you want the set to be: ";
	cin >> setSize;
	cout << "Please enter the number of subsets: ";
	cin >> numberOfSets;
	cin.get();
	_ftime(&start);
	maxSubSetSize = setSize - numberOfSets + 1;
	minimumSubSetSize = 2;  // changed this to just be 2 to get all cases
	vector<int> numberSet;
	for (int i = 0; i < setSize; i++)
		numberSet.push_back(i);
	vector< vector<int> > permutations;
	vector< vector< vector<int> > > allSubSets;
	permutations = CalculatePossibleSets(setSize, maxSubSetSize, numberOfSets, minimumSubSetSize);
	allSubSets = MakeSubsets(numberSet, permutations, numberOfSets);
	Print(allSubSets);
	_ftime(&end);
	milliseconds = (end.time * 1000 + end.millitm) - (start.time * 1000 + start.millitm);
	cout << "\nTotal time was " << milliseconds << " ms";
	cin.get();
	return 0;
}

vector< vector<int> > CalculatePossibleSets(int totalLength, int maxSubSetSize, int numberOfSets, int minimumSubSetSize)
{
	vector< vector<int> > allSets;
	vector<int> oneSet;
	while (maxSubSetSize >= minimumSubSetSize)
	{
		oneSet = CalculatePossibleSetSizes(totalLength, maxSubSetSize, numberOfSets);
		allSets.push_back(oneSet);
		if (maxSubSetSize * numberOfSets >= totalLength)
			while(next_permutation(oneSet.rbegin(), oneSet.rend()))
				allSets.push_back(oneSet);
		else
			while(next_permutation(oneSet.begin(), oneSet.end()))
				allSets.push_back(oneSet);
		maxSubSetSize--;
	}
	return allSets;
}

vector<int> CalculatePossibleSetSizes(int totalLength, int maxSubSetSize, int numberOfSets)
{
	vector<int> set;
	int currentSpot = 1, tempMaxSubSetSize, totalVectorSize = numberOfSets;
	if (totalLength % maxSubSetSize == 0)
	{
		set.resize(totalVectorSize);
		fill(set.begin(), set.end(), maxSubSetSize);
		return set;   // forgot this the first time
	}
        // this part here is for sets smaller than L / M
	if (maxSubSetSize * numberOfSets < totalLength)
	{
		set.resize(totalVectorSize - 1);
		fill(set.begin(), set.end(), maxSubSetSize);
		set.push_back(totalLength - (maxSubSetSize * (numberOfSets - 1)));
		return set;
	}
	while (true)
	{
		set.push_back(maxSubSetSize);
		numberOfSets--;
		totalLength -= maxSubSetSize;
		if (totalLength == numberOfSets)
		{
			set.resize(totalVectorSize);
			fill(set.begin() + currentSpot, set.end(), 1);
			return set;
		}
		tempMaxSubSetSize = totalLength - numberOfSets + 1;
		if (maxSubSetSize > tempMaxSubSetSize)
			maxSubSetSize = tempMaxSubSetSize;
		currentSpot++;
	}
	return set;
}

vector< vector< vector<int> > > MakeSubsets(vector<int> set, vector< vector<int> > permutations, int numberOfSets)
{
	vector< vector< vector<int> > > allSets;
	vector< vector<int> > oneSet;
	vector<int> subSet;
	vector< vector<int> >::iterator it = permutations.begin(), end = permutations.end();
	vector<int>::const_iterator setIt, setEnd, setStop;
	while (it != end)
	{
		setIt = set.begin();
		setEnd = set.end();
		for (int i = 0; i < numberOfSets; i++)
		{
			setStop = setIt + (*it)[i];
			while (setIt != setStop)
			{
				subSet.push_back(*setIt);
				setIt++;
			}
			oneSet.push_back(subSet);
			subSet.clear();
		}
		allSets.push_back(oneSet);
		oneSet.clear();
		it++;
	}
	return allSets;
}

void Print(vector< vector< vector<int> > > allSets)
{
	int firstDSize, secondDSize, thirdDSize;
	firstDSize = allSets.size();
	secondDSize = allSets[0].size();
	for (int i = 0; i < firstDSize; i++)
	{
		cout << "[";
		for (int j = 0; j < secondDSize; j++)
		{
			thirdDSize = allSets[i][j].size();
			cout << "[";
			for (int k = 0; k < thirdDSize; k++)
			{
				cout << allSets[i][j][k];
				if (k + 1 != thirdDSize)
					cout << ",";
			}
			if (j + 1 != secondDSize)
				cout << "], ";
			else
				cout << "]";
		}
		cout << "]";
		cout << endl;
	}
}

if there is anything else that isn't right let me know. BTW that is a nice algorithm you have dusktreader. One thing I'm curious about is why do you use negative numbers?

Edited 14 Years Ago by NathanOliver because: added output

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

NathanOliver 429 Veteran Poster Featured Poster · Answer 1 · 2010-05-03T05:25:58+00:00

I was going to wait and see what dusktreader wants but that is a very good idea Vernon. BTW is alright if I address you as Vernon?

VernonDozier 2,218 Posting Expert Featured Poster · Answer 2 · 2010-05-03T05:59:24+00:00

I was going to wait and see what dusktreader wants but that is a very good idea Vernon. BTW is alright if I address you as Vernon?

Vern, Vernon, it's all good. No worries. It's not even my name. He's a character from the Phil Hendrie Show.

http://www.statemaster.com/encyclopedia/List-of-characters-on-The-Phil-Hendrie-Show#Vernon_Dozier

NathanOliver 429 Veteran Poster Featured Poster · Answer 3 · 2010-05-03T06:05:49+00:00

NathanOliver 429 Veteran Poster

14 Years Ago

Ah I See. Well Vernon thanks for that little tidbit.

nerdinator 0 Light Poster · Answer 4 · 2010-05-03T23:29:15+00:00

Hi.This is my program but it runs a lot of unnecessary stuff.
Please post your program.:)

#include "stdafx.h"
#include <iostream>
using namespace std;
void DoIt(int* y,int n,int m,int Level);
int _tmain(int argc, _TCHAR* argv[])
{
	cout<<"Number of elements:"<<endl;
	int n;
	cin>>n;
	cout<<"Number of sets:"<<endl;
	int m;
	cin>>m;
	int* SubSetPositions;//Holds the positions were the main set 'Set' has to split
	SubSetPositions=new int[m];
	int x;
	for(x=1;x<=m;x++)
	{
		SubSetPositions[x-1]=1;//Initialization
	}
	DoIt(SubSetPositions,n,m,m-1);
	return 0;
}


void DoIt(int* y,int n,int m,int Level)
{
	int Greatest=y[0];
	bool GoOn=true;
	for(int loop=1;loop<m;loop++)//Checks the order and decides if it is correct
	{
		if(y[loop]>Greatest)
		{
			Greatest=y[loop];
		}
		else
		{
			GoOn=false;
			break;
		}
	}
	int loop1,loop2;
	if(GoOn)//Printing part
	{
		for(loop1=0;loop1<m;loop1++)
		{
			if(loop1==0)
			{
				for(loop2=1;loop2<y[0];loop2++)
				{
					cout<<loop2;
				}
			}
			if(loop1==m-1)
			{
				for(loop2=y[loop1];loop2<=n;loop2++)
				{
					cout<<loop2;
				}
			}
			else
			{
				for(loop2=y[loop1];loop2<y[loop1+1];loop2++)
				{
					cout<<loop2;
				}
			}
			cout<<"  ";
		}
		cout<<endl;
	}
	if(y[Level]<=n)
	{
		if(Level<m-1)
		{
			y[Level]++;
			Level++;
		}
		else
		{
			y[Level]++;
		}
	}
	if(y[Level]>n)
	{
		y[Level]=1;
		if(Level>=1)
		{
			Level--;
		}
	}
	bool good=false;
	for(int loop=0;loop<m;loop++)
	{
		if(y[loop]!=n)
		{
			good=true;//It still has to continue
			break;
		}
		else
		{
			good=false;//Program is over
		}
	}
	if(good==true)
	{
		DoIt(y,n,m,Level);
	}
}

NathanOliver 429 Veteran Poster Featured Poster · Answer 5 · 2010-05-04T04:01:10+00:00

at nerdinator

do you know that you are getting multiple entries of the same disjointed set?

nerdinator 0 Light Poster · Answer 6 · 2010-05-04T13:57:22+00:00

nerdinator 0 Light Poster

14 Years Ago

Oh.Yes.I haven't taken care of that.

dusktreader 137 Posting Whiz in Training · Answer 7 · 2010-05-04T23:21:48+00:00

Go ahead and post your solution, Nathan. I'll post mine probably tomorrow

caut_baia 9 Posting Whiz · Answer 8 · 2010-05-05T03:48:03+00:00

I'm staying up tonight so .. could you cancel your post until tomorrow so i could give it a shot?:)

dusktreader 137 Posting Whiz in Training · Answer 9 · 2010-05-06T05:51:06+00:00

First, lets establish some variables. Let L be the length of the range. Let M be the number of partitions to create in the range.

The first thing I noticed in this problem is that creating M partitions requires M-1 dividers in the range. Let D be the set of dividers for a particular partitioning. The following range has been partitioned into 3 subsets, and the dividers are at index 1 and 4: { 7 8 | 9 10 11 | 12 } . The indices for the dividers must all be unique, and D > D[i-1]. Using this sort of logic, a sort of enumeration quickly appears for the possible divider indices.

Given L=7 and M=4, let's step through the possible values for D

D                   P(L)
0, 1, 2  ->  [0][1][2][3,4,5,6]
0, 1, 3  ->  [0][1][2,3][4,5,6]
...
0, 1, 5  ->  [0][1][2,3,4,5][6]

We can't increment the D[2] anymore with out making the division invalid, so, we have to increment D[1]. This of course means that D[2] must be made 1 greater than D[1] because of our original constraints.

0, 2, 3  ->  [0][1,2][3][4,5,6]
0, 2, 4  ->  [0][1,2][3,4][5,6]
0, 2, 5  ->  [0][1,2][3,4,5][6]

Again, the D[2] can't increment further so we increment D[1] again and set D[2] = D[1] + 1

0, 3, 4  ->  [0][1,2,3][4][5,6]
...
0, 4, 5  ->  [0][1,2,3,4][5][6]

Now, D[1] can't be incremented any further without invalidating the divisions, so we must increment D[0] and set D[1] = D[0] + 1 and D[2] = D[1] + 1. Now that a clear pattern is emerging, let's build and algorithm for it.

First, we need some sort of formula to tell if D cannot legally be incremented any longer. The last divider D[2] is at index M - 2. The maximum value that D[2] can take is L - 2. The maximum for D[1] = L - 3 ( one less than D[2] ). So, the maximum for D = L - M + i.

Next, we need a terminating condition. Obviously, the algorithm should stop when all of the division indices are at their maximum values. However, rather than checking all of the indices, we can take a short cut. When D[0] is at its max, D[1] = max( D[0] ) + 1. It just so happens that max( D ) = max( D[i-1] ) + 1. So, once D[0] is at its maximum value, all of the other indices are also at their maximums. This will be our terminating condition.

We are ready to write our algorithm for getting the full set of all possible division indices:

given L, M
create index list D of length M - 1
for i in range( 0, M-2 ):
    set D[i] = i
set D[M-2] = D[M-3]  # this prevents us from skipping the first D
while D[0] < L - M + 0:
    set iterator i = M - 2
    while D[i] >= L - M + i:
        decrement i
    increment( D[i] )
    while i < M - 2:
        D[i+1] = D[i] + 1
        increment i
    Add D to list of possible divisions

All of the indexing is a little confusing, but makes perfect sense when the algorithm is built incrementally. The set of all possible division indices defines the complete partitioning of the range of numbers. It is a simple matter to next interpret the division indices as subsets of integers.

Here is my exact implementation of the algorithm in c++

#include <iostream>
#include <vector>

using namespace std;

void makeDivSet( int M, int L, vector< vector< int > >& divSet )
{
    vector<int> D( M - 1 );
    for( int i=0; i<M-2; i++ )
        D[i] = i;
    D[M-2] = D[M-3];
    while( D[0] < L - M )
    {
        int i = M - 2;
        while( D[i] >= L - M + i )
            i--;
        D[i]++;
        for(; i<M-2; i++)
            D[i+1] = D[i] + 1;
        divSet.push_back( D );
    }

}

void printPartitions( const vector< vector<int> >& divSet, int elem0, int L )
{
    int M = divSet[0].size();
    vector<int> divs;
    for( unsigned int i=0; i<divSet.size(); i++ )
    {
        divs = divSet[i];
        divs.push_back( L - 1 );
        int prevDiv = -1;
        for( int j=0; j<divs.size(); j++ )
        {
            cout << "[ ";
            for( int k=prevDiv+1; k<=divs[j]; k++ )
                cout << ( elem0 + k ) << " ";
            cout << "] ";
            prevDiv = divs[j];
        }
        cout << endl;
    }
}

int main()
{
    int num0 = -3;
    int num1 = 8;
    int M = 5;
    int L = num1 - num0;
    vector< vector<int> > divSet;
    makeDivSet( M, L, divSet );
    printPartitions( divSet, num0, L );
    return 0;
}

And here is the output:

[ -3 ] [ -2 ] [ -1 ] [ 0 ] [ 1 2 3 4 5 6 7 ] 
[ -3 ] [ -2 ] [ -1 ] [ 0 1 ] [ 2 3 4 5 6 7 ] 
[ -3 ] [ -2 ] [ -1 ] [ 0 1 2 ] [ 3 4 5 6 7 ] 
[ -3 ] [ -2 ] [ -1 ] [ 0 1 2 3 ] [ 4 5 6 7 ] 
[ -3 ] [ -2 ] [ -1 ] [ 0 1 2 3 4 ] [ 5 6 7 ] 
[ -3 ] [ -2 ] [ -1 ] [ 0 1 2 3 4 5 ] [ 6 7 ] 
[ -3 ] [ -2 ] [ -1 ] [ 0 1 2 3 4 5 6 ] [ 7 ] 
[ -3 ] [ -2 ] [ -1 0 ] [ 1 ] [ 2 3 4 5 6 7 ] 
[ -3 ] [ -2 ] [ -1 0 ] [ 1 2 ] [ 3 4 5 6 7 ] 
[ -3 ] [ -2 ] [ -1 0 ] [ 1 2 3 ] [ 4 5 6 7 ] 
[ -3 ] [ -2 ] [ -1 0 ] [ 1 2 3 4 ] [ 5 6 7 ] 
[ -3 ] [ -2 ] [ -1 0 ] [ 1 2 3 4 5 ] [ 6 7 ] 
[ -3 ] [ -2 ] [ -1 0 ] [ 1 2 3 4 5 6 ] [ 7 ] 
[ -3 ] [ -2 ] [ -1 0 1 ] [ 2 ] [ 3 4 5 6 7 ] 
[ -3 ] [ -2 ] [ -1 0 1 ] [ 2 3 ] [ 4 5 6 7 ] 
[ -3 ] [ -2 ] [ -1 0 1 ] [ 2 3 4 ] [ 5 6 7 ] 
[ -3 ] [ -2 ] [ -1 0 1 ] [ 2 3 4 5 ] [ 6 7 ] 
[ -3 ] [ -2 ] [ -1 0 1 ] [ 2 3 4 5 6 ] [ 7 ] 
[ -3 ] [ -2 ] [ -1 0 1 2 ] [ 3 ] [ 4 5 6 7 ] 
[ -3 ] [ -2 ] [ -1 0 1 2 ] [ 3 4 ] [ 5 6 7 ] 
[ -3 ] [ -2 ] [ -1 0 1 2 ] [ 3 4 5 ] [ 6 7 ] 
[ -3 ] [ -2 ] [ -1 0 1 2 ] [ 3 4 5 6 ] [ 7 ] 
[ -3 ] [ -2 ] [ -1 0 1 2 3 ] [ 4 ] [ 5 6 7 ] 
[ -3 ] [ -2 ] [ -1 0 1 2 3 ] [ 4 5 ] [ 6 7 ] 
[ -3 ] [ -2 ] [ -1 0 1 2 3 ] [ 4 5 6 ] [ 7 ] 
[ -3 ] [ -2 ] [ -1 0 1 2 3 4 ] [ 5 ] [ 6 7 ] 
[ -3 ] [ -2 ] [ -1 0 1 2 3 4 ] [ 5 6 ] [ 7 ] 
[ -3 ] [ -2 ] [ -1 0 1 2 3 4 5 ] [ 6 ] [ 7 ] 
[ -3 ] [ -2 -1 ] [ 0 ] [ 1 ] [ 2 3 4 5 6 7 ] 
[ -3 ] [ -2 -1 ] [ 0 ] [ 1 2 ] [ 3 4 5 6 7 ] 
[ -3 ] [ -2 -1 ] [ 0 ] [ 1 2 3 ] [ 4 5 6 7 ] 
[ -3 ] [ -2 -1 ] [ 0 ] [ 1 2 3 4 ] [ 5 6 7 ] 
[ -3 ] [ -2 -1 ] [ 0 ] [ 1 2 3 4 5 ] [ 6 7 ] 
[ -3 ] [ -2 -1 ] [ 0 ] [ 1 2 3 4 5 6 ] [ 7 ] 
[ -3 ] [ -2 -1 ] [ 0 1 ] [ 2 ] [ 3 4 5 6 7 ] 
[ -3 ] [ -2 -1 ] [ 0 1 ] [ 2 3 ] [ 4 5 6 7 ] 
[ -3 ] [ -2 -1 ] [ 0 1 ] [ 2 3 4 ] [ 5 6 7 ] 
[ -3 ] [ -2 -1 ] [ 0 1 ] [ 2 3 4 5 ] [ 6 7 ] 
[ -3 ] [ -2 -1 ] [ 0 1 ] [ 2 3 4 5 6 ] [ 7 ] 
[ -3 ] [ -2 -1 ] [ 0 1 2 ] [ 3 ] [ 4 5 6 7 ] 
[ -3 ] [ -2 -1 ] [ 0 1 2 ] [ 3 4 ] [ 5 6 7 ] 
[ -3 ] [ -2 -1 ] [ 0 1 2 ] [ 3 4 5 ] [ 6 7 ] 
[ -3 ] [ -2 -1 ] [ 0 1 2 ] [ 3 4 5 6 ] [ 7 ] 
[ -3 ] [ -2 -1 ] [ 0 1 2 3 ] [ 4 ] [ 5 6 7 ] 
[ -3 ] [ -2 -1 ] [ 0 1 2 3 ] [ 4 5 ] [ 6 7 ] 
[ -3 ] [ -2 -1 ] [ 0 1 2 3 ] [ 4 5 6 ] [ 7 ] 
[ -3 ] [ -2 -1 ] [ 0 1 2 3 4 ] [ 5 ] [ 6 7 ] 
[ -3 ] [ -2 -1 ] [ 0 1 2 3 4 ] [ 5 6 ] [ 7 ] 
[ -3 ] [ -2 -1 ] [ 0 1 2 3 4 5 ] [ 6 ] [ 7 ] 
[ -3 ] [ -2 -1 0 ] [ 1 ] [ 2 ] [ 3 4 5 6 7 ] 
[ -3 ] [ -2 -1 0 ] [ 1 ] [ 2 3 ] [ 4 5 6 7 ] 
[ -3 ] [ -2 -1 0 ] [ 1 ] [ 2 3 4 ] [ 5 6 7 ] 
[ -3 ] [ -2 -1 0 ] [ 1 ] [ 2 3 4 5 ] [ 6 7 ] 
[ -3 ] [ -2 -1 0 ] [ 1 ] [ 2 3 4 5 6 ] [ 7 ] 
[ -3 ] [ -2 -1 0 ] [ 1 2 ] [ 3 ] [ 4 5 6 7 ] 
[ -3 ] [ -2 -1 0 ] [ 1 2 ] [ 3 4 ] [ 5 6 7 ] 
[ -3 ] [ -2 -1 0 ] [ 1 2 ] [ 3 4 5 ] [ 6 7 ] 
[ -3 ] [ -2 -1 0 ] [ 1 2 ] [ 3 4 5 6 ] [ 7 ] 
[ -3 ] [ -2 -1 0 ] [ 1 2 3 ] [ 4 ] [ 5 6 7 ] 
[ -3 ] [ -2 -1 0 ] [ 1 2 3 ] [ 4 5 ] [ 6 7 ] 
[ -3 ] [ -2 -1 0 ] [ 1 2 3 ] [ 4 5 6 ] [ 7 ] 
[ -3 ] [ -2 -1 0 ] [ 1 2 3 4 ] [ 5 ] [ 6 7 ] 
[ -3 ] [ -2 -1 0 ] [ 1 2 3 4 ] [ 5 6 ] [ 7 ] 
[ -3 ] [ -2 -1 0 ] [ 1 2 3 4 5 ] [ 6 ] [ 7 ] 
[ -3 ] [ -2 -1 0 1 ] [ 2 ] [ 3 ] [ 4 5 6 7 ] 
[ -3 ] [ -2 -1 0 1 ] [ 2 ] [ 3 4 ] [ 5 6 7 ] 
[ -3 ] [ -2 -1 0 1 ] [ 2 ] [ 3 4 5 ] [ 6 7 ] 
[ -3 ] [ -2 -1 0 1 ] [ 2 ] [ 3 4 5 6 ] [ 7 ] 
[ -3 ] [ -2 -1 0 1 ] [ 2 3 ] [ 4 ] [ 5 6 7 ] 
[ -3 ] [ -2 -1 0 1 ] [ 2 3 ] [ 4 5 ] [ 6 7 ] 
[ -3 ] [ -2 -1 0 1 ] [ 2 3 ] [ 4 5 6 ] [ 7 ] 
[ -3 ] [ -2 -1 0 1 ] [ 2 3 4 ] [ 5 ] [ 6 7 ] 
[ -3 ] [ -2 -1 0 1 ] [ 2 3 4 ] [ 5 6 ] [ 7 ] 
[ -3 ] [ -2 -1 0 1 ] [ 2 3 4 5 ] [ 6 ] [ 7 ] 
[ -3 ] [ -2 -1 0 1 2 ] [ 3 ] [ 4 ] [ 5 6 7 ] 
[ -3 ] [ -2 -1 0 1 2 ] [ 3 ] [ 4 5 ] [ 6 7 ] 
[ -3 ] [ -2 -1 0 1 2 ] [ 3 ] [ 4 5 6 ] [ 7 ] 
[ -3 ] [ -2 -1 0 1 2 ] [ 3 4 ] [ 5 ] [ 6 7 ] 
[ -3 ] [ -2 -1 0 1 2 ] [ 3 4 ] [ 5 6 ] [ 7 ] 
[ -3 ] [ -2 -1 0 1 2 ] [ 3 4 5 ] [ 6 ] [ 7 ] 
[ -3 ] [ -2 -1 0 1 2 3 ] [ 4 ] [ 5 ] [ 6 7 ] 
[ -3 ] [ -2 -1 0 1 2 3 ] [ 4 ] [ 5 6 ] [ 7 ] 
[ -3 ] [ -2 -1 0 1 2 3 ] [ 4 5 ] [ 6 ] [ 7 ] 
[ -3 ] [ -2 -1 0 1 2 3 4 ] [ 5 ] [ 6 ] [ 7 ] 
[ -3 -2 ] [ -1 ] [ 0 ] [ 1 ] [ 2 3 4 5 6 7 ] 
[ -3 -2 ] [ -1 ] [ 0 ] [ 1 2 ] [ 3 4 5 6 7 ] 
[ -3 -2 ] [ -1 ] [ 0 ] [ 1 2 3 ] [ 4 5 6 7 ] 
[ -3 -2 ] [ -1 ] [ 0 ] [ 1 2 3 4 ] [ 5 6 7 ] 
[ -3 -2 ] [ -1 ] [ 0 ] [ 1 2 3 4 5 ] [ 6 7 ] 
[ -3 -2 ] [ -1 ] [ 0 ] [ 1 2 3 4 5 6 ] [ 7 ] 
[ -3 -2 ] [ -1 ] [ 0 1 ] [ 2 ] [ 3 4 5 6 7 ] 
[ -3 -2 ] [ -1 ] [ 0 1 ] [ 2 3 ] [ 4 5 6 7 ] 
[ -3 -2 ] [ -1 ] [ 0 1 ] [ 2 3 4 ] [ 5 6 7 ] 
[ -3 -2 ] [ -1 ] [ 0 1 ] [ 2 3 4 5 ] [ 6 7 ] 
[ -3 -2 ] [ -1 ] [ 0 1 ] [ 2 3 4 5 6 ] [ 7 ] 
[ -3 -2 ] [ -1 ] [ 0 1 2 ] [ 3 ] [ 4 5 6 7 ] 
[ -3 -2 ] [ -1 ] [ 0 1 2 ] [ 3 4 ] [ 5 6 7 ] 
[ -3 -2 ] [ -1 ] [ 0 1 2 ] [ 3 4 5 ] [ 6 7 ] 
[ -3 -2 ] [ -1 ] [ 0 1 2 ] [ 3 4 5 6 ] [ 7 ] 
[ -3 -2 ] [ -1 ] [ 0 1 2 3 ] [ 4 ] [ 5 6 7 ] 
[ -3 -2 ] [ -1 ] [ 0 1 2 3 ] [ 4 5 ] [ 6 7 ] 
[ -3 -2 ] [ -1 ] [ 0 1 2 3 ] [ 4 5 6 ] [ 7 ] 
[ -3 -2 ] [ -1 ] [ 0 1 2 3 4 ] [ 5 ] [ 6 7 ] 
[ -3 -2 ] [ -1 ] [ 0 1 2 3 4 ] [ 5 6 ] [ 7 ] 
[ -3 -2 ] [ -1 ] [ 0 1 2 3 4 5 ] [ 6 ] [ 7 ] 
[ -3 -2 ] [ -1 0 ] [ 1 ] [ 2 ] [ 3 4 5 6 7 ] 
[ -3 -2 ] [ -1 0 ] [ 1 ] [ 2 3 ] [ 4 5 6 7 ] 
[ -3 -2 ] [ -1 0 ] [ 1 ] [ 2 3 4 ] [ 5 6 7 ] 
[ -3 -2 ] [ -1 0 ] [ 1 ] [ 2 3 4 5 ] [ 6 7 ] 
[ -3 -2 ] [ -1 0 ] [ 1 ] [ 2 3 4 5 6 ] [ 7 ] 
[ -3 -2 ] [ -1 0 ] [ 1 2 ] [ 3 ] [ 4 5 6 7 ] 
[ -3 -2 ] [ -1 0 ] [ 1 2 ] [ 3 4 ] [ 5 6 7 ] 
[ -3 -2 ] [ -1 0 ] [ 1 2 ] [ 3 4 5 ] [ 6 7 ] 
[ -3 -2 ] [ -1 0 ] [ 1 2 ] [ 3 4 5 6 ] [ 7 ] 
[ -3 -2 ] [ -1 0 ] [ 1 2 3 ] [ 4 ] [ 5 6 7 ] 
[ -3 -2 ] [ -1 0 ] [ 1 2 3 ] [ 4 5 ] [ 6 7 ] 
[ -3 -2 ] [ -1 0 ] [ 1 2 3 ] [ 4 5 6 ] [ 7 ] 
[ -3 -2 ] [ -1 0 ] [ 1 2 3 4 ] [ 5 ] [ 6 7 ] 
[ -3 -2 ] [ -1 0 ] [ 1 2 3 4 ] [ 5 6 ] [ 7 ] 
[ -3 -2 ] [ -1 0 ] [ 1 2 3 4 5 ] [ 6 ] [ 7 ] 
[ -3 -2 ] [ -1 0 1 ] [ 2 ] [ 3 ] [ 4 5 6 7 ] 
[ -3 -2 ] [ -1 0 1 ] [ 2 ] [ 3 4 ] [ 5 6 7 ] 
[ -3 -2 ] [ -1 0 1 ] [ 2 ] [ 3 4 5 ] [ 6 7 ] 
[ -3 -2 ] [ -1 0 1 ] [ 2 ] [ 3 4 5 6 ] [ 7 ] 
[ -3 -2 ] [ -1 0 1 ] [ 2 3 ] [ 4 ] [ 5 6 7 ] 
[ -3 -2 ] [ -1 0 1 ] [ 2 3 ] [ 4 5 ] [ 6 7 ] 
[ -3 -2 ] [ -1 0 1 ] [ 2 3 ] [ 4 5 6 ] [ 7 ] 
[ -3 -2 ] [ -1 0 1 ] [ 2 3 4 ] [ 5 ] [ 6 7 ] 
[ -3 -2 ] [ -1 0 1 ] [ 2 3 4 ] [ 5 6 ] [ 7 ] 
[ -3 -2 ] [ -1 0 1 ] [ 2 3 4 5 ] [ 6 ] [ 7 ] 
[ -3 -2 ] [ -1 0 1 2 ] [ 3 ] [ 4 ] [ 5 6 7 ] 
[ -3 -2 ] [ -1 0 1 2 ] [ 3 ] [ 4 5 ] [ 6 7 ] 
[ -3 -2 ] [ -1 0 1 2 ] [ 3 ] [ 4 5 6 ] [ 7 ] 
[ -3 -2 ] [ -1 0 1 2 ] [ 3 4 ] [ 5 ] [ 6 7 ] 
[ -3 -2 ] [ -1 0 1 2 ] [ 3 4 ] [ 5 6 ] [ 7 ] 
[ -3 -2 ] [ -1 0 1 2 ] [ 3 4 5 ] [ 6 ] [ 7 ] 
[ -3 -2 ] [ -1 0 1 2 3 ] [ 4 ] [ 5 ] [ 6 7 ] 
[ -3 -2 ] [ -1 0 1 2 3 ] [ 4 ] [ 5 6 ] [ 7 ] 
[ -3 -2 ] [ -1 0 1 2 3 ] [ 4 5 ] [ 6 ] [ 7 ] 
[ -3 -2 ] [ -1 0 1 2 3 4 ] [ 5 ] [ 6 ] [ 7 ] 
[ -3 -2 -1 ] [ 0 ] [ 1 ] [ 2 ] [ 3 4 5 6 7 ] 
[ -3 -2 -1 ] [ 0 ] [ 1 ] [ 2 3 ] [ 4 5 6 7 ] 
[ -3 -2 -1 ] [ 0 ] [ 1 ] [ 2 3 4 ] [ 5 6 7 ] 
[ -3 -2 -1 ] [ 0 ] [ 1 ] [ 2 3 4 5 ] [ 6 7 ] 
[ -3 -2 -1 ] [ 0 ] [ 1 ] [ 2 3 4 5 6 ] [ 7 ] 
[ -3 -2 -1 ] [ 0 ] [ 1 2 ] [ 3 ] [ 4 5 6 7 ] 
[ -3 -2 -1 ] [ 0 ] [ 1 2 ] [ 3 4 ] [ 5 6 7 ] 
[ -3 -2 -1 ] [ 0 ] [ 1 2 ] [ 3 4 5 ] [ 6 7 ] 
[ -3 -2 -1 ] [ 0 ] [ 1 2 ] [ 3 4 5 6 ] [ 7 ] 
[ -3 -2 -1 ] [ 0 ] [ 1 2 3 ] [ 4 ] [ 5 6 7 ] 
[ -3 -2 -1 ] [ 0 ] [ 1 2 3 ] [ 4 5 ] [ 6 7 ] 
[ -3 -2 -1 ] [ 0 ] [ 1 2 3 ] [ 4 5 6 ] [ 7 ] 
[ -3 -2 -1 ] [ 0 ] [ 1 2 3 4 ] [ 5 ] [ 6 7 ] 
[ -3 -2 -1 ] [ 0 ] [ 1 2 3 4 ] [ 5 6 ] [ 7 ] 
[ -3 -2 -1 ] [ 0 ] [ 1 2 3 4 5 ] [ 6 ] [ 7 ] 
[ -3 -2 -1 ] [ 0 1 ] [ 2 ] [ 3 ] [ 4 5 6 7 ] 
[ -3 -2 -1 ] [ 0 1 ] [ 2 ] [ 3 4 ] [ 5 6 7 ] 
[ -3 -2 -1 ] [ 0 1 ] [ 2 ] [ 3 4 5 ] [ 6 7 ] 
[ -3 -2 -1 ] [ 0 1 ] [ 2 ] [ 3 4 5 6 ] [ 7 ] 
[ -3 -2 -1 ] [ 0 1 ] [ 2 3 ] [ 4 ] [ 5 6 7 ] 
[ -3 -2 -1 ] [ 0 1 ] [ 2 3 ] [ 4 5 ] [ 6 7 ] 
[ -3 -2 -1 ] [ 0 1 ] [ 2 3 ] [ 4 5 6 ] [ 7 ] 
[ -3 -2 -1 ] [ 0 1 ] [ 2 3 4 ] [ 5 ] [ 6 7 ] 
[ -3 -2 -1 ] [ 0 1 ] [ 2 3 4 ] [ 5 6 ] [ 7 ] 
[ -3 -2 -1 ] [ 0 1 ] [ 2 3 4 5 ] [ 6 ] [ 7 ] 
[ -3 -2 -1 ] [ 0 1 2 ] [ 3 ] [ 4 ] [ 5 6 7 ] 
[ -3 -2 -1 ] [ 0 1 2 ] [ 3 ] [ 4 5 ] [ 6 7 ] 
[ -3 -2 -1 ] [ 0 1 2 ] [ 3 ] [ 4 5 6 ] [ 7 ] 
[ -3 -2 -1 ] [ 0 1 2 ] [ 3 4 ] [ 5 ] [ 6 7 ] 
[ -3 -2 -1 ] [ 0 1 2 ] [ 3 4 ] [ 5 6 ] [ 7 ] 
[ -3 -2 -1 ] [ 0 1 2 ] [ 3 4 5 ] [ 6 ] [ 7 ] 
[ -3 -2 -1 ] [ 0 1 2 3 ] [ 4 ] [ 5 ] [ 6 7 ] 
[ -3 -2 -1 ] [ 0 1 2 3 ] [ 4 ] [ 5 6 ] [ 7 ] 
[ -3 -2 -1 ] [ 0 1 2 3 ] [ 4 5 ] [ 6 ] [ 7 ] 
[ -3 -2 -1 ] [ 0 1 2 3 4 ] [ 5 ] [ 6 ] [ 7 ] 
[ -3 -2 -1 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 5 6 7 ] 
[ -3 -2 -1 0 ] [ 1 ] [ 2 ] [ 3 4 ] [ 5 6 7 ] 
[ -3 -2 -1 0 ] [ 1 ] [ 2 ] [ 3 4 5 ] [ 6 7 ] 
[ -3 -2 -1 0 ] [ 1 ] [ 2 ] [ 3 4 5 6 ] [ 7 ] 
[ -3 -2 -1 0 ] [ 1 ] [ 2 3 ] [ 4 ] [ 5 6 7 ] 
[ -3 -2 -1 0 ] [ 1 ] [ 2 3 ] [ 4 5 ] [ 6 7 ] 
[ -3 -2 -1 0 ] [ 1 ] [ 2 3 ] [ 4 5 6 ] [ 7 ] 
[ -3 -2 -1 0 ] [ 1 ] [ 2 3 4 ] [ 5 ] [ 6 7 ] 
[ -3 -2 -1 0 ] [ 1 ] [ 2 3 4 ] [ 5 6 ] [ 7 ] 
[ -3 -2 -1 0 ] [ 1 ] [ 2 3 4 5 ] [ 6 ] [ 7 ] 
[ -3 -2 -1 0 ] [ 1 2 ] [ 3 ] [ 4 ] [ 5 6 7 ] 
[ -3 -2 -1 0 ] [ 1 2 ] [ 3 ] [ 4 5 ] [ 6 7 ] 
[ -3 -2 -1 0 ] [ 1 2 ] [ 3 ] [ 4 5 6 ] [ 7 ] 
[ -3 -2 -1 0 ] [ 1 2 ] [ 3 4 ] [ 5 ] [ 6 7 ] 
[ -3 -2 -1 0 ] [ 1 2 ] [ 3 4 ] [ 5 6 ] [ 7 ] 
[ -3 -2 -1 0 ] [ 1 2 ] [ 3 4 5 ] [ 6 ] [ 7 ] 
[ -3 -2 -1 0 ] [ 1 2 3 ] [ 4 ] [ 5 ] [ 6 7 ] 
[ -3 -2 -1 0 ] [ 1 2 3 ] [ 4 ] [ 5 6 ] [ 7 ] 
[ -3 -2 -1 0 ] [ 1 2 3 ] [ 4 5 ] [ 6 ] [ 7 ] 
[ -3 -2 -1 0 ] [ 1 2 3 4 ] [ 5 ] [ 6 ] [ 7 ] 
[ -3 -2 -1 0 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 6 7 ] 
[ -3 -2 -1 0 1 ] [ 2 ] [ 3 ] [ 4 5 ] [ 6 7 ] 
[ -3 -2 -1 0 1 ] [ 2 ] [ 3 ] [ 4 5 6 ] [ 7 ] 
[ -3 -2 -1 0 1 ] [ 2 ] [ 3 4 ] [ 5 ] [ 6 7 ] 
[ -3 -2 -1 0 1 ] [ 2 ] [ 3 4 ] [ 5 6 ] [ 7 ] 
[ -3 -2 -1 0 1 ] [ 2 ] [ 3 4 5 ] [ 6 ] [ 7 ] 
[ -3 -2 -1 0 1 ] [ 2 3 ] [ 4 ] [ 5 ] [ 6 7 ] 
[ -3 -2 -1 0 1 ] [ 2 3 ] [ 4 ] [ 5 6 ] [ 7 ] 
[ -3 -2 -1 0 1 ] [ 2 3 ] [ 4 5 ] [ 6 ] [ 7 ] 
[ -3 -2 -1 0 1 ] [ 2 3 4 ] [ 5 ] [ 6 ] [ 7 ] 
[ -3 -2 -1 0 1 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 7 ] 
[ -3 -2 -1 0 1 2 ] [ 3 ] [ 4 ] [ 5 6 ] [ 7 ] 
[ -3 -2 -1 0 1 2 ] [ 3 ] [ 4 5 ] [ 6 ] [ 7 ] 
[ -3 -2 -1 0 1 2 ] [ 3 4 ] [ 5 ] [ 6 ] [ 7 ] 
[ -3 -2 -1 0 1 2 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ]

dusktreader 137 Posting Whiz in Training · Answer 10 · 2010-05-06T06:33:21+00:00

Well to start things off i have be going a little STL crazy lately. I'm having fun playing around with all the things you can do so I decided to give this an entire STL approach. There is probably a faster way but this was fun and some good practice. I hope you guys enjoy this one.

You almost got it, Nathan. In fact, I was convinced you did have it until I ran your code on a large set. I use this algorithm to do Multi-level Otsu thresholding on grayscale images, so my set is (usually) 256 elements. Running your code on 256 elements with 4 divisions ran in 7 ms while mine took 400. I was impressed, but a little suspicious. It turned out that your program was finding 2087 partitions while mine found 2731135. So, I ran them again side by side on a 7 element set with 3 partitions and compared the results. It appears you are missing a few of the possible partitionings. Here is the comparison

dusktreader's implementation:
found 15 possible partitionings
[ 0 ] [ 1 ] [ 2 3 4 5 6 ] 
[ 0 ] [ 1 2 ] [ 3 4 5 6 ] 
[ 0 ] [ 1 2 3 ] [ 4 5 6 ] 
[ 0 ] [ 1 2 3 4 ] [ 5 6 ] 
[ 0 ] [ 1 2 3 4 5 ] [ 6 ] 
[ 0 1 ] [ 2 ] [ 3 4 5 6 ] 
[ 0 1 ] [ 2 3 ] [ 4 5 6 ] 
[ 0 1 ] [ 2 3 4 ] [ 5 6 ] 
[ 0 1 ] [ 2 3 4 5 ] [ 6 ] 
[ 0 1 2 ] [ 3 ] [ 4 5 6 ] 
[ 0 1 2 ] [ 3 4 ] [ 5 6 ] 
[ 0 1 2 ] [ 3 4 5 ] [ 6 ] 
[ 0 1 2 3 ] [ 4 ] [ 5 6 ] 
[ 0 1 2 3 ] [ 4 5 ] [ 6 ] 
[ 0 1 2 3 4 ] [ 5 ] [ 6 ] 

nathan's implementation
found 12 possible partitionings
[[0,1,2,3,4], [5], [6]]
[[0], [1,2,3,4,5], [6]]
[[0], [1], [2,3,4,5,6]]
[[0,1,2,3], [4,5], [6]]
[[0,1], [2,3,4,5], [6]]
[[0,1,2,3], [4], [5,6]]
[[0], [1,2,3,4], [5,6]]
[[0,1], [2], [3,4,5,6]]
[[0], [1,2], [3,4,5,6]]
[[0,1,2], [3,4,5], [6]]
[[0,1,2], [3], [4,5,6]]
[[0], [1,2,3], [4,5,6]]

It looks like the trouble comes when the partitions are nearly equal.

dusktreader 137 Posting Whiz in Training · Answer 11 · 2010-05-06T23:55:09+00:00

alright I looked into it and i forgot to add a least case scenario since my algorithm for making the sets always found the largest set to make the permutations. Now I'm running my minimum value to 2 since i already have 1 covered in the largest first set. my machine is a little old running and only has a 500 MHz processor with 640 MB ram so my total time was 120 ms with L = 7 and M = 3. I also fixed another error in my code. I forgot to have a return if the set was evenly divisible by M.
my output was
[[0,1,2,3,4], [5], [6]]
[[0], [1,2,3,4,5], [6]]
[[0], [1], [2,3,4,5,6]]
[[0,1,2,3], [4,5], [6]]
[[0,1], [2,3,4,5], [6]]
[[0,1,2,3], [4], [5,6]]
[[0], [1,2,3,4], [5,6]]
[[0,1], [2], [3,4,5,6]]
[[0], [1,2], [3,4,5,6]]
[[0,1,2], [3,4,5], [6]]
[[0,1,2], [3], [4,5,6]]
[[0], [1,2,3], [4,5,6]]
[[0,1], [2,3], [4,5,6]]
[[0,1], [2,3,4], [5,6]]
[[0,1,2], [3,4], [5,6]]
if there is anything else that isn't right let me know. BTW that is a nice algorithm you have dusktreader. One thing I'm curious about is why do you use negative numbers?

It looks like you have it correct now.

The reason I used negative numbers in my example was because I specified in my original description that the algorithm should partition any range of integers. Of course, you only need to do the partitioning from 0 to L and then offset all the numbers in the partitions by i0 where i0 is the first integer in the range. I just used a set spanning zero to demonstrate that it worked according to my original description. In practice I would never use negative numbers, and the range would always be a subset of [0..256).

dusktreader 137 Posting Whiz in Training · Answer 12 · 2010-05-07T00:07:17+00:00

Hi.This is my program but it runs a lot of unnecessary stuff.
Please post your program.:)

You are very close with your implementation. As far as I can tell, your algorithm prints out all possible partition schemes for the range. However, it prints a lot of redundant copies of many of the partitioned subsets.

For example, I ran your code against the same set I tested Nathan's with and got the following output with 35 partitioning schemes:
L = 7, M = 4

1  2  34567  
1  23  4567  
1  234  567  
1  2345  67  
1  23456  7  
12  3  4567  
12  34  567  
12  345  67  
12  3456  7  
123  4  567  
123  45  67  
123  456  7  
1234  5  67  
1234  56  7  
12345  6  7  
12  3  4567  
12  34  567  
12  345  67  
12  3456  7  
123  4  567  
123  45  67  
123  456  7  
1234  5  67  
1234  56  7  
12345  6  7  
123  4  567  
123  45  67  
123  456  7  
1234  5  67  
1234  56  7  
12345  6  7  
1234  5  67  
1234  56  7  
12345  6  7  
12345  6  7

There are only 15 possible partition schemes, and you can see from the output above that there are many duplicate lines.