Converting recursive algorithm to an iterative version
 

Hi,

Here is my problem:
I implemented recurive algorithm in c++ for a problem given below:

I have a list of items (only positive integers are allowed) and fixed
number of bins of identical capacity. I need to pack items (if
possible) so that elements in each bin sum up to given capacity.

I try to convert my recursive algorithm to an one. However, my
implementation with explicit stack doesn't work as I expected. I can't
pinpoint the place where I have made a mistake.

//items are sorted in decreasing order

Recursive:
bool backtrack(vector<int>& items, vector<Bin>& bins, unsigned
index,unsigned bin_capacity)
{
if (bin_capacity - items.front() < 0) return false;

if (index < items.size())
{
//try to put an item into all opened bins
for(unsigned i = 0; i < bins.size(); ++i)
{
if (bins[i].sum() + items[index] + items.back() <=
bin_capacity || bin_capacity - bins[i].sum() == items[index])
{
bins[i].add(items[index]);
return backtrack(items, bins, index + 1,
bin_capacity);

}
}
//put an item without exceeding maximum number of bins
if (bins.size() < BINS)
{
Bin new_bin = Bin();
bins.push_back(new_bin);
bins.back().add(items[index]);

return backtrack(items, bins, index + 1, bin_capacity);

}
}
else
{
//check if solution has been found
if (bins.size() == BINS )
{
for (unsigned i = 0; i <bins.size(); ++i)
{
packed_items.push_back(bins[i]);
}

return true;
}
}
return false;

}

Iterative( not working properly)
bool backtrack(vector<int>& items, vector<Bin>& bins, unsigned index,
unsigned bin_capacity)
{
stack<Node> stack;
Node node, child_node;
Bin new_bin;
//init the stack
node.bins.add(new_bin);
node.bins.back().add(items[item_index]);
stack.push(node);
item_index++;

while(!stack.empty())
{
node = stack.top();
stack.pop();

if (item_index < items.size())
{
if (node.bins.size() < BINS)
{
child_node = node;
Bin empty;
child_node.bins.add(empty);
child_node.bins.back().add(items[item_index]);
stack.push(child_node);
}

int last_index = node.bins.size() - 1;
for (unsigned i = 0; i <= last_index; i++)
{
if (node.bins[last_index - i]->get_sum()
+items[item_index]+ items.back( <=bin_capacity || bin_capacity -
node.bins[last_index - i]->get_sum() ==items[item_index])
{
child_node = node;
child_node.bins[last_index - i]-
>push_back(items[item_index]);

stack.push(child_node);
}
}
item_index++;
}
else
{
if (node.bins() == BINS)
{
//copy solution
bins = node.bins;
return true;
}
}
}
return false;

}

Any help would be highly appreciated.

Re: Converting recursive algorithm to an iterative version
 

On 12/7/2011 6:48 PM, Ania wrote:
> Here is my problem:
> I implemented recurive algorithm in c++ for a problem given below:
>
> I have a list of items (only positive integers are allowed) and fixed
> number of bins of identical capacity. I need to pack items (if
> possible) so that elements in each bin sum up to given capacity.
>
> I try to convert my recursive algorithm to an one. However, my
> implementation with explicit stack doesn't work as I expected.

What does that mean? What did you expect? What does it do? Do you
think we should be guessing or dusting off our crystal ball?

> I can't
> pinpoint the place where I have made a mistake.

Have you tried using a "debugger" and step through your code? Do you
have a test case? Do you know what values of your objects need to be on
every step of your algorithm? If you do, just fire off that debugger
(whichever you got, all pretty much work when you know what you're
doing) and execute your test program step by step, and verify that the
values of the objects as they need to be. If they aren't make changes
to the code.

If you don't have a test case, get yourself one. If you don't know what
values of your objects should be at every point in your program... did
you actually write your program yourself? If you did, you should. Do
you know how to use a debugger? If you don't, it looks like it's time
to learn.

Bite the bullet and fix your own program. Otherwise, find a different
field to develop your skills.

V
--
I do not respond to top-posted replies, please don't ask

Re: Converting recursive algorithm to an iterative version
 

On Dec 7, 11:48*pm, Ania <anka.step...@gmail.com> wrote:
> Hi,
>
> Here is my problem:
> I implemented recurive algorithm in c++ for a problem given below:
>
> I have a list of items (only positive integers are allowed) and fixed
> number of bins of identical capacity. I need to pack items (if
> possible) so that elements in each bin sum up to given capacity.
>
> I try to convert my recursive algorithm to an one. However, my
> implementation with explicit stack doesn't work as I expected. I can't
> pinpoint the place where I have made a mistake.
>
> //items are sorted in decreasing order
>
> Recursive:
> bool backtrack(vector<int>& items, vector<Bin>& bins, unsigned
> index,unsigned bin_capacity)
> {
> * * if (bin_capacity - items.front() < 0) return false;
>
> * * if (index < items.size())
> * * {
> * * * * //try to put an item into all opened bins
> * * * * for(unsigned i = 0; i < bins.size(); ++i)
> * * * * {
> * * * * * * if (bins[i].sum() + items[index] + items.back() <=
> bin_capacity || bin_capacity - bins[i].sum() == items[index])
> * * * * * * {
> * * * * * * * * bins[i].add(items[index]);
> * * * * * * * * return backtrack(items, bins, index + 1,
> bin_capacity);
>
> * * * * * * }
> * * * * }
> * * * * //put an item without exceeding maximum number of bins
> * * * * if (bins.size() < BINS)
> * * * * {
> * * * * * * Bin new_bin = Bin();
> * * * * * * bins.push_back(new_bin);
> * * * * * * bins.back().add(items[index]);
>
> * * * * * * return backtrack(items, bins, index + 1, bin_capacity);
>
> * * * * }
> * * }
> * * else
> * * {
> * * * * //check if solution has been found
> * * * * if *(bins.size() == BINS )
> * * * * {
> * * * * * * for (unsigned i = 0; i <bins.size(); ++i)
> * * * * * * {
> * * * * * * * * packed_items.push_back(bins[i]);
> * * * * * * }
>
> * * * * * * return true;
> * * * * }
> * * }
> * * return false;
>
> }
>
> Iterative( not working properly)
> bool backtrack(vector<int>& items, vector<Bin>& bins, unsigned index,
> unsigned bin_capacity)
> {
> * * * stack<Node> stack;
> * * * Node node, child_node;
> * * * Bin new_bin;
> * * * //init the stack
> * * * node.bins.add(new_bin);
> * * * node.bins.back().add(items[item_index]);
> * * * stack.push(node);
> * * * item_index++;
>
> * * * while(!stack.empty())
> * * * {
> * * * * node = stack.top();
> * * * * stack.pop();
>
> * * * * if (item_index < items.size())
> * * * * {
> * * * * * * if (node.bins.size() < BINS)
> * * * * * * {
> * * * * * * * *child_node = node;
> * * * * * * * *Bin empty;
> * * * * * * * *child_node.bins.add(empty);
> * * * * * * * *child_node.bins.back().add(items[item_index]);
> * * * * * * * *stack.push(child_node);
> * * * * * * }
>
> * * * * * * int last_index = node.bins.size() - 1;
> * * * * * * for (unsigned i = 0; i <= last_index; i++)
> * * * * * * {
> * * * * * * * * if (node.bins[last_index - i]->get_sum()
> +items[item_index]+ items.back( <=bin_capacity || bin_capacity -
> node.bins[last_index - i]->get_sum() ==items[item_index])
> * * * * * * * *{
> * * * * * * * * * *child_node = node;
> * * * * * * * * * *child_node.bins[last_index - i]-
>
> >push_back(items[item_index]);
>
> * * * * * * * * * *stack.push(child_node);
> * * * * * * * * }
> * * * * * * }
> * * * * * * item_index++;
> * * * * * * }
> * * * * else
> * * * * {
> * * * * * *if (node.bins() == BINS)
> * * * * * *{
> * * * * * * * *//copy solution
> * * * * * * * *bins = node.bins;
> * * * * * * * *return true;
> * * * * * *}
> * * * *}
> * *}
> * * return false;
>
> }
>
> Any help would be highly appreciated.

build in some sort of trace facility. By seeing what gets called with
what parameters should enable you to compare the recursive with the
iterative and fix one or the other.

Why are you doing this?

Re: Converting recursive algorithm to an iterative version
 

@Nick Keighley I'm trying to implement an iterative version just
because of stack overflows for large datasets in recursive approach,

Thanks for your suggestions, I'll try to use debugger.

Re: Converting recursive algorithm to an iterative version
 

On 12/07/11 17:48, Ania wrote:
[snip]
> I try to convert my recursive algorithm to an one. However, my
> implementation with explicit stack doesn't work as I expected. I can't
> pinpoint the place where I have made a mistake.
[snip]

In the iterative code, there's:

> int last_index = node.bins.size() - 1;
> for (unsigned i = 0; i <= last_index; i++)
> {
> if (node.bins[last_index - i]->get_sum()
> +items[item_index]+ items.back( <=bin_capacity || bin_capacity -
> node.bins[last_index - i]->get_sum() ==items[item_index])
This looks suspicious to me:

( <=bin_capacity

Are you sure you've posted code that compiles?

-regards,
Larry

Re: Converting recursive algorithm to an iterative version
 

On 8 Gru, 18:58, Larry Evans <cppljev...@suddenlink.net> wrote:
> On 12/07/11 17:48, Ania wrote:
> [snip]> I try to convert my recursive algorithm to an one. However, my
> > implementation with explicit stack doesn't work as I expected. I can't
> > pinpoint the place where I have made a mistake.
>
> [snip]
>
> In the iterative code, there's:
>
> > * * * * * * int last_index = node.bins.size() - 1;
> > * * * * * * for (unsigned i = 0; i <= last_index; i++)
> > * * * * * * {
> > * * * * * * * * if (node.bins[last_index - i]->get_sum()
> > +items[item_index]+ items.back( <=bin_capacity || bin_capacity -
> > node.bins[last_index - i]->get_sum() ==items[item_index])
>
> This looks suspicious to me:
>
> * ( <=bin_capacity
>
> Are you sure you've posted code that compiles?
>
> -regards,
> Larry

Finally, I found a place where I made a mistake. I messed with
pointers(shallow copies) and that was the main problem. Now it works
great.

Thanks for inspiring me.

I'm sorry but the code posted was not ready to compile, it was high
level pseudocode.
Here is code ready to compile (I don't use pointers here, just to make
it simpler).

class Bin
{
public:
Bin() { _sum = 0;}
int get_sum(){ return _sum; }
int size() {return bin.size(); }
bool isFull() { return _sum == bin.size(); }
void add(int item)
{
bin.push_back(item);
_sum += item;
}
//for testing output
void print(){
for(unsigned i = 0; i < bin.size(); ++i)
{
cout<< bin[i]<<endl;
}
}
private:
vector<unsigned> bin;
unsigned _sum;
};

struct Node
{
vector<Bin> bins;
};

BINS = 3; //just example value

bool backtrack(vector<unsigned>& items, vector<Bin>& bins, unsigned
index,unsigned bin_capacity)
{
if (bin_capacity - items.front() < 0) return false;

if (index < items.size())
{
//try to put an item into all opened bins
for(unsigned i = 0; i < bins.size(); ++i)
{
if (bins[i].get_sum() + items[index] + items.back() <=
bin_capacity || bin_capacity - bins[i].get_sum() == items[index])
{
bins[i].add(items[index]);
return backtrack(items, bins, index + 1,
bin_capacity);

}
}
//put an item without exceeding maximum number of bins
if (bins.size() < BINS)
{
Bin new_bin = Bin();
bins.push_back(new_bin);
bins.back().add(items[index]);

return backtrack(items, bins, index + 1, bin_capacity);

}
}
else
{
if (bins.size() == BINS )
{
return true;
}
}
return false;

}


bool backtrack2(vector<unsigned>& items, vector<Bin>& bins, unsigned
item_index, unsigned bin_capacity)
{
stack<Node> stack;
Node node, child_node;
Bin new_bin;
//init the stack
node.bins.push_back(new_bin);
node.bins.back().add(items[item_index]);
stack.push(node);
item_index++;

while(!stack.empty())
{
node = stack.top();
stack.pop();

if (item_index < items.size())
{
if (node.bins.size() < BINS)
{
child_node = node;
Bin empty;
child_node.bins.push_back(empty);
child_node.bins.back().add(items[item_index]);
stack.push(child_node);
}

int last_index = node.bins.size() - 1;
for (unsigned i = 0; i <= last_index; i++)
{
if (node.bins[last_index - i].get_sum()
+items[item_index]+ items.back() <=bin_capacity || bin_capacity -
node.bins[last_index - i].get_sum() ==items[item_index])
{
child_node = node;
child_node.bins[last_index -
i].add(items[item_index]);

stack.push(child_node);
}
}
item_index++;
}
else
{
if (node.bins.size() == BINS)
{
//copy solution
bins = node.bins;
return true;
}
}
}
return false;

}

Re: Converting recursive algorithm to an iterative version
 

Ania <anka.stepien@gmail.com> wrote:
> I try to convert my recursive algorithm to an [iterative] one.

May I ask why?

I think that unless there's a good reason for that, this is a true case
of premature optimization (in the most negative sense). It is often the
case that if an algorithm is recursive in nature, trying to implement it
iteratively (especially if you need an explicit stack) only produces
significantly longer and more complicated code. If the amount of recursion
in the original algorithm is less-than-linear (eg. O(log n) recursions),
then any possible overhead caused by the recursive calls is insignificant.

Thus, in such a case, the iterative version will be longer, more
complicated and with little to no speed benefit. (Hence why it's true
premature optimization.)

Re: Converting recursive algorithm to an iterative version
 

On Friday, December 9, 2011 2:41:12 PM UTC+8, Juha Nieminen wrote:
> Ania <anka.s...@gmail.com> wrote:
> > I try to convert my recursive algorithm to an [iterative] one.
>
> May I ask why?
>
> I think that unless there's a good reason for that, this is a true case
> of premature optimization (in the most negative sense). It is often the
> case that if an algorithm is recursive in nature, trying to implement it
> iteratively (especially if you need an explicit stack) only produces
> significantly longer and more complicated code. If the amount of recursion
> in the original algorithm is less-than-linear (eg. O(log n) recursions),
> then any possible overhead caused by the recursive calls is insignificant.
>
> Thus, in such a case, the iterative version will be longer, more
> complicated and with little to no speed benefit. (Hence why it's true
> premature optimization.)

If you are writing programs to be run infrequently for trivial jobs,
I have to say that in this kind of trivial cases there is no need for any optimization or improvement for this kind of programming.

But in my experience, codes fine-tued for speed requirements are not low paid
programmers' jobs in the industry.

Re: Converting recursive algorithm to an iterative version
 

88888 Dihedral <dihedral88888@googlemail.com> wrote:
> If you are writing programs to be run infrequently for trivial jobs,
> I have to say that in this kind of trivial cases there is no need for any optimization or improvement for this kind of programming.

And my point is that *regardless* of where the code might be used,
converting a naturally recursive algorithm into an iterative form that
avoids the recursive function call is usually premature optimization of
the bad kind (makes the code significantly more complicated for little
to no benefit).

Re: Converting recursive algorithm to an iterative version
 

On Saturday, December 10, 2011 5:54:32 PM UTC+8, Juha Nieminen wrote:
> 88888 Dihedral <dihedr...@googlemail.com> wrote:
> > If you are writing programs to be run infrequently for trivial jobs,
> > I have to say that in this kind of trivial cases there is no need for any optimization or improvement for this kind of programming.
>
> And my point is that *regardless* of where the code might be used,
> converting a naturally recursive algorithm into an iterative form that
> avoids the recursive function call is usually premature optimization of
> the bad kind (makes the code significantly more complicated for little
> to no benefit).

There are very limited cases for recursive functions to be used in C.
The quick sort in the c lib is notorious to be choked quite often.
Tree visiting of 30K nodes or less in C is too simple to be modified for speeds.