What's wrong with my Heap's Algorithm code?

Question

My homework requires me to write a program that takes a string from the terminal (argc and argv) and print every possible permutation. I have tried to use Heap's Algorithm, but it doesn't seem to be working out. Below is my function.

char **getPermutation(char * in)
{
//n is the size of the input string.
 int n = strlen(in);
 int count[n];
 int counter= 0;
 char copy[n];
 char **permutations = malloc(sizeof(char*)*(factorial(n)));
 permutations[0] = in;
 strcpy(in, copy);
 counter++;
 for( int i = 1; i < n;)
 {

  if (count[i] < i){
   if (i%2==0){
    swap(&in[0],&in[i]);
   }
   else
   {
    swap(&in[count[i]],&in[i]);
   }
    permutations[counter] = in;
    strcpy(in, copy);
    counter++;
    count[i]++;
    i = 1;
  }
  else
  {
   count[i] = 0;
   i++;
   }
  }
 return permutations;
 }

The function must return the pointer to the character pointer as specified by the instructions. That's also why there are so many variables (although, I'm not really sure what to do with the copy of the string. I'm fairly sure I need it). Testing shows that the program will loop, often too much and eventually hit a seg fault. It doesn't seem like the swapped strings make it into the returned array on top of that.

The segfault is because you need to allocate memory for each individual permutation, too: permutation[counter] = malloc(strlen(in) +1)... I can't say much about the rest, your post lacks a bit of code. — deamentiaemundi
– deamentiaemundi, Commented Sep 23, 2016 at 4:04
1) int count[n]; It's uninitialized. 2) char copy[n]; --> char copy[n+1]; 3) strcpy(in, copy); --> strcpy(copy, in); — BLUEPIXY
– BLUEPIXY, Commented Sep 23, 2016 at 4:07
strlen give a size_t back not a int. you should not use int for sizes and array index. — 12431234123412341234123
– 12431234123412341234123, Commented Sep 23, 2016 at 6:56

cdlane · Accepted Answer · 2016-09-23 06:59:21Z

Below is a rework of your code with cleaned up memory allocation and it addresses some problems mentioned in the above comments. Additionally, you have a bug in your algorithm, this statement strcpy(in, copy); keeps you from getting all the permutations (causes repeats instead.) This code works but isn't finished, it can use more error checking and other finishing touches:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

unsigned int factorial(unsigned int n)
{
    /* ... */
}

void swap(char *a, char *b)
{
    /* ... */
}

char **getPermutations(const char *input)
{
    char *string = strdup(input);

    size_t length = strlen(string);

    char **permutations = calloc(factorial(length), sizeof(char *));

    int *counts = calloc(length, sizeof(int)); // point to array of ints all initialized to 0

    int counter = 0;

    permutations[counter++] = strdup(string);

    for (size_t i = 1; i < length;)
    {
        if (counts[i] < i)
        {
            if (i % 2 == 0)
            {
                swap(&string[0], &string[i]);
            }
            else
            {
                swap(&string[counts[i]], &string[i]);
            }
            permutations[counter++] = strdup(string);
            counts[i]++;
            i = 1;
        }
        else
        {
            counts[i++] = 0;
        }
    }

    free(counts);
    free(string);

    return permutations;
 }

int main(int argc, char *argv[])
{

    char *string = argv[1];

    char **permutations = getPermutations(string);

    unsigned int total = factorial(strlen(string));

    for (unsigned int i = 0; i < total; i++)
    {
        printf("%s\n", permutations[i]);
    }

    free(permutations);

    return 0;
}

OUTPUT

> ./a.out abc
abc
bac
cab
acb
bca
cba
>

Collectives™ on Stack Overflow

What's wrong with my Heap's Algorithm code?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related