Returning an array in Heap's recursive algorithm

Question

I've implemented the Heap's algorithm for finding all permutations of the elements of array A:

//A = {1, 2, 3, 4}; B = perms(A) ; num_row(B) = (4!+1) and B[0][0] = 4!;
//This is B.R. Heap's algorithm
public static void perms(int [] A, int [][]B, int n)
{
   if (n == 1)
   {
       int k = B[0][0];
       for (int i = 0; i < A.length; i++)
       {
           B[k + 1][i] = A[i];
       }
       B[0][0]++;
   }
   else
   {
       for (int i = 0; i < n - 1 ;i++)
       {
           perms(A, B, n-1);
           if (n % 2 == 0)
           {
               swap(A, i, n - 1);
           }
           else
           {
               swap(A, 0, n - 1);
           }
       }
       perms(A, B, n - 1); 
   }
}
public static void swap(int[] A, int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

I'm new to Java. The problem is I want to have B as the output (return) of the function perms(A) , but in this implementation, I have to initialize a int[n! + 1][A.length] B array before calling the function. How can I do it?
Is there anything like private variable or anything in java to help a recursive function to remember a variable from a former call?

Thanks

What is n variable starting value, how do you call this method? — maskacovnik
– maskacovnik, Commented Jul 7, 2015 at 8:29
n = A.length and I call it this way: int [] A = {1, 2, 3}; int [][] B = new int[(int)factorial(A.length) + 1][A.length]; perms(A, B, A.length); — Zeta.Investigator
– Zeta.Investigator, Commented Jul 7, 2015 at 8:35

maskacovnik · Accepted Answer · 2015-07-07 09:03:17Z

1

You can create an "entering" method to recursion like this:

public static int[][] perms(int[] a){
    int[][] perms = new int[factorial(a.length)+1][a.length];
    perms(a,perms,a.length);
    return perms;
}

Method factorial is well know method and can be found on Google for example
Wondering if n parameter is neccessary

EDIT

it is not neccessary (above corrected)

EDIT

By my test the k variable is just incrementing, so I would use static variable like this:

private static int counter = 0;
// your code here, following is a part of your perms method
if (n == 1)
{
    for (int i = 0; i < A.length; i++)
    {
        B[counter][i] = A[i];
    }
    counter++;
}
//and my code corrected too:
public static int[][] perms(int[] a){
    int[][] perms = new int[factorial(a.length)][a.length]; //+1 is not necessary
    counter=0; //necessary to call it again
    perms(a,perms,a.length);
    return perms;
}

edited Jul 7, 2015 at 9:03

answered Jul 7, 2015 at 8:24

maskacovnik

3,0845 gold badges23 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

maskacovnik Over a year ago

Answer was corrected with your help @Zeta.Investigator

Zeta.Investigator Over a year ago

This is great! Thanks; Any idea how can I get rid of B[0][0] (where I keep track of the k'th permutaion) ?

Collectives™ on Stack Overflow

Returning an array in Heap's recursive algorithm

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related