Heap's Algorithm

Hi All,

I have been trying to implement Heap’s Algorithm on an Arduino Uno but I am running into some problems. I think it has to do with my swap function but when I test the function in isolation it works as expected. I am expecting the following output:

1 2 3
2 1 3
3 1 2
1 3 2
2 3 1
3 2 1

but instead I get:

1 2 3
1 3 2
1 2 3
1 3 2
1 2 3
1 3 2

Full code can be found below:

const int dial = 3;
const int combo_size = 3;
int ar [dial];
int n = sizeof(ar)/sizeof ar[0];

void setup() {
  // put your setup code here, to run once:
Serial.begin(9600);
create_dial(dial);
perm(ar, n, n);
//Swap Test Code
  //swapTest();
return 0;
}

void loop() {
  // put your main code here, to run repeatedly:

}

void create_dial(int dial) {
  for(int i=0; i<dial; i++){
      ar [i] = i+1;
      //Serial.println((String)"Array Position " + i + " = " + ar[i]);    
    }
}

void perm(int a[], int size, int n) {
  if(size ==1){
    printArr(a, n );
    return;
  }
  else{
    perm(a,size-1,n);
  
  for (int i=0; i<size-1; i++) {     
        // if size is even, swap ith and last 
        // element 
        if (size%2==0){ 
            swap(a, a[i], a[size-1]); 
        }
        // If size is odd, swap first and last 
        // element 
        else{
            swap(a, a[0], a[size-1]); 
        }
        perm(a,size-1,n);
    }
  }
}

//Prints the array 
void printArr(int a[],int n) { 
    for (int i=0; i<n; i++) 
        Serial.print((String) a[i] + " "); 
    Serial.print("\n");
}
//Swaps array positions
void swap(int a[], int apos1, int apos2) {
  int temp = a[apos1];
  int temp1 = apos2;
  a[apos1] = a[temp1];
  a[apos2] = temp;
  return;
}

void swapTest(){
  //Serial.println("***SWAP TEST***");
  Serial.println((String)"N is: " + n);
  Serial.println("Before Swap: ");
  printArr(ar,n);
  swap(ar, 2, n-1);
  Serial.println("After Swap: ");
  printArr(ar,n);
}

What am I missing?

Performing an Auto-Format might help you figure out if you have some braces in the wrong places.

Did you copy the code from some website describing the algorithm? Post a clickable link to there. What language was it originally? Maybe there is some difference between that language and C you are not aware of, such as how parameters are passed to functions.

swap(a, a[i], a[size-1]);

Should that be

swap(a, i, size-1);

If not, consider the swap function, where you WILL be using out of bounds array indices. (Hint: in swap you are using array elements as array indices. One of those indices will ALWAYS be out of bounds)

Also, setup is defined void, yet you are returning a value.

GorillaDetective:
What am I missing?

Transparent coding… I suspect you have a for loop to many causing you to do an extra swap back to the original position. Recursive functions can be hard to read as a rule, but writing something in this way

int n = sizeof(ar)/sizeof ar[0];

is overkill. Anyway back to the issue i suspect

for (int i=0; i<size-1; i++) {     
        // if size is even, swap ith and last 
        // element

this doesn’t need to be a loop, if you are going to swap 2 elements once should be enough, though the whole construction of the code to me, seems overly complex (and due to some style elements a little hard to read)

tweaked your code a bit and this worked for me:

const int dial = 3;
const int combo_size = 3;
int ar [dial];
int n = sizeof(ar) / sizeof(ar[0]);

void setup() {
  // put your setup code here, to run once:
  Serial.begin(9600);
  create_dial(dial);
  perm(ar, n, n);

}

void loop() {
  // put your main code here, to run repeatedly:

}

void create_dial(int dial) {
  for (int i = 0; i < dial; i++) {
    ar [i] = i + 1;
    //Serial.println((String)"Array Position " + i + " = " + ar[i]);
  }
}

// Generating permutation using Heap Algorithm
void perm(int a[], int size, int n)
{
  // if size becomes 1 then prints the obtained
  // permutation
  if (size == 1)
  {
    printArr(a, n);
  }

  for (int i = 0; i < size; i++)
  {
    perm(a, size - 1, n);


    int temp;

    // if size is odd, swap first and last element
    if (size & 0x01) { //works quicker than %2
      temp = a[0];
      a[0] = a[size - 1];
      a[size - 1] = temp;
    }
    
    // If size is even, swap ith and last element
    else {
      temp = a[i];
      a[i] = a[size - 1];
      a[size - 1] = temp;
    }
  }
}

//Prints the array
void printArr(int a[], int n) {
  for (int i = 0; i < n; i++) {
    Serial.print(a[i]);
    Serial.print(" ");
  }
  Serial.print("\n");
}

result:
1 2 3
2 1 3
3 2 1
2 3 1
3 1 2
1 3 2

Thanks @Sherzaad

That works. The output I get is in a slightly different order than I was expecting but order doesn’t really matter as long as all the permutations are there.

I did have a question about why you moved the swapping code out of the swap function and into the perm function. Is that better to do? Does it make it less complicated? Really appreciate the assistance!

Thanks!

GorillaDetective:
I did have a question about why you moved the swapping code out of the swap function and into the perm function. Is that better to do? Does it make it less complicated?

a) it is simpler
b) it is correct (without your superfluous double indirection)
See reply #2

Hi AWOL,

My reply wasn’t directed to you specifically but thanks for chiming in and providing your perspective on why someone else did something.

You’re very welcome

GorillaDetective:
I did have a question about why you moved the swapping code out of the swap function and into the perm function. Is that better to do? Does it make it less complicated? Really appreciate the assistance!

TheMemberFormerlyKnownAsAWOL:
a) it is simpler
b) it is correct (without your superfluous double indirection)
See reply #2

could now have said it any better! :wink: