来，做题吧。 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

来，做题吧。

来，做题吧。# Programming - 葵花宝典

b*a2007-11-11 08:11

1 楼

【以下文字转载自 JobHunting 讨论区】
发信人: bugzilla (report a bug to me), 信区: JobHunting
标题: 来，做题吧。
发信站: BBS 未名空间站 (Sun Nov 11 02:01:16 2007), 转信
给定一个长度为6，含有重复字母的字符串，写程序列出所有不重合的排列.

t*t2007-11-11 08:11

2 楼

void all_perm(const string& s)
{
string s1=s;
sort(s1.begin(), s1.end());
string s2=s1;
do {
cout<next_permutation(s1.begin(), s1.end());
} while (s1!=s2);
}

【在 b******a 的大作中提到】

: 【以下文字转载自 JobHunting 讨论区】
: 发信人: bugzilla (report a bug to me), 信区: JobHunting
: 标题: 来，做题吧。
: 发信站: BBS 未名空间站 (Sun Nov 11 02:01:16 2007), 转信
: 给定一个长度为6，含有重复字母的字符串，写程序列出所有不重合的排列.

s*u2007-11-11 08:11

3 楼

do {} while (next_permutation)...

【在 t****t 的大作中提到】

: void all_perm(const string& s)
: {
: string s1=s;
: sort(s1.begin(), s1.end());
: string s2=s1;
: do {
: cout<: next_permutation(s1.begin(), s1.end());
: } while (s1!=s2);
: }

t*t2007-11-11 08:11

4 楼

哦，没看到还有个返回值

【在 s****u 的大作中提到】

: do {} while (next_permutation)...

p*s2007-11-11 08:11

5 楼

为什么要sort?

【在 t****t 的大作中提到】

: void all_perm(const string& s)
: {
: string s1=s;
: sort(s1.begin(), s1.end());
: string s2=s1;
: do {
: cout<: next_permutation(s1.begin(), s1.end());
: } while (s1!=s2);
: }

r*r2007-11-11 08:11

6 楼

The next_permutation() function attempts to transform the given range of ele
ments [start,end) into the next lexicographically greater permutation of ele
ments. If it succeeds, it returns true, otherwise, it returns false.

【在 p**s 的大作中提到】

: 为什么要sort?

b*a2007-11-11 08:11

7 楼

不是调用lib，是自己写。呵呵。

【在 t****t 的大作中提到】

: void all_perm(const string& s)
: {
: string s1=s;
: sort(s1.begin(), s1.end());
: string s2=s1;
: do {
: cout<: next_permutation(s1.begin(), s1.end());
: } while (s1!=s2);
: }

s*e2007-11-11 08:11

8 楼

发信人: shaye (wonderfull), 信区: JobHunting
标题: Re: 来，做题吧。
发信站: BBS 未名空间站 (Sun Nov 11 04:32:21 2007)
原来写过一个,应该work
bool nextPermutation(char* a, int n){
int pos=n-1;
while(pos>0 && a[pos]<=a[pos-1]) pos--;
if(pos==0)return false;
int s=pos;
int e=n-1;
while(e>s){std::swap(a[s],a[e]),s++;e--;}
for(int i=pos;iif(a[i]>a[pos-1]){
std::swap(a[i],a[pos-1]);
break;
}
return true;
}
void printAllPermutation(char* a, int n){
std::sort(a,a+n);
std::cout<while(nextPermutation(a,n)) std

【在 b******a 的大作中提到】

: 不是调用lib，是自己写。呵呵。

p*s2007-11-11 08:11

9 楼

1.我问的是为什么要sort，不是什么是next_permutation
2.你的next_permutation解释得也不完全

【在 r****r 的大作中提到】

: The next_permutation() function attempts to transform the given range of ele
: ments [start,end) into the next lexicographically greater permutation of ele
: ments. If it succeeds, it returns true, otherwise, it returns false.

c*g2007-11-11 08:11

10 楼

next_permutation() assumes input sequence is sorted in ascending order using
operator<.>
【在 p**s 的大作中提到】

: 1.我问的是为什么要sort，不是什么是next_permutation
: 2.你的next_permutation解释得也不完全

z*e2007-11-11 08:11

11 楼

呃，我只会brute force穷举，这是前一阵用C#写的对一个string得全部permutation:
ArrayList GetAllPermutations(String s)
{
ArrayList list= new ArrayList();;
if (s.Length == 1)
{
list.Add(s);
return list;
}
for (int i = 0; i < s.Length; ++i)
{
String subStr = String.Concat(s.Substring(0, i), s.Substring
(i + 1, s.Length - (i + 1)));
ArrayList subResult = GetAllPermutations(sub

s*u2007-11-11 08:11

12 楼

解空间就是n!的，穷举没有问题
只是可能有重复枚举的，可以合并一下相同字母

【在 z***e 的大作中提到】

: 呃，我只会brute force穷举，这是前一阵用C#写的对一个string得全部permutation:
: ArrayList GetAllPermutations(String s)
: {
: ArrayList list= new ArrayList();;
: if (s.Length == 1)
: {
: list.Add(s);
: return list;
: }
: for (int i = 0; i < s.Length; ++i)

s*u2007-11-11 08:11

13 楼

单纯枚举permutation可以
void permutation(int depth, int len, string str) {
if (depth >= len) {
// aaa
return;
}
for (int i = depth; i < len; ++i) {
swap(str[i], str[depth]);
permutation(depth + 1, len, str);
swap(str[i], str[depth]);
}
}

【在 s****u 的大作中提到】

: 解空间就是n!的，穷举没有问题
: 只是可能有重复枚举的，可以合并一下相同字母

b*a2007-11-11 08:11

14 楼

对啊。我写了一个用来排除重复字母的，但是还是有问题。
比如输入 aabbcc.还是有重复的。
code如下，牛人帮俺改正一下。
输入字符串是经过排序的，这样所有相同的字母会在一起，比如aabbcc.
算法就是把头字符跟剩下的字符轮流交换，然后递归。如果交换的两个处于不同位置字
母相同的话，那么就跳过这个字符，继续进行下一轮的交换。
/*
char* input: input string;
int pos: start position, for all string permutation, should start from 0.
*/
void permutation(char* input,int pos)
{
int len;
int index;
char temp;

len=strlen(input);

if(pos==len-1)
{
printf("%s\n",input);

【在 s****u 的大作中提到】

: 解空间就是n!的，穷举没有问题
: 只是可能有重复枚举的，可以合并一下相同字母

s*u2007-11-11 08:11

15 楼

要不重复的不难写，但是我没有用过这样靠交换枚举的方法，我去想想-_-

【在 b******a 的大作中提到】

: 对啊。我写了一个用来排除重复字母的，但是还是有问题。
: 比如输入 aabbcc.还是有重复的。
: code如下，牛人帮俺改正一下。
: 输入字符串是经过排序的，这样所有相同的字母会在一起，比如aabbcc.
: 算法就是把头字符跟剩下的字符轮流交换，然后递归。如果交换的两个处于不同位置字
: 母相同的话，那么就跳过这个字符，继续进行下一轮的交换。
: /*
: char* input: input string;
: int pos: start position, for all string permutation, should start from 0.
: */

b*a2007-11-11 08:11

16 楼

举个例子 abcd来排列，
先固定 a,来排列 bcd
再固定 b,来排列 acd，
再固定 c,来排列 bad，
再固定 d,来排列 bca，
对于 aa bb cc这样的，
当第一个a 与第二个a交换是，由于交换后的字串是不变的，所以就跳过这个交换，进入
a与b的交换。因为已经排过序了，所以所有相同的字符都是在一起的。
我就搞不清为什么还会出来相同的串了。

【在 s****u 的大作中提到】

: 要不重复的不难写，但是我没有用过这样靠交换枚举的方法，我去想想-_-

s*u2007-11-11 08:11

17 楼

交换的话我不知道怎么判重。。。
我知道的穷举方法是每个字母数数有多少个
比如aabbcc变成
a b c
2 2 2
这样表示
然后枚举就可以了

【在 b******a 的大作中提到】

s*u2007-11-11 08:11

18 楼

void solve(int depth, int n, const char* str, int* cnt, char* path) {
if (depth >= n) {
path[depth] = 0;
// print path
return;
}
for (int i = 0; i < n; ++i) if (cnt[i] > 0) {
cnt[i]--;
path[depth] = str[i];
solve(depth + 1, n, str, cnt, path);
cnt[i]++;
}
}
这样枚举复杂度还是比较大的，但是如果输入很多重复，比如aaaaaa这样的会很快

交换的话我不知道怎么判重。。。
我知道的穷举方法是每个字母数数有多少个
比如aabbcc变成
a b c
2 2 2
这样表示
然后枚举就可以了

【在 s****u 的大作中提到】

: 交换的话我不知道怎么判重。。。
: 我知道的穷举方法是每个字母数数有多少个
: 比如aabbcc变成
: a b c
: 2 2 2
: 这样表示
: 然后枚举就可以了

s*u2007-11-11 08:11

19 楼

aabb -> abba
0123
可以 aabb -> abab (12交换) -> abba (23交换)
可以 aabb -> abba (13交换)

进入

【在 b******a 的大作中提到】

: 举个例子 abcd来排列，
: 先固定 a,来排列 bcd
: 再固定 b,来排列 acd，
: 再固定 c,来排列 bad，
: 再固定 d,来排列 bca，
: 对于 aa bb cc这样的，
: 当第一个a 与第二个a交换是，由于交换后的字串是不变的，所以就跳过这个交换，进入
: a与b的交换。因为已经排过序了，所以所有相同的字符都是在一起的。
: 我就搞不清为什么还会出来相同的串了。

b*a2007-11-11 08:11

20 楼

谢谢。
我知道了。
交换后的字串还是要排序的。

【在 s****u 的大作中提到】

: void solve(int depth, int n, const char* str, int* cnt, char* path) {
: if (depth >= n) {
: path[depth] = 0;
: // print path
: return;
: }
: for (int i = 0; i < n; ++i) if (cnt[i] > 0) {
: cnt[i]--;
: path[depth] = str[i];
: solve(depth + 1, n, str, cnt, path);

s*u2007-11-11 08:11

21 楼

你用13327那个模拟好了，那样应该是最快的
我记得以前在一个离散数学的书上看到过模拟的方法，不过忘记了

【在 b******a 的大作中提到】

: 谢谢。
: 我知道了。
: 交换后的字串还是要排序的。

r*r2007-11-11 08:11

22 楼

不是我解释的，copy+paste过来
就是不明白你既然知道next_permutation居然还不知道为什么要sort

【在 p**s 的大作中提到】

: 1.我问的是为什么要sort，不是什么是next_permutation
: 2.你的next_permutation解释得也不完全

p*s2007-11-11 08:11

23 楼

1.你自己把trust的code里sort一行去掉，看看结果再说
2.看来你还是不知道next_permutation所以不知道为什么可以不要sort

【在 r****r 的大作中提到】

: 不是我解释的，copy+paste过来
: 就是不明白你既然知道next_permutation居然还不知道为什么要sort

t*t2007-11-11 08:11

24 楼

呵呵，好了好了
我那个写法是自己判循环，可以不要sort
如果用返回值，就要sort了
总的来说，sort一下比较便宜一些，要不然每次都要比较
最后，不许叫我trust

【在 p**s 的大作中提到】

: 1.你自己把trust的code里sort一行去掉，看看结果再说
: 2.看来你还是不知道next_permutation所以不知道为什么可以不要sort

p*s2007-11-11 08:11

25 楼

为什么这里人人都叫你trust就不许我叫。。。

【在 t****t 的大作中提到】

: 呵呵，好了好了
: 我那个写法是自己判循环，可以不要sort
: 如果用返回值，就要sort了
: 总的来说，sort一下比较便宜一些，要不然每次都要比较
: 最后，不许叫我trust

t*t2007-11-11 08:11

26 楼

人人？什么人人？叫我trust的都是猪

【在 p**s 的大作中提到】

: 为什么这里人人都叫你trust就不许我叫。。。

c*x2007-11-11 08:11

27 楼

Here is my way:
1. Eleminate the multi occurrance char,
2, Use the bubble sort to swith the position of the char, each step
is a snap shot of the permutation you want.