Backtracking: I would like to conveert this c code into java to be able to run.

Question

Backtracking:

I would like to conveert this c code into java to be able to run.

In what order will the subsets of {1, 2, 3} be generated? It depends on the order
of moves construct candidates. Since true always appears before false, the subset
of all trues is generated first, and the all-false empty set is generated last: {123},
{12}, {13}, {1}, {23}, {2}, {3}, {} <-------- this is what I expect to get in Java code

bool finished = FALSE; /* found all solutions yet? */
backtrack(int a[], int k, data input)
{
     int c[MAXCANDIDATES]; /* candidates for next position */
     int ncandidates; /* next position candidate count */
     int i; /* counter */

if (is_a_solution(a,k,input))
      process_solution(a,k,input);
else {
      k = k+1;

construct_candidates(a,k,input,c,&ncandidates);

for (i=0; i<ncandidates; i++) {
a[k] = c[i];
    make_move(a,k,input);
    backtrack(a,k,input);
    unmake_move(a,k,input);
    if (finished) return; /* terminate early */
}
}
}

///////Constructing All Subsets

is_a_solution(int a[], int k, int n)
{
return (k == n); /* is k == n? */
}

construct_candidates(int a[], int k, int n, int c[], int *ncandidates)
{
c[0] = TRUE;
c[1] = FALSE;
*ncandidates = 2;
}

process_solution(int a[], int k)
{
int i; /* counter */
printf("{");
for (i=1; i<=k; i++)
if (a[i] == TRUE) printf(" %d",i);
printf(" } ");
}

generate_subsets(int n)
{
int a[NMAX]; /* solution vector */
backtrack(a,0,n);
}

Constructing All Permutations as well

As a consequence of the candidate order, these routines generate permutations
in lexicographic, or sorted order%u2014i.e., 123, 132, 213, 231, 312, and 321 <------ expect output

construct_candidates(int a[], int k, int n, int c[], int *ncandidates)
{
int i; /* counter */
bool in_perm[NMAX]; /* who is in the permutation? */
for (i=1; i<NMAX; i++) in_perm[i] = FALSE;
for (i=0; i<k; i++) in_perm[ a[i] ] = TRUE;
*ncandidates = 0;
for (i=1; i<=n; i++)
if (in_perm[i] == FALSE) {
c[ *ncandidates] = i;
*ncandidates = *ncandidates + 1;
}
}

process_solution(int a[], int k)
{
int i; /* counter */
for (i=1; i<=k; i++) printf(" %d",a[i]);
printf(" ");
}

is_a_solution(int a[], int k, int n)
{
return (k == n);
}
generate_permutations(int n)
{
int a[NMAX]; /* solution vector */
backtrack(a,0,n);
}

Explanation / Answer

nedd more time

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.