Keeping multiple two dimensional arrays - recursive method

[Denis Palas]

Hi everybody

I am working on a search algorithm which involves certain categories:

A = {A11,A12,A13,A14,A15}
B= {B21,B22,B23}
C= {C31,C32,C33,C44}


and so on (Different Number of categories may exist for different problems)

The main function is a recursive function , and at each round , one category
is taken, some elements chosen according to certain criteria, and this
result is

joined with previous result, for example:


At first round , from A , A11,A14,A15 are chosen.
At second round , from B , B22,B23 is chosen and joined with A11,A14 and
A15:

Result Array:
A11 B22
A14 B22
A15 B22
A11 B23
A14 B23
A15 B23

and this process continues and this two dimensional result array contains
all the joined chosen elements of sets of categories.My code to use the
result array from previous round and join it with new values is working
fine. However , I need to have multiple versions of result array as
explained below:


My Question : Since at any point, the algorithm needs to backtrack , and
choose different values , I must keep a search tree of all the result arrays
found so far. I need to find a way to keep a version of my result array at
each round (result array which contains join of A and B , result array which
contains the join of A,B and C , result array which contains the join of
A,B,C and D , and so on ) so at any point I will be able to backtrack and
choose the appropriate result set.

Could you please advise how I can do this ?


Most Appreciated
Denis

 

[Denis Palas]

Just adding little more detail to make it clearer !

Roughly , I have the code :

public String[][] search(String resultarray[][] , int i)

{ String Category[][]={{"A11","A12","A13","A14","A15"},
{"B21","B22","B23"},
{"C31","C32","C33","C34"},
{"D41","D42","D43"}
}

//My base case
if (i> Noofcategories)
{return resultarray;} //return to main function

// My recursive part
resultarray=jointwoArrays(resultarray,category,i);

return(search(resultarray,i+1));
}


What I need advice for is, instead of having one result array, which has all
the answers joined so far, I need to have multiple versions of resultarray,
kept separately at each round of recursive function. This will help me
backtrack to the proper place.

Resultarray version 1:
A11,A12

Resultarray version 2:
A11 B21
A11 B21
A12 B23
A12 B23

Resultarray version 3:
A11 B21 C34 , etc.



Any tips is EXTREMELY appreciated ....

 

[Patricia Shanahan]

Denis Palas wrote:
....

What I need advice for is, instead of having one result array, which has all
the answers joined so far, I need to have multiple versions of resultarray,
kept separately at each round of recursive function. This will help me
backtrack to the proper place.

....

The obvious answer seems to be "make a copy and keep a reference to it".

Is there some reason why that is not a valid answer?

Patricia

 

[Denis Palas]

Could you please explain a little more? Please note that I am using a
recursive method ...

Thank you

 

[Patricia Shanahan]

Could you please explain a little more? Please note that I am using a
recursive method ...

Thank you

Please don't add new material at the top. It messes up the flow of the
flow of comments.

I'm afraid I still don't understand the question.

Using a recursive method for a backtracking algorithm means that you
have the option of keeping state data in the call stack. If you were
doing an iterative approach to backtracking you would need an explicit
stack of states.

Is the difficulty backtracking with recursion, or something about two
dimensional arrays?

Patricia

 

[Denis Palas]

Using a recursive method for a backtracking algorithm means that you
have the option of keeping state data in the call stack. If you were
doing an iterative approach to backtracking you would need an explicit
stack of states.

Is the difficulty backtracking with recursion, or something about two
dimensional arrays?

Patricia

The algorithm backtracks when some conditions are not met , by calling

public String[][] search(String resultarray[][] , int i)

{ String Category[][]={{"A11","A12","A13","A14","A15"},
{"B21","B22","B23"},
{"C31","C32","C33","C34"},
{"D41","D42","D43"}
}

//My base case
if (i> Noofcategories)
{return resultarray;} //return to main function

// My recursive part
resultarray=jointwoArrays(resultarray,category,i);

If conditions are met:
return(search(resultarray,i+1));

else
Change some parameters and return(search(resultarray,i-1));
}

I have some difficulty understanding how stacks will work in my case, since
my base case holds the final answer and will return it to the main function
as soon as all categories are considered.

Thank You
Denis

 

[lightning]

If conditions are met:
return(search(resultarray,i+1));

this condition can be "(i==2)",so it returns the version 2,is that what
you want?

In fact , I think it's not necessary to use recursive,you can surely
use "for" instead......