打印字符串的所有排列 [英] print all permutations of string
问题描述
嘿，任何人都可以帮我写c（函数）中的代码打印
字符串的所有排列。请帮助
hey can anyone help me in writing a code in c (function) that prints
all permutations of a string.please help
推荐答案
anurag写道：
anurag wrote:
嘿，任何人都可以帮我编写c（函数）中打印的代码
字符串的所有排列。请帮助
hey can anyone help me in writing a code in c (function) that prints
all permutations of a string.please help
请问，对于C问题，不要交叉发布到comp.lang.c ++。谢谢！
V
-
请在通过电子邮件回复时删除资金''A' />
我没有回复最热门的回复，请不要问
Please, for C questions do not cross-post to comp.lang.c++. Thanks!
V
--
Please remove capital ''A''s when replying by e-mail
I do not respond to top-posted replies, please don''t ask
[comp.lang.c ++ snipped - followups设置为comp。 lang.c]
anurag说：
[comp.lang.c++ snipped - followups set to comp.lang.c]
anurag said:
嘿，任何人都可以帮我编写c（函数）中的代码打印
字符串的所有排列。请帮助
hey can anyone help me in writing a code in c (function) that prints
all permutations of a string.please help
考虑如何手动执行此操作。例如，让我们看一下
字符串ABCD。我们可以把这个字符串的排列想象为
分为四组（因为字符串长度为四个字符）：
1）所有字符串从A开始并继续进行一些排列
BCD
2）所有字符串以B开头并继续进行一些排列
CDA
3）所有字符串以C开头并继续进行一些排列
DAB
4）所有字符串以D开头并继续一些排列
ABC
正如您可能想象的那样，只需移动字符串
即可轻松获得这些设置。
让我们看一下这些集合中的一个（因为其他的以相同的方式处理
），显然是：字符串开头A继续使用BCD的一些
排列。
我们现在面临的问题是找到包含BCD的所有字符串
（我们可以简单地附加到A来获得完整的排列。
我们可以把这个字符串的排列分成三个
集（因为字符串是三个字符长）：
1）所有字符串以B开头并继续进行一些排列
CD
2）所有字符串以C开头并继续进行一些排列
DB
3）所有字符串以D开头并继续进行一些排列
BC
正如您可能想象的那样，您可以通过稍微移动字符串
来获得这些设置。
让我们看看其中一个集合（因为其他集合以相同的方式处理
），显然是：以（A和B）开头的字符串和
继续CD的一些排列。
我们现在面临的问题是找到包含CD的所有字符串
（我们可以简单地附加AB得到完整的排列）。
我们可以把这个字符串的排列分成两个
集（因为字符串是两个字符）长）：
1）所有字符串以C开头并继续D / / $
的所有字符串2）所有字符串以D开头并继续C的排列
正如您可能想象的那样，您可以通过稍微移动字符串
来获得这些设置。
让我们看看其中一个集合（因为其他集合以相同的方式处理
），显然是：字符串以（A然后是B然后）开头C，
并继续D的一些排列。
我们现在面临的问题是找到包含D的所有字符串
（我们可以简单地附加到ABC来获得完整的排列）。
我们可以把这个字符串的排列分成一个
set（因为字符串是一个字符长）：
1）所有以D开头的字符串 - 当然很明显。
执行此操作的规范方法是通过递归，传入字符串，
以及尚未置换的项目数。如果该数字为0，则
只显示字符串。否则，绕着最左边的
尚未处理的字符循环，并在循环内用n-1递归。
现在对它进行破解亲爱的，让我们知道你是怎么过的。
-
Richard Heathfield
Usenet是一个奇怪的地方 ; - dmr 29/7/1999
http://www.cpax.org.uk
电子邮件：rjh在上面的域名（但显然放弃了www）
Consider how you would do this by hand. For example, let''s look at the
string "ABCD". We can think of the permutations of this string as being
divided into four sets (because the string is four characters long):
1) All the strings starting with A and continuing with some permutation of
BCD
2) All the strings starting with B and continuing with some permutation of
CDA
3) All the strings starting with C and continuing with some permutation of
DAB
4) All the strings starting with D and continuing with some permutation of
ABC
As you might imagine, you can get at these sets simply by moving the string
around a little.
Let''s look at just one of these sets (because the others are dealt with in
the same way, obviously): strings starting with A and continuing with some
permutation of BCD.
We are now faced with the problem of finding all the strings containing BCD
(which we can simply append to A to get the full permutation).
We can think of the permutations of this string as being divided into three
sets (because the string is three characters long):
1) All the strings starting with B and continuing with some permutation of
CD
2) All the strings starting with C and continuing with some permutation of
DB
3) All the strings starting with D and continuing with some permutation of
BC
As you might imagine, you can get at these sets simply by moving the string
around a little.
Let''s look at just one of these sets (because the others are dealt with in
the same way, obviously): strings starting with (A and then) B and
continuing with some permutation of CD.
We are now faced with the problem of finding all the strings containing CD
(which we can simply append to AB to get the full permutation).
We can think of the permutations of this string as being divided into two
sets (because the string is two characters long):
1) All the strings starting with C and continuing with some permutation of D
2) All the strings starting with D and continuing with some permutation of C
As you might imagine, you can get at these sets simply by moving the string
around a little.
Let''s look at just one of these sets (because the others are dealt with in
the same way, obviously): strings starting with (A and then B and then) C,
and continuing with some permutation of D.
We are now faced with the problem of finding all the strings containing D
(which we can simply append to ABC to get the full permutation).
We can think of the permutations of this string as being divided into one
set (because the string is one character long):
1) All the string starting with D - which is obvious, of course.
The canonical way to do this is via recursion, passing in the string,
together with the number of items yet to be permuted. If that number is 0,
simply display the string. Otherwise, loop around the leftmost
not-yet-handled character and, within the loop, recurse with n-1.
Now take a crack at it yourself, and let us know how you get on.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
----- BEGIN PGP签名消息-----
哈希：SHA1
anurag写道：
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
anurag wrote:
嘿，任何人都可以帮我写作c（函数）中的代码打印
字符串的所有排列。请帮助
hey can anyone help me in writing a code in c (function) that prints
all permutations of a string.please help
IIRC，这个优惠被请求了一个数字最近几周的时间。
我想知道为什么突然对使用C
函数置换字符串感兴趣。
无论如何，给出RH讨论的具体例子
elsethread，这是我几周前做的一次尝试，当时问题首先出现了问题。按照你的意愿去做。
对于常客：是的，我知道回答作业问题是
皱眉apon，更糟糕的是回答一个算法问题，但
这个引起了我的兴趣。所以，对于我一年的免费赠品，我发布这个
代码;-)
== snip ==
#include< stdio.h>
#include< stdlib.h>
#include< string.h>
void rotate（无符号长度，字符*字符串）
{
char save;
save = * string;
while（ - length）
{
* string = *（string + 1）;
++ string;
}
* string = save;
}
void permute （无符号长度，字符*字符串，无符号深度）
{
if（length == 0）
printf（" ;％s \ n"，string-depth）;
else
{
无符号数;
for（count = length; count 0; --count）
{
permute（length-1，string + 1，depth + 1）;
旋转（长度，字符串）;
}
}
}
int main（int argc，char ** argv）
{
while（--argc ）
{
char * source = malloc（strlen（* ++ argv）+1）;
if（source ）
{
strcpy（source，* argv）;
printf（" \ nPermuting \"％s \" ; \ n"，source）;
permute（strlen（source），source，0）;
free（source）;
}
}
返回EXIT_SUCCESS;
}
== snip = =
- -
Lew Pitcher
-----开始PGP签名-----
版本：GnuPG v1.4.3（MingW32） - WinPT 0.11.12
iD8DBQFEv84lagVFX4UWr64RAq3YAKDBs4 // FGSrc + zn7 + duG2bRtCuRaQCfSnOS
mg6QbOGNExUVVsXBp5lQYD8 = < br $>
= pYBy
-----结束PGP签名-----
IIRC, this favour has been requested a number of times in recent weeks.
I wonder why the sudden interest in permuting strings using C
functions.
In any case, to give a concrete example of what R.H. discusses
elsethread, here''s an attempt I made a few weeks ago, when the question
first came up. Take it as you will.
For the regulars: yes I know that answering a homework question is
frowned apon, and even worse is answering an algorithm question, but
this one piqued my interest. So, for my one freebie a year, I post this
code ;-)
==snip==
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void rotate(unsigned length, char *string)
{
char save;
save = *string;
while(--length)
{
*string=*(string+1);
++string;
}
*string = save;
}
void permute(unsigned length, char *string, unsigned depth)
{
if (length == 0)
printf("%s\n",string-depth);
else
{
unsigned count;
for (count = length ; count 0; --count)
{
permute(length-1,string+1,depth+1);
rotate(length,string);
}
}
}
int main(int argc, char **argv)
{
while (--argc)
{
char *source = malloc(strlen(*++argv)+1);
if (source)
{
strcpy(source,*argv);
printf("\nPermuting \"%s\"\n",source);
permute(strlen(source),source,0);
free(source);
}
}
return EXIT_SUCCESS;
}
==snip==
- --
Lew Pitcher
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (MingW32) - WinPT 0.11.12
iD8DBQFEv84lagVFX4UWr64RAq3YAKDBs4//FGSrc+zn7+duG2bRtCuRaQCfSnOS
mg6QbOGNExUVVsXBp5lQYD8=
=pYBy
-----END PGP SIGNATURE-----
这篇关于打印字符串的所有排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
