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);
}
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.
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.
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)
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");
}
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!
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
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
