b******a
发帖数: 215 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: bugzilla (report a bug to me), 信区: JobHunting
标 题: 来，做题吧。
发信站: BBS 未名空间站 (Sun Nov 11 02:01:16 2007), 转信
给定一个长度为6，含有重复字母的字符串，写程序列出所有不重合的排列. |
t****t
发帖数: 6806 | 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****u
发帖数: 118 | 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****t
发帖数: 6806 | 4 哦，没看到还有个返回值
【在 s****u 的大作中提到】
: do {} while (next_permutation)...
|
p**s
发帖数: 2707 | 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****r
发帖数: 115 | 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******a
发帖数: 215 | 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***e
发帖数: 793 | 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;i
if(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**s
发帖数: 2707 | 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*****g
发帖数: 119 | 10 next_permutation() assumes input sequence is sorted in ascending order using
operator<.
【在 p**s 的大作中提到】
: 1.我问的是为什么要sort，不是什么是next_permutation
: 2.你的next_permutation解释得也不完全
|
|
|
z***e
发帖数: 5393 | 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****u
发帖数: 118 | 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****u
发帖数: 118 | 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******a
发帖数: 215 | 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****u
发帖数: 118 | 15 要不重复的不难写，但是我没有用过这样靠交换枚举的方法，我去想想-_-
【在 b******a 的大作中提到】
: 对啊。我写了一个用来排除重复字母的，但是还是有问题。
: 比如输入 aabbcc.还是有重复的。
: code如下，牛人帮俺改正一下。
: 输入字符串是经过排序的，这样所有相同的字母会在一起，比如aabbcc.
: 算法就是把头字符跟剩下的字符轮流交换，然后递归。如果交换的两个处于不同位置字
: 母相同的话，那么就跳过这个字符，继续进行下一轮的交换。
: /*
: char* input: input string;
: int pos: start position, for all string permutation, should start from 0.
: */
|
b******a
发帖数: 215 | 16 举个例子 abcd来排列，
先固定 a,来排列 bcd
再固定 b,来排列 acd，
再固定 c,来排列 bad，
再固定 d,来排列 bca，
对于 aa bb cc这样的，
当第一个a 与第二个a交换是，由于交换后的字串是不变的，所以就跳过这个交换，进入
a与b的交换。因为已经排过序了，所以所有相同的字符都是在一起的。
我就搞不清为什么还会出来相同的串了。
【在 s****u 的大作中提到】
: 要不重复的不难写，但是我没有用过这样靠交换枚举的方法，我去想想-_-
|
s****u
发帖数: 118 | 17 交换的话我不知道怎么判重。。。
我知道的穷举方法是每个字母数数有多少个
比如aabbcc变成
a b c
2 2 2
这样表示
然后枚举就可以了
【在 b******a 的大作中提到】
: 对啊。我写了一个用来排除重复字母的，但是还是有问题。
: 比如输入 aabbcc.还是有重复的。
: code如下，牛人帮俺改正一下。
: 输入字符串是经过排序的，这样所有相同的字母会在一起，比如aabbcc.
: 算法就是把头字符跟剩下的字符轮流交换，然后递归。如果交换的两个处于不同位置字
: 母相同的话，那么就跳过这个字符，继续进行下一轮的交换。
: /*
: char* input: input string;
: int pos: start position, for all string permutation, should start from 0.
: */
|
s****u
发帖数: 118 | 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****u
发帖数: 118 | 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******a
发帖数: 215 | 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****u
发帖数: 118 | 21 你用13327那个模拟好了，那样应该是最快的
我记得以前在一个离散数学的书上看到过模拟的方法，不过忘记了
【在 b******a 的大作中提到】
: 谢谢。
: 我知道了。
: 交换后的字串还是要排序的。
|
r****r
发帖数: 115 | 22 不是我解释的，copy+paste过来
就是不明白你既然知道next_permutation居然还不知道为什么要sort
【在 p**s 的大作中提到】
: 1.我问的是为什么要sort，不是什么是next_permutation
: 2.你的next_permutation解释得也不完全
|
p**s
发帖数: 2707 | 23 1.你自己把trust的code里sort一行去掉，看看结果再说
2.看来你还是不知道next_permutation所以不知道为什么可以不要sort
【在 r****r 的大作中提到】
: 不是我解释的，copy+paste过来
: 就是不明白你既然知道next_permutation居然还不知道为什么要sort
|
t****t
发帖数: 6806 | 24 呵呵，好了好了
我那个写法是自己判循环，可以不要sort
如果用返回值，就要sort了
总的来说，sort一下比较便宜一些，要不然每次都要比较
最后，不许叫我trust
【在 p**s 的大作中提到】
: 1.你自己把trust的code里sort一行去掉，看看结果再说
: 2.看来你还是不知道next_permutation所以不知道为什么可以不要sort
|
p**s
发帖数: 2707 | 25 为什么这里人人都叫你trust就不许我叫。。。
【在 t****t 的大作中提到】
: 呵呵，好了好了
: 我那个写法是自己判循环，可以不要sort
: 如果用返回值，就要sort了
: 总的来说，sort一下比较便宜一些，要不然每次都要比较
: 最后，不许叫我trust
|
t****t
发帖数: 6806 | 26 人人？什么人人？叫我trust的都是猪
【在 p**s 的大作中提到】
: 为什么这里人人都叫你trust就不许我叫。。。
|
c********x
发帖数: 84 | 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. |
