z****u
发帖数: 104 | 1 字符串的 permutation 肯定是比较基础的题了，可是自己写了一下发现要 bug free
真心很难啊。调试了半天才 ok，而且程序看起来很臃肿，这要是在白板上铁定写不出
来啊
求大家指点一下该向哪个方向改进？
#include
#include
#include
char* insert(char* dst, int n, char c, int j)
{
/* Insert char c into string dst at location j */
n++;
dst = (char*) realloc(dst, sizeof(char) * n);
while(j < n)
{
char tmp = dst[j];
dst[j] = c;
c = tmp;
j++;
}
return dst;
}
char** permutation_recursive(char* s, int n, int* m)
{
if (n == 1) /* base case */
{
char* base_string = (char*) malloc(sizeof(char));
char** ps = (char**) malloc(sizeof(char*));
memcpy(base_string, s, sizeof(char));
ps[0] = base_string;
*m = 1;
return ps;
}
else /* recursive part */
{
char** ps = permutation_recursive(s + 1, n - 1, m);
ps = (char**) realloc(ps, sizeof(char*) * (*m) * n);
int i, j;
for (i = 1; i < n; i++)
{
for (j = 0; j < *m; j++)
{
ps[(*m)*i + j] = (char*) malloc(sizeof(char) * (n - 1));
memcpy(ps[(*m)*i + j], ps[j], sizeof(char) * (n - 1));
ps[(*m)*i + j] = insert(ps[(*m)*i + j], n - 1, s[0], i);
}
}
for (j = 0; j < *m; j++)
{
ps[j] = insert(ps[j], n - 1, s[0], 0);
}
*m = (*m) * n;
return ps;
}
}
int main(int argc, char* argv[])
{
char s[] = "1234";
int n = 4;
int m = 0;
char** ps = permutation_recursive(s, n, &m);
int i = 0;
while (i < m)
{
int j;
for (j = 0; j < n; j++)
{
printf("%c", *(*(ps + i) + j));
}
printf("\n");
i++;
}
i = 0;
while(i < m)
{
free(ps[i++]);
}
free(ps);
return 0;
} | l******c
发帖数: 2555 | 2 what are you doing?
so many alloc, realloc
can you test
aab | f*******t
发帖数: 7549 | 3 没那么复杂，只要交换就好了
#include
#include
#include
void swap(char *arr, int idx1, int idx2) {
char temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}
void permutation(char* arr, int index, int size) {
if (index == size) {
printf("%s\n", arr);
}
else {
for (int i=index; i
swap(arr, i, index);
permutation(arr, index+1, size);
swap(arr, i, index);
}
}
}
int main()
{
char characters[6] = "abcd";
permutation(characters, 0, 4);
return 0;
} | p*****2
发帖数: 21240 | 4
不错。
【在 f*******t 的大作中提到】
: 没那么复杂，只要交换就好了
: #include
: #include
: #include
: void swap(char *arr, int idx1, int idx2) {
: char temp = arr[idx1];
: arr[idx1] = arr[idx2];
: arr[idx2] = temp;
: }
: void permutation(char* arr, int index, int size) {
| w****x
发帖数: 2483 | 5 用bool map[26]记录重复的perpetuation | z****u
发帖数: 104 | 6 果真好很多，多谢！
【在 f*******t 的大作中提到】
: 没那么复杂，只要交换就好了
: #include
: #include
: #include
: void swap(char *arr, int idx1, int idx2) {
: char temp = arr[idx1];
: arr[idx1] = arr[idx2];
: arr[idx2] = temp;
: }
: void permutation(char* arr, int index, int size) {
| z****u
发帖数: 104 | 7 没有考虑重复字母的问题，所以测试 aab 肯定通不过
主要考虑的是 permutation 出来的字符串的存储，所以用了很多 malloc 和 realloc
，不过现在想起来我其实完全可以在开始就用一个 malloc 搞定的。
写代码前没动脑子，出来就是这个效果了, /sigh，水平亟待提高啊
【在 l******c 的大作中提到】
: what are you doing?
: so many alloc, realloc
: can you test
: aab
| q****x
发帖数: 7404 | 8 不错。但不能处理重复情况。
【在 f*******t 的大作中提到】
: 没那么复杂，只要交换就好了
: #include
: #include
: #include
: void swap(char *arr, int idx1, int idx2) {
: char temp = arr[idx1];
: arr[idx1] = arr[idx2];
: arr[idx2] = temp;
: }
: void permutation(char* arr, int index, int size) {
| l******c
发帖数: 2555 | 9 if your code is designed by yourself, not learned elsewhere, you are above
the average level on this board.
most learned this algorithm from others.
realloc
【在 z****u 的大作中提到】
: 没有考虑重复字母的问题，所以测试 aab 肯定通不过
: 主要考虑的是 permutation 出来的字符串的存储，所以用了很多 malloc 和 realloc
: ，不过现在想起来我其实完全可以在开始就用一个 malloc 搞定的。
: 写代码前没动脑子，出来就是这个效果了, /sigh，水平亟待提高啊
|
|
