s*******y
发帖数: 105 | 1 求一个string的所有的permutation. C code如下：
int permutations(char *str)
{
int length, i, *used;
char *out;
length = strlen(str);
out = (char *)malloc(length+1);
if(!out)
return 0;
out[length] = '\0';
used = (int*)malloc(sizeof(int)*length);
if(!used)
return 0;
for(i=0;i
used[i]=0;
DoPermute(str, out, used, length, 0);
free(out);
free(used);
return 1;
}
void DoPermute(char *str, char* out, int* used, int length, int recursLev)
{
int i;
if(recursLev==length)
{
printf("%s\n", out);
return;
}
for(i=0;i
{
if(used[i])
continue;
out[recursLev] = str[i];
used[i] = 1;
DoPermute(str, out, used, length, recursLev+1);
used[i]=0;
}
} |
s*******y
发帖数: 105 | 2 不是很理解这里的recursion.
举例来说：
With input "hat",
1. value of i =0, out[0] = 'h', used[0]=1, recursive call (I assume i=0,
recursLev =0, is pushed on to the stack)
2. i =0 continue, i=1 out[1]='a', used[1] = 1, recursive call (i =1,
recurseLev =1 on stack)
3. i=0,1 continue, i=1 out[2] = 't', used[2] = 1, recursive call(i=2,
recurseLev=2 on stack)
4. Line 31 is executed, "hat" is printed out and it returns.
It is from here that I am confused. This is what I think happens:
5. Return to line 45, pop i from stack, used[2]=0, i incremented to 3, break
out of the loop.
Could you like trace it from here for 1 run? I just want to be clear in my
head as to how these recursive calls work?
I mean the way I think this code works is: print out the first character and
then permute the other 2 i.e. "h" and permute "at" to get "hat" and "hta"
respectively. What I also cannot figure out is where the swapping of
characters a and t is done to output "hta"?
Thanks again for all your help. |
p*****2
发帖数: 21240 | 3 前几天有人给了一个非常精巧的code。利用swap字符。 |
f*******t
发帖数: 7549 | 4 #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
if(i != index && arr[i] == arr[index])
continue;
swap(arr, i, index);
permutation(arr, index+1, size);
swap(arr, i, index);
}
}
}
int main()
{
char characters[6] = "aacd";
permutation(characters, 0, 4);
return 0;
}
这是我上次贴的代码的改进版，能处理含重复字母的字符串 |
p*****2
发帖数: 21240 | 5
好呀。大牛。
【在 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) {
: if (index == size) {
|
g*********8
发帖数: 64 | 6 跟风写一个C++版本的
void string_permute_noduplicate(string str, int d){
if(d==str.length()){
cout<
return;
}
else{
char lastswap=' ';
for(unsigned int i=d;i
if(str[i]==lastswap) continue;
else{
lastswap=str[i];
swap(str[i],str[d]);
string_permute_noduplicate(str,d+1);
swap(str[i],str[d]);
}
}
}
} |
g*********8
发帖数: 64 | 7 这题还可以扩展到输出大小为m的一个数组的所有子集以及给定一个电话号码输出所有
可能的字符串。
void SubArrayS_size_m(vector v, int m,int l, vector& output){
if(l==m){
for(int i=0;i
cout<
cout<
return;
}
else{
for(int i=l;i
output[l]=v[i];
SubArrayS_size_m(v,m,l+1,output);
}
}
} |
A**u
发帖数: 2458 | 8 大牛
if(i != index && arr[i] == arr[index])
continue;
这是什么意思
【在 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) {
: if (index == size) {
|
l*****a
发帖数: 14598 | 9 remove duplicate
you can try to find some samples and print the result
【在 A**u 的大作中提到】
: 大牛
: if(i != index && arr[i] == arr[index])
: continue;
: 这是什么意思
|
l*****a
发帖数: 14598 | 10 注意别忘了提一下，需要对输入进行排序
【在 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) {
: if (index == size) {
|
|
|
f*******t
发帖数: 7549 | 11 如果不考虑输出的顺序，就不用对输入排序
【在 l*****a 的大作中提到】
: 注意别忘了提一下，需要对输入进行排序
|
l*****a
发帖数: 14598 | 12 then how will you avoid duplicate?
【在 f*******t 的大作中提到】
: 如果不考虑输出的顺序，就不用对输入排序
|
A**u
发帖数: 2458 | 13 太聪明了
终于看明白啦
【在 l*****a 的大作中提到】
: remove duplicate
: you can try to find some samples and print the result
|
s*******y
发帖数: 105 | 14 假如
char characters[6] = "cdaa";
就变成22个output了 好像不太对
【在 f*******t 的大作中提到】
: 如果不考虑输出的顺序，就不用对输入排序
|
z******t
发帖数: 59 | 15 字符串的排列：
http://zhedahht.blog.163.com/blog/static/254111742007499363479/
字符串的组合：
http://zhedahht.blog.163.com/blog/static/2541117420114172812217
【在 s*******y 的大作中提到】
: 求一个string的所有的permutation. C code如下：
: int permutations(char *str)
: {
: int length, i, *used;
: char *out;
: length = strlen(str);
: out = (char *)malloc(length+1);
: if(!out)
: return 0;
: out[length] = '\0';
|
B*******1
发帖数: 2454 | |
g*********8
发帖数: 64 | |
p*****2
发帖数: 21240 | 18
你试一下 10 4 4 2
【在 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) {
: if (index == size) {
|
f*******t
发帖数: 7549 | 19 我这个代码确实不能处理duplicate，身败名裂了
【在 p*****2 的大作中提到】
:
: 你试一下 10 4 4 2
|
p*****2
发帖数: 21240 | 20
那应该怎么处理呢？
【在 f*******t 的大作中提到】
: 我这个代码确实不能处理duplicate，身败名裂了
|
|
|
l*****a
发帖数: 14598 | 21 上面不是说了吗
排了序就可以了
【在 p*****2 的大作中提到】
:
: 那应该怎么处理呢？
|
f*******t
发帖数: 7549 | 22 我改进了一下，这回貌似行了，不过输出没能按照字典序：
#include
#include
#include
using namespace std;
void swap(string& s, int idx1, int idx2) {
if(idx1 == idx2)
return;
char temp = s[idx1];
s[idx1] = s[idx2];
s[idx2] = temp;
}
void permutation(string& s, int index, int size) {
if (index == size)
cout << s << endl;
else {
char last = 0;
for (int i=index; i
if(s[i] == last)
continue;
swap(s, i, index);
permutation(s, index+1, size);
swap(s, i, index);
last = s[i];
}
}
}
int main()
{
string s("ccaab");
sort(s.begin(), s.end());
permutation(s, 0, s.size());
return 0;
}
【在 p*****2 的大作中提到】
:
: 那应该怎么处理呢？
|
p*****2
发帖数: 21240 | 23 我试试了，sort以后还是不行。
【在 l*****a 的大作中提到】
: 上面不是说了吗
: 排了序就可以了
|
s*****n
发帖数: 162 | 24 Following is a solution based on the very interesting method called Knuth’s
Permutations. This has the duplicate permutation avoidance logic built-in.
The first call to the method is StringPermutation(str, 0).
void StringPermutation(char* str, int k) {
if (!str || (k < 0))
return;
if (str[k] == '\0') {
cout << str << endl;
return;
}
StringPermutation(str, k + 1);
int i;
for (i = k;(i > 0) && (str[i] != str[i - 1]);i--) {
char t = str[i];
str[i] = str[i - 1];
str[i - 1] = t;
StringPermutation(str, k + 1);
}
char t = str[i];
for (int j = i;j < k;j++)
str[j] = str[j + 1];
str[k] = t;
} |
L**********u
发帖数: 194 | 25
【在 s*******y 的大作中提到】
: 求一个string的所有的permutation. C code如下：
: int permutations(char *str)
: {
: int length, i, *used;
: char *out;
: length = strlen(str);
: out = (char *)malloc(length+1);
: if(!out)
: return 0;
: out[length] = '\0';
|
L**********u
发帖数: 194 | 26 I solved this problem several days ago. hehe
My algorithm is following:
//print out all permutations of a given string.
//A string with n characters has n! permutations
//The permutations can be obtained by the following method.
//n=1, only one permutation 1
//n=2, permutations are obtained by inserting 2 to every possible positions
of each string obtained when n=1
// there are two possible positions and one string, therefore
permutations are
// 21 12
//n=3, permutations are obtained by inserting 3 to every possible positions
of each string obtained when n=2
// there are 3 positions for each string and there are 2 strings in
total, therefore, permutations are
// 321 231 213 312 132 123
//generalize the method described as above, we can get all permutation of a
//string with n characters by iteration.
【在 s*******y 的大作中提到】
: 求一个string的所有的permutation. C code如下：
: int permutations(char *str)
: {
: int length, i, *used;
: char *out;
: length = strlen(str);
: out = (char *)malloc(length+1);
: if(!out)
: return 0;
: out[length] = '\0';
|
k***t
发帖数: 276 | 27 This one is perfect now. How about combination with the handling of duplicated items?
【在 f*******t 的大作中提到】
: 我改进了一下，这回貌似行了，不过输出没能按照字典序：
: #include
: #include
: #include
: using namespace std;
: void swap(string& s, int idx1, int idx2) {
: if(idx1 == idx2)
: return;
: char temp = s[idx1];
: s[idx1] = s[idx2];
|
f*******t
发帖数: 7549 | 28 呃，什么是“combination with the handling of duplicated items”？
duplicated items?
【在 k***t 的大作中提到】
: This one is perfect now. How about combination with the handling of duplicated items?
|
k***t
发帖数: 276 | 29 Given a string, print out all subsets. Each subset is a string with some, or
all, characters in the original string.The original string may have
duplicated characters. The output shouldn't contain any duplicated subset
strings.
【在 f*******t 的大作中提到】
: 呃，什么是“combination with the handling of duplicated items”？
:
: duplicated items?
|
p*****2
发帖数: 21240 | 30 这个work, 也是要先sort。
【在 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) {
: if (index == size) {
|
|
|
L**********u
发帖数: 194 | 31 This problem can be solved by binary representation of an integer.
I am a rookie of C++. thanks for comments
my codes
#include
#include
#include
using namespace std;
const int N=5;
void subset(int arr[], int n)
{
bitset n_bit(n);
cout<<"{";
for(int i=0;i
if(n_bit[i]==1)
cout<
cout<<"};";
cout<
}
//main function
int main()
{
cout<<"The set has "<
int arr[N];
for(int i=0;i
arr[i]=1000*(1.0*rand()/RAND_MAX);
cout<<"The input set is:"<
for(int i=0;i
cout<
cout<
//print all subsets
cout<<"The subsets are:"<
cout<<"{"<<" }"<
int n=1;
for(int i=0;i
{
for(int k=n;k<2*n;++k)
subset(arr,k);
n*=2;
}
return 0;
}
or
【在 k***t 的大作中提到】
: Given a string, print out all subsets. Each subset is a string with some, or
: all, characters in the original string.The original string may have
: duplicated characters. The output shouldn't contain any duplicated subset
: strings.
|
f*******t
发帖数: 7549 | 32 #include
#include
#include
#define BUFFSIZE 1024
using namespace std;
char buff[BUFFSIZE];
int idx;
void enumerate(const string& s, int pos)
{
if(pos == s.size()) {
if(idx == 0)
printf("{Empty}\n");
buff[idx] = 0;
printf("%s\n", buff);
}
else if(pos != 0 && s[pos] == s[pos-1]) {
enumerate(s, pos+1);
}
else {
buff[idx] = s[pos];
idx++;
enumerate(s, pos+1);
idx--;
enumerate(s, pos+1);
}
}
int main()
{
string s("ccabddd");
sort(s.begin(), s.end());
idx = 0;
enumerate(s, 0);
return 0;
}
or
【在 k***t 的大作中提到】
: Given a string, print out all subsets. Each subset is a string with some, or
: all, characters in the original string.The original string may have
: duplicated characters. The output shouldn't contain any duplicated subset
: strings.
|
g**********y
发帖数: 14569 | 33 没仔细看后面回帖，贴一个Java解，就是实现next_permute()。对任意输入串，把字母
排序，然后调用就行。
这里的main()就是给了个简单例子。
public class NextPermute {
/**
* Return next permute number/string in sequence. If already highest,
* return null.
*
* @param number
* @return
*/
public String nextPermute(String s) {
int N = s.length();
StringBuilder sb = new StringBuilder(s);
int head = N - 2;
while (head >= 0 && sb.charAt(head) >= sb.charAt(head+1)) head--;
if (head < 0) return null;
int tail = N - 1;
while (sb.charAt(head) >= sb.charAt(tail)) tail--;
char t = sb.charAt(head);
sb.setCharAt(head, sb.charAt(tail));
sb.setCharAt(tail, t);
return sb.substring(0, head+1) + reverse(sb.substring(head+1, N));
}
private String reverse(String s) {
return new StringBuilder(s).reverse().toString();
}
public static void main(String[] args) {
NextPermute np = new NextPermute();
int total = 1;
String s = "111223";
System.out.println(s);
while ( (s = np.nextPermute(s)) != null) {
total++;
System.out.println(s);
}
System.out.println("Total = " + total);
}
}
【在 p*****2 的大作中提到】
: 这个work, 也是要先sort。
|
z******t
发帖数: 59 | 34 客气了，呵呵
是区区小可
新年快乐^_^
【在 B*******1 的大作中提到】
: 你就是何海涛？
: 传说中的100题就是你老的？
|
j*****j
发帖数: 201 | 35 网易博客上的方法似乎不能处理重复字符啊，比如输入“aab"，输出了两个"aab"
【在 z******t 的大作中提到】
: 客气了，呵呵
: 是区区小可
: 新年快乐^_^
|
