3 replies to this topic

[DarkSun]

Hey,
I would like to hear some opinions about a recursion problem...
I have a basic solution, which I am quite sure there are better ones...

The problem is -
I have N blocks of different size (for example 1,2,3 meaning block 1 is the smallest and 3 is the biggest).
and have print all possible combinations of building pyramids using the blocks.
Each pyramid can be built of 1 to N blocks, and each block can be put on the ground, or on a bigger block.

For example for N=3 all the posible combinations are:
[ 3 2 1 ] -> 1 Pyramid:
meaning 1 (smallest block) is on top of 2 which is on top of 3
(biggest block)
[ 3 2 ][ 1 ] -> 2 Pyramids
[ 3 1 ][ 2 ] -> ...
[ 3 ][ 2 1 ] -> ...
[ 3 ][ 2 ][ 1 ] -> 3 Pyramids

I have found this page Bell_number (Wikipedia),
Which tells me how many combinations there are for N, but I should print the actual combinations (not their number).

I have tried backtracking recursion,

buildBlocks(0,1);
...
function buildBlocks(int startPos, int endPos) {

    	if ((endPos >= stacksOfStones.length) || 
    	    (startPos >= endPos)) {
    		return;
    	}

   for (int i=startPos; i<endPos; i++) {
      ... some ignore dups ifs...
      stacksOfStones[i].push( stacksOfStones[endPos].pop() );
      printStacks();
     buildBlocks(i,endPos+1);
      stacksOfStones[endPos].push( stacksOfStones[i].pop() );
     buildBlocks(i,endPos+1);
}

Besides an issue of dups, it basically works...
But I am quite sure a better solution can be found...
Any ideas?

Edited by WingedPanther, 20 January 2009 - 04:59 AM.
add code blocks (the # button)

[elegos]

I'm not sure of what are you asking (I'm pseudo-asleep :P )

You mean you have n blocks to form k piramids?
Like, the simplest one,
[1]
[2][2]?

[WingedPanther]

First of all, are you required to use recursion, or is this just your idea? This seems like something I'd use a while loop on, as recursion could very quickly chew up large amounts of memory.

[roboticforest]

I'm not sure of a "better" solution. Are you wanting something that runs faster? You could try a while loop instead of recursion as WingedPanther suggested.

WingedPanther said:

... recursion could very quickly chew up large amounts of memory.

Recursion probably will, but that depends on the compiler and the kind of recursion being used.