1

我的作业要求我编写一个程序，从终端（argc 和 argv）获取字符串并打印所有可能的排列。我曾尝试使用堆的算法，但它似乎并没有奏效。下面是我的功能。

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;
 }

该函数必须返回指向指令指定的字符指针的指针。这也是为什么有这么多变量的原因（虽然，我不太确定如何处理字符串的副本。我很确定我需要它）。测试表明程序会循环，通常会循环太多，最终会遇到段错误。看起来交换后的字符串并没有将其放入返回的数组中。

4

1 回答 1

1

下面是对您的代码进行了清理内存分配的返工，它解决了上述评论中提到的一些问题。此外，您的算法中有一个错误，此语句strcpy(in, copy);使您无法获得所有排列（反而导致重复。）此代码有效但尚未完成，它可以使用更多错误检查和其他收尾工作：

#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;
}

输出

> ./a.out abc
abc
bac
cab
acb
bca
cba
>
于 2016-09-23T06:53:07.740 回答