论坛: 编程破解 标题: 我面试的一道题目 复制本贴地址    
作者: ziaichen [ziaichen]    论坛用户   登录
我现在实习所在公司以前给我的一到面试题目:把一个字符串的全排列输出
语言种类不限(最好是c)
请有兴趣的朋友贴出自己的算法,大家交流以下

地主 发表时间: 06-03-20 16:45

回复: jhkdiy [jhkdiy]   版主   登录
遭了,什么是全排列。

B1层 发表时间: 06-03-20 19:14

回复: ziaichen [ziaichen]   论坛用户   登录
汗,就是一个字符串所有不同的字母排列,比如有n个字母,这样的排列就有n!个

B2层 发表时间: 06-03-21 08:39

回复: sniper167 [sniper167]   论坛用户   登录
上网有限制  又贴不上来  大家去看看这个程序  字符串的全排列的
偶还没看懂  哪位要是看懂了  麻烦解释下  谢谢咯 http://community.csdn.net/Expert/topic/4651/4651618.xml?temp=.5014459

B3层 发表时间: 06-03-30 19:15

回复: ziaichen [ziaichen]   论坛用户   登录
楼上的程序有个严重的错误:当输入的字符串有相邻的字符是相同的话,会重复输出相同的排列

如:请输入一个不超过20个字符的字符kkm
1:kkm
2:kmk
3:kkm
4:kmk
5:mkk
6:mkk
Press any key to continue




[此贴被 一窍不通(ziaichen) 在 04月06日17时37分 编辑过]

B4层 发表时间: 06-04-06 17:32

回复: ziaichen [ziaichen]   论坛用户   登录
楼上的,最近没什么时间上网看帖子喽,偶要走了,有时间和你q或者邮箱多多探讨问题,qq:153975801 邮箱:ckun0210@163.com

B5层 发表时间: 06-04-06 17:36

回复: sniper167 [sniper167]   论坛用户   登录
偶只能邮箱跟你联系咯    我这不能上qq的

我正在用另外一种算法写    写好了发上来   
偶最近也有点忙啊

B6层 发表时间: 06-04-07 12:53

回复: sniper167 [sniper167]   论坛用户   登录
TO: 一窍不通 
楼上的程序有个严重的错误:当输入的字符串有相邻的字符是相同的话,会重复输出相同的排列

如:请输入一个不超过20个字符的字符kkm
1:kkm
2:kmk
3:kkm
4:kmk
5:mkk
6:mkk
Press any key to continue

写完了,可是偶还没解决这个问题
办法想象中。。。


B7层 发表时间: 06-04-08 16:25

回复: sniper167 [sniper167]   论坛用户   登录
日哦
又贴不上来
真服了

B8层 发表时间: 06-04-21 08:51

回复: sniper167 [sniper167]   论坛用户   登录
修正了重复字符问题      还请各位多指点  有没有更好的方法
#include <stdio.h>

#include <stdlib.h>

#include <string.h>



int sum = 0;    /* 全排列个数 */

int iLength = 0;  /* 字符串才长度 */



struct node

{

char *string;

struct node *next;

};

struct node *head, *pCurNode;



void insert(char *pStr)

{

struct node *ptmp;

int i;

char *pCurStr;



pCurStr = (char *)malloc(strlen(pStr) + 1);

strcpy(pCurStr, pStr);



if(sum == 0)

{

ptmp = (struct node *)malloc(sizeof(struct node));

if(ptmp == NULL)

{

printf("malloc error!\n");

return;

}



ptmp->string = pCurStr;

ptmp->next = NULL;

head = ptmp;

pCurNode = head;

sum++;

}

else

{  /* 检查有无重复字符 */

        ptmp = head;

for(i=0; i<sum; i++)

{

if(!strcmp(ptmp->string, pCurStr))

{

printf("Have same string: %s\n", pCurStr);

return;

}

ptmp = ptmp->next;

}

        /* 无重复字符,插入存储链表 */

ptmp = (struct node *)malloc(sizeof(struct node));

if(ptmp == NULL)

{

printf("malloc error!\n");

return;

}

ptmp->string = pCurStr;

ptmp->next = NULL;

pCurNode->next = ptmp;

pCurNode = ptmp;

sum++;

}

}



/* 把字母从小到大排序 */

void compositor(char *pStr)

{

char temp;

int i, j;

for(i=0; i<iLength-1; i++)

for(j=i+1; j<iLength; j++)

if(pStr[i] > pStr[j])

{

temp = pStr[i];

pStr[i] = pStr[j];

pStr[j] = temp;

}

    printf("Now, the string is %s\n", pStr);

}



void Permute(char in[], char out[], int used[], int recursLev)

{

    int i;



    if(recursLev == iLength)

    {

        insert(out);

    }



    for(i = 0; i < iLength; i++)

    {

        if(used[i])          /* 如果这个字母已经使用,则跳到下一个字母 */

            continue;



        out[recursLev] = in[i];          /* 把这个字符填充入out序列 */

        used[i] = 1;                /* 标记这个字母已经被使用 */



        Permute(in, out, used, recursLev+1);



        used[i] = 0;          /* 取消字母标记 */

    }

}



int Init(char *inString)

{

    int i, *ipUsedFlag;

    char *cpOut;



    cpOut = (char *)malloc(iLength + 1);

    if(!cpOut)

        return 0;

    cpOut[iLength] = '\0';



    ipUsedFlag = (int *)malloc(sizeof(int) * iLength);

    if(!ipUsedFlag)

        return 0;



    for(i = 0; i < iLength; i++)    /* 初始化ipUsedFlag */

    {

        ipUsedFlag[i] = 0;

    }



    Permute(inString, cpOut, ipUsedFlag, 0);



    free(cpOut);

    free(ipUsedFlag);

    return 1;

}



void main()

{

    char Str;

struct node *p;

int i;



    printf("Please input the string:\n");

    gets(&Str);

iLength = strlen(&Str);

compositor(&Str);  /* 可以不要,只是为了好看 */

    Init(&Str);



/* 输出所有排列 */

    p = head;

for(i = 1; i <=sum; i++)

{

printf("%d : %s\n", i, p->string);

p = p->next;

}

}

B9层 发表时间: 06-04-27 12:33

回复: 286 [unique]   版主   登录
先加个预处理,把重复的去掉。
穷举的算法,以前写过一个,回头给你找找吧。

B10层 发表时间: 06-04-27 17:42

回复: sniper167 [sniper167]   论坛用户   登录
我那个还有问题
超过5个字符 在VC 6.0下有问题
在Linux下我没发现这个问题  改天找找    最近忙着写毕业论文

PS:  N久没见286咯 

B11层 发表时间: 06-04-28 10:38

回复: ProgramLive [coolcall]   论坛用户   登录
若为3位字符串,把它们转换为数值方式计算
做个3进制的,用穷举法,输出的数值与当前字符对应
这样应该可以

B12层 发表时间: 06-04-29 19:13

回复: zhoen889 [zhoen889]   论坛用户   登录
我也写了一个,是基于递归的,不过算来算去,时间复杂度都很高,甚至达到了O(n!)
我把算法整理后帖上来,大家研究研究
有更好的算法的兄弟帖上来啊



B13层 发表时间: 06-05-06 20:30

回复: zuiaizhy [zuiaizhy]   论坛用户   登录
比如有n个字符串
那么这个字符串的全排列就是
N*N-1*N-2*N-3*N-4……*2*1
理论上是这样
实践中最后的*1是不需要的

B14层 发表时间: 06-06-24 05:30

回复: yeniaoer [yeniaoer]   论坛用户   登录
先定义输入
用数学的排列组合函数
就这么简单嘛
昏哦

B15层 发表时间: 07-03-17 18:37

论坛: 编程破解

20CN网络安全小组版权所有
Copyright © 2000-2010 20CN Security Group. All Rights Reserved.
论坛程序编写:NetDemon

粤ICP备05087286号