Paid Job: Seeking recursion expert

Community Forums/General Help/Paid Job: Seeking recursion expert

AarbronBeast

(Posted 2011) [#1]

Hi guys.

I am looking for someone to write me an algorithm that solves the problem below. I will be able to pay a nominal amount (of money) for a program that completely and efficiently solves the problem correctly. Could use this today or tomorrow. Any takers?

I am looking for an algorithm that solve the following problem (please read carefully as this isn't your typical straightforward combination logic):

Given a set of unique items, write an algorithm that walks through all of the possible combinations of GROUPS of items, avoiding duplicate groups and duplicate items.

For example: A set of 5 items can be grouped as follows:
1 group of 5 items
1 group of 1 item + 1 group of 4 items
1 group of 2 items + 1 group of 3 items
2 groups of 1 item + 1 group of 3 items
2 groups of 2 items + 1 group of 1 item
3 groups of 1 item + 1 group of 2 items
5 groups of 1 item

(I think I listed them all. It gets a lot more complicated the more items you have.)

Knowing the complete set of possible groupings, the final output should look like this (given items A, B, C, D and E):

-1 GROUP
[ABCDE] 

-2 GROUPS
[A] [BCDE]
[B] [ACDE]
[C] [ABDE]
[D] [ABCE]
[E] [ABCD]
[AB] [CDE]
[AC] [BDE]
[AD] [BCE]
and so on…

-3 GROUPS
[A] [B] [CDE] 
[A] [C] [BDE]
[A] [D] [BCE]
and so on…

-4 GROUPS
[A] [B] [C] [DE] 
[A] [B] [D] [CE]
[A] [B] [E] [CD]
and so on…

-5 GROUPS
[A] [B] [C] [D] [E]

<end>

Requirements:
1) The number of group sections will always equal the total number of items.
2) Must use EACH of the items in the set ONCE for each row of data. (i.e. No duplicate items.)
3) A row of data should not exist on another row in the same section with a different group order (for example, [A] [BCDE] and [BCDE] [A] are the same and need to be avoided.)
4) Likewise, items within a data row's grouping should not be duplicated on a different row within a section out of sequence. (meaning [A] [BCDE] and [A] [DCBE] are the same, and need to be avoided.)
5) Recursion is probably the best way to solve this, but please avoid using any sort of outside libraries or uncommon functions. The logic should be written by using only the core language elements (arrays, variables, conditionals, loops, subroutines, etc…)
6) Can be programmed in BlitzMax, or any other "easily readable language" so that it can be translated to other languages without too much hassle. The program must be able to output the results to prove it works.

I spent more than enough time on it already, and I couldn't figure out a good way to do it. If you are interested in getting paid for your work, please check with me first for authorization.

Anyone want the job?

slenkar

(Posted 2011) [#2]

I have done stuff similar to this before, I could take a go,
If I find I cant do it you dont have to pay me of course

AarbronBeast

(Posted 2011) [#3]

Thanks, slenkar. How long do you think it'll take you to figure something out?

Floyd

(Posted 2011) [#4]

Mathematically this problem is "generate all partitions of a set of size n". You can find plenty of algorithms online.

The number of partitions is called the Bell Numbers and grows exponentially. By n=16 it is over a billion.

So I hope you don't need this for anything but very small n.

Last edited 2011

AarbronBeast

(Posted 2011) [#5]

Thanks, Floyd. I didn't know what this math subject was called, so I was unable to find anything. I'll have a look. Billions sounds like a lot, and it's certainly possible that I'll have lots more than 16 items. I might have to think of a different way to approach the problem.

slenkar, maybe you can hold off. I might be able to make sense of the algorithms online or change my mind altogether.

Last edited 2011

Last edited 2011

Floyd

(Posted 2011) [#6]

Here's some c code, which I got from http://compprog.wordpress.com/2007/10/15/generating-the-partitions-of-a-set/
I changed it slightly to get better looking output in BlitzMax.

If you have BlitzMax, and MingW set up to work with it, then you can run this directly from the IDE.

1. Create a new file.
2. Save it as partitions.c, so the IDE knows it is c code.
3. Paste in the code given below.
4. Build and Run.

#include <stdio.h>

/*
	printp
		- print out the partitioning scheme s of n elements 
		as: {1, 2, 4} {3}
*/
void printp(int *s, int n) {
	/* Get the total number of partitions. In the exemple above, 2.*/
	int part_num = 1;
	int i;
	for (i = 0; i < n; ++i)
		if (s[i] > part_num)
			part_num = s[i];

	/* Print the p partitions. */
	int p;
	for (p = part_num; p >= 1; --p) {
		printf("{");
		/* If s[i] == p, then i + 1 is part of the pth partition. */
		for (i = 0; i < n; ++i)
			if (s[i] == p)
				printf("%d ", i + 1);
		printf("} ");
	}
	printf("\n");
}

/*
	next
		- given the partitioning scheme represented by s and m, generate
		the next

	Returns: 1, if a valid partitioning was found
		0, otherwise
*/
int next(int *s, int *m, int n) {
	/* Update s: 1 1 1 1 -> 2 1 1 1 -> 1 2 1 1 -> 2 2 1 1 -> 3 2 1 1 ->
	1 1 2 1 ... */
	/*int j;
	printf(" -> (");
	for (j = 0; j < n; ++j)
		printf("%d, ", s[j]);
	printf(")\n");*/
	int i = 0;
	++s[i];
	while ((i < n - 1) && (s[i] > m[i] + 1)) {
		s[i] = 1;
		++i;
		++s[i];
	}

	/* If i is has reached n-1 th element, then the last unique partitiong
	has been found*/
	if (i == n - 1)
		return 0;

	/* Because all the first i elements are now 1, s[i] (i + 1 th element)
	is the largest. So we update max by copying it to all the first i
	positions in m.*/
	int max = s[i];
	for (i = i - 1; i >= 0; --i)
		m[i] = max;

/*	for (i = 0; i < n; ++i)
		printf("%d ", m[i]);
	getchar();*/
	return 1;
}

int main(int argc, char *argv[]) {
	int s[16]; /* s[i] is the number of the set in which the ith element
			should go */
	int m[16]; /* m[i] is the largest of the first i elements in s*/

	int n = 3;
	int i;
	/* The first way to partition a set is to put all the elements in the same
	   subset. */
	for (i = 0; i < n; ++i) {
		s[i] = 1;
		m[i] = 1;
	}

	/* Print the first partitioning. */
	printp(s, n);

	/* Print the other partitioning schemes. */
	while (next(s, m, n))
		printp(s, n);

	return 0;
}

Last edited 2011

AarbronBeast

(Posted 2011) [#7]

Thanks, Floyd. I don't have MinGW installed, but I found a post with instructions on how to do that. I'll be checking it out tonight. You're a gem.

Shortwind

(Posted 2011) [#8]

Please be aware that there is bug in the above code. After line 61 you need to add:

if (m[i] > max) max = m[i];

(This part of the code.....)

/* Because all the first i elements are now 1, s[i] (i + 1 th element)
is the largest. So we update max by copying it to all the first i
positions in m.*/
int max = s[i];
if (m[i] > max) max = m[i]; /*----------< Add this line */
for (i = i - 1; i >= 0; --i)
m[i] = max;

What your looking for is indeed the bell numbers. So starting at n=5 the code starts missing good sets. If uncorrected n=5 results in 51 instead of 52 sets. n=6 results in 188 instead of 203, so for and so on.

http://compprog.wordpress.com/2007/10/15/generating-the-partitions-of-a-set/

Floyd

(Posted 2011) [#9]

Thanks for this. It figures it would go wrong at n=5. I tried n=3 and n=4 and it looked fine.
I could have looked a little more thoroughly, or at least scrolled down the page where I got the code!

Here's an updated version, with line numbers added to the output. It gets 52 partitions for n=5.

#include <stdio.h>

/*
	printp
		- print out the partitioning scheme s of n elements 
		as: {1, 2, 4} {3}
*/
void printp(int *s, int n) {
	/* Get the total number of partitions. In the exemple above, 2.*/
	int part_num = 1;
	int i;
	for (i = 0; i < n; ++i)
		if (s[i] > part_num)
			part_num = s[i];

	/* Print the p partitions. */
	static int count;
	printf( "%10d: ", ++count );
	int p;
	for (p = part_num; p >= 1; --p) {
		printf("{");
		/* If s[i] == p, then i + 1 is part of the pth partition. */
		for (i = 0; i < n; ++i)
			if (s[i] == p)
				printf("%d ", i + 1);
		printf("} ");
	}
	printf("\n");
}

/*
	next
		- given the partitioning scheme represented by s and m, generate
		the next

	Returns: 1, if a valid partitioning was found
		0, otherwise
*/
int next(int *s, int *m, int n) {
	/* Update s: 1 1 1 1 -> 2 1 1 1 -> 1 2 1 1 -> 2 2 1 1 -> 3 2 1 1 ->
	1 1 2 1 ... */
	/*int j;
	printf(" -> (");
	for (j = 0; j < n; ++j)
		printf("%d, ", s[j]);
	printf(")\n");*/
	int i = 0;
	++s[i];
	while ((i < n - 1) && (s[i] > m[i] + 1)) {
		s[i] = 1;
		++i;
		++s[i];
	}

	/* If i is has reached n-1 th element, then the last unique partitiong
	has been found*/
	if (i == n - 1)
		return 0;

	/* Because all the first i elements are now 1, s[i] (i + 1 th element)
	is the largest. So we update max by copying it to all the first i
	positions in m.*/
	int max = s[i];
   if (m[i] > max) max = m[i];     /* missing in original code!  */
	for (i = i - 1; i >= 0; --i)
		m[i] = max;

/*	for (i = 0; i < n; ++i)
		printf("%d ", m[i]);
	getchar();*/
	return 1;
}

int main(int argc, char *argv[]) {
	int s[16]; /* s[i] is the number of the set in which the ith element
			should go */
	int m[16]; /* m[i] is the largest of the first i elements in s*/

	int n = 5;
	int i;
	/* The first way to partition a set is to put all the elements in the same
	   subset. */
	for (i = 0; i < n; ++i) {
		s[i] = 1;
		m[i] = 1;
	}

	/* Print the first partitioning. */
	printp(s, n);

	/* Print the other partitioning schemes. */
	while (next(s, m, n))
		printp(s, n);

	return 0;
}

Last edited 2011

AarbronBeast

(Posted 2011) [#10]

Ok, I just installed MinGW and tried out the code. Yup. That seems to be exactly what I was looking for. Many thanks.

Bobysait

(Posted 2011) [#11]

same code in blitz3d

Function printp(s[16],n)
	Local txt$="", pn=1
	For i=0 To n-1
		If s[i]>pn Then pn=s[i]
	Next
	For p = pn To 1 Step -1
		txt=txt+"{"
		For i=0 To n-1
			If s[i]=p Then txt=txt+Str(i+1)
		Next
		txt=txt+"} "
	Next
	Print txt
End Function

Function Next_(s[16], m[16], n)
	s[0]=s[0]+1
	While i<n-1 And s[i]>m[i]+1
		s[i]=1
		i=i+1
		s[i]=s[i]+1
	Wend
	If (i=n-1) Then Return 0
	max=s[i]
	If m[i]>max Then max=m[i]
	For j=i-1 To 0 Step -1
		m[j]=max
	Next
	Return 1
End Function

Local s[16], m[16], n=4

For i=0 To n-1
	s[i]=1
	m[i]=1
Next

printp(s,n)
While (Next_(s, m,n))
	printp(s,n)
Wend

WaitKey
End

bluemoon

(Posted 2013) [#12]

I know this is 2 years ago but someone may find this useful. It produces all the combination between 1 and 1023, i.e upto 10 items.

Type Combination
		Field strRep$
		Field number%
		Field size%
	End Type
	
	Dim combination.Combination(1023)
	
	For x = 1 To 1023
		combination(x) = New Combination
		combination(x)\strRep$=comBuilder$(x)                 ;string representation of the combination.
		combination(x)\number%=x                              ;is the number that builds the combination
		combination(x)\size=Len((combination(x)\strRep$)+1)/2 ;number of objects in the combination
	Next 
	
	For x = 1 To 15
		DebugLog "No "+Str$(x)+"...."+combination(x)\strRep$+ " size = "+Str$(combination(x)\size%)
	Next	
	
	WaitKey()
	End
	
	;builds a string rep of a combination
	;comma delimeter.	
	Function comBuilder$(n)
		
		nRep=n
		
		Repeat
		If nRep Mod 2 = 1 Then 
			count=count+1
			s$=s$+Str$(count)
			s$=s$+","	
			Else
			count=count+1
		End If
		
		nRep=nRep/2
		Until nRep = 0
		
		Return Left$(s$,Len(s$)-1) ;return string without the last comma.
		 
	End Function

Generating combinations is that simple!.

Who was John Galt?

(Posted 2013) [#13]

Hey thanks for gravedigging a 2 year old thread offering paid work.

virtlands

(Posted 2013) [#14]

" ... the partitions of a set S are all the ways in which you can choose disjoint, non-empty subsets of S that unioned result in S. "

Floyd

(Posted 2013) [#15]

bluemoon's program generates subsets, not partitions.

For elements 1 to n there are 2^n subsets, including the empty set. That would be 1024 subsets of {1,2,3...10}.

The way that program works is that there is a natural correspondence between subsets of 1..n and n-bit numbers. The element k is in the subset if bit k is 1 in the corresponding number.

Here's a demonstration with 1..5, showing the subset number, the five relevant bits and the corresponding subset.

Graphics 600, 450, 0, 2

N = 5

For k = 0 To 2^N - 1
	Write RSet( k, 5 ) + ": " + Right( Bin(k), 5 ) + "    " 
	bit = 1
	For b = 1 To N
		If bit And k Then Write " " + b
		bit = bit Shl 1
	Next
	Print
Next

WaitKey

virtlands

(Posted 2013) [#16]

. . . .