i**9
发帖数: 351 | 1 前面有朋友onsite遇到的，print all permutations of a given string, 比较简洁的一
种backtrack解法
permute(char a[],int i,int n){
if(i==n){
//print string;
return;
}
for(int j=i;j
swap(a[i],a[j]);
permute(a,i+1,n);
swap(a[j],a[i]);
}
}
但是这个算法对于有重复字母的会输出很多重复的permutations,比如string "att"
会有这些个permutations
att
att
tat
tta
tta
tat
有很多重复的，被问到如何去掉重复的，有什么好的解法在打印出之前解决掉重复的吗？ | D*********y
发帖数: 876 | 2 说个brute force的解法，可以直接用原来的算法
输出结果放在一个二维array里，
然后把重复的去掉
简单来说就是用两个index
一个指向当前读到的string
一个指向unique string的结尾
每读到一个unique string，就把它加到之前的unique string结尾去
坐等高人给出复杂度更小的解法
估计就得改动原来的算法了 | g*********s
发帖数: 1782 | 3 std::next_permutation().
【在 D*********y 的大作中提到】
: 说个brute force的解法，可以直接用原来的算法
: 输出结果放在一个二维array里，
: 然后把重复的去掉
: 简单来说就是用两个index
: 一个指向当前读到的string
: 一个指向unique string的结尾
: 每读到一个unique string，就把它加到之前的unique string结尾去
: 坐等高人给出复杂度更小的解法
: 估计就得改动原来的算法了
| P********l
发帖数: 452 | | h***n
发帖数: 276 | 5 在backtracking的基础上，进行剪枝，举个例子，att的排列
当第一个字符确定是a，然后选第二个字符的时候，有t和t做candidate，第一次选择将
第一个t放在第二个位置，然后继续罗列相关的排列，当回朔回来重新选第二个位置的时
候，发现剩下的candidate，第二个t，在前面已经有同样的字符被选择过了，于是剪枝
，pass掉这个分支，这样的话，就避免了罗列相同的排列
所以，你给出的backtracking的程序框架可以继续使用，只是在每一步选择的时候要进
行book-keeping，不要选择以前选过的就可以了
的一
【在 i**9 的大作中提到】
: 前面有朋友onsite遇到的，print all permutations of a given string, 比较简洁的一
: 种backtrack解法
: permute(char a[],int i,int n){
: if(i==n){
: //print string;
: return;
: }
: for(int j=i;j: swap(a[i],a[j]);
: permute(a,i+1,n);
| i****d
发帖数: 35 | 6 TAOCP Vol.4介绍了一种据说很古老的方法，我觉得可行
唯一不便的是最开始需要把原始字符串拍个序
不过鉴于n! >> nlgn，所以我觉得也没啥问题
基本的思想是我们需要从1,2,3,...n 生成到 n,n-1,...1
只需要提供一个根据当前排列，生成下一个排列的方法就可以了
通过个例子也许更好描述一点
123
132
213
...
321
1. 每次从右向左扫描，碰到第一个a[j]停止，此时 a[j-1]....a[0] 是非递增的，但a
[j] < a[j-1]
比如说 132，我们就在1这个地方停止。因为从3往后看都是非递增的，但是从1看就不
是了，1<3。直观上理解，这时候后面的a[j-1]...a[0]已经是最大的了，要想更大，必
须得调整前面的数了。
2. 从a[j-1]...a[0]中找到一个刚好比a[i]大的数，交换a[j], a[i]。其实就是从0~j-
1扫描，碰到第一个a[i]>a[j]就找到了。或者你想二分查找也可以。
还是看132, 找到第一个比1大的是2，交换后变成231。
直观想的话，a[n-1]...a[j+1]我们显然不想动，因为只要活动a[j]...a[0]就肯定能生
成比当前排列大的排列了，比如说交换a[j]和a[j-1]肯定就比当前排列大了。
但是我们想生成下一个排列的话，必须刚刚好比当前排列大，这个时候就得从a[j-1]-a
[0]中找到个刚好比a[j]大的，与其交换。
3. 交换后a[j-1]..a[0]显然还是非递增序，反转a[j-1]...a[0]。
231 反转后面的31变成213，这就是下一个排列了。
这是因为a[j]的位置已经比原来大了，要刚好生成下一个排列，后面的a[j-1]...a[0]
这j个数应该排列成所有可能中的最小数，也就是非递减序。
其实基本原则就是想办法生成比当前排列大的，并且刚好比当前排列大的。
上面的方法显然也能处理重复的情况，比如说a是[122]，那么按照下标来看的话，上例
中的[1]a[2]a[3] 和 a[1][3][2] 生成出来都是 [122]。但是上文描述中找a[j]和a[i]
的时候都是用的严格>和严格<，所以从122可以直接跳到212了。
汗。。。自己看着都有点晕。。大家凑合着看吧....
的一
【在 i**9 的大作中提到】
: 前面有朋友onsite遇到的，print all permutations of a given string, 比较简洁的一
: 种backtrack解法
: permute(char a[],int i,int n){
: if(i==n){
: //print string;
: return;
: }
: for(int j=i;j: swap(a[i],a[j]);
: permute(a,i+1,n);
| g*********s
发帖数: 1782 | 7 this is just std::next_permutation().
【在 i****d 的大作中提到】
: TAOCP Vol.4介绍了一种据说很古老的方法，我觉得可行
: 唯一不便的是最开始需要把原始字符串拍个序
: 不过鉴于n! >> nlgn，所以我觉得也没啥问题
: 基本的思想是我们需要从1,2,3,...n 生成到 n,n-1,...1
: 只需要提供一个根据当前排列，生成下一个排列的方法就可以了
: 通过个例子也许更好描述一点
: 123
: 132
: 213
: ...
| i****d
发帖数: 35 | 8 这样...
不过面试直接说就是std::next_permutation会不会不太好...
【在 g*********s 的大作中提到】
: this is just std::next_permutation().
| h**********d
发帖数: 4313 | 9 put them into a HashSet then output?
的一
【在 i**9 的大作中提到】
: 前面有朋友onsite遇到的，print all permutations of a given string, 比较简洁的一
: 种backtrack解法
: permute(char a[],int i,int n){
: if(i==n){
: //print string;
: return;
: }
: for(int j=i;j: swap(a[i],a[j]);
: permute(a,i+1,n);
| g*********s
发帖数: 1782 | 10 why not. knowledge and understanding of stl algorithm is certainly a plus.
proper use of stl algorithm actually will make your code more robust, as
those are widely tested.
【在 i****d 的大作中提到】
: 这样...
: 不过面试直接说就是std::next_permutation会不会不太好...
| | | i****d
发帖数: 35 | 11 那是自然
但既然当面试题问了,我想考官应该会期望你把细节也说一下吧
实际用的时候,当然没必要自己实现
【在 g*********s 的大作中提到】
: why not. knowledge and understanding of stl algorithm is certainly a plus.
: proper use of stl algorithm actually will make your code more robust, as
: those are widely tested.
| g*********s
发帖数: 1782 | 12 by understanding i mean u know how the next_permutation works, in addition
to how to use this function.
【在 i****d 的大作中提到】
: 那是自然
: 但既然当面试题问了,我想考官应该会期望你把细节也说一下吧
: 实际用的时候,当然没必要自己实现
| i**9
发帖数: 351 | 13 看样子把 backtracking algorithm 改造成没有duplicate output有点困难，根据大家
的建议谢了一个简易版的 next_permutation (参考了 PuTTYshell 的 link
http://code.google.com/p/sureinterview/source/browse/src/lib/co
)
void next_permutation(char a[],int n,bool & next,bool &first){
int k=n-2;
if(first){
first = false;
print(a,n);
return;
}
next = false;
for(;k>=0;k--){
if(a[k] < a[k+1]){
next = true;
break;
}
}
if(!next){
return;
}
int l=n-1;
for(;a[k]>=a[l];l--){
}
swap(a[k],a[l]);
for (int i = k + 1, j = n - 1; i < j; i++, j--) {
swap(a[i], a[j]);
}
print(a,n);
}
int main(){
char a[3]={'a','t','t'};
bool next = true;
bool first = true;
while(next){
next_permutation(a,3,next,first);
}
} | J*******i
发帖数: 2162 | 14 我的一个解法，有些细节没有完全优化
import java.util.*;
public class StrPermute {
public static void main (String[] args) {
strPermute(args[0]);
}
public static void strPermute (String str) {
char[] ori = str.toCharArray();
boolean[] avail = new boolean[ori.length];
for (int i=0;i
avail[i] = true;
char[] result = new char[ori.length];
permute(ori, avail, result, 0);
}
public static void permute (char[] ori, boolean[] avail, char[] result,
int idx) {
if (idx == result.length) {
System.out.println(result);
return;
}
HashSet already = new HashSet();
for (int i=0;i
if (avail[i]) {
if (!already.contains(ori[i])) {
already.add(ori[i]);
avail[i] = false;
result[idx] = ori[i];
permute(ori, avail, result, idx+1);
avail[i] = true;
}
}
}
}
} | J*******i
发帖数: 2162 | 15 用这样的思路，楼主的方法这样改一下应该就可以了吧？
public static void permute (char[] a, int i, int n) {
if(i==n){
System.out.println(a);
return;
}
HashSet already = new HashSet();
for(int j=i;j
if (!already.contains(a[j])) {
already.add(a[j]);
swap(a, i, j);
permute(a,i+1,n);
swap(a, j, i);
}
}
} | l*****e
发帖数: 1374 | 16 for循环是从a[i]~a[n]中依次选一个字母作为下一个分支，如果a[i]~a[n]有重复的，
就没必要再选择了，这个分支就可以去掉。
的一
【在 i**9 的大作中提到】
: 前面有朋友onsite遇到的，print all permutations of a given string, 比较简洁的一
: 种backtrack解法
: permute(char a[],int i,int n){
: if(i==n){
: //print string;
: return;
: }
: for(int j=i;j: swap(a[i],a[j]);
: permute(a,i+1,n);
| h***n
发帖数: 276 | 17 对backtracking的改造不难，贴段代码把
void set_all_permutations_with_duplicates_helper(int a[], int n, int l, int
s[])
{
int i, first;
int flag[n];
if (l == n) {
for (i = 0; i < l; i++)
printf("%d\t", a[s[i]]);
printf("\n");
return;
}
for (i = 0; i < n; i++)
flag[i] = 0;
for (i = 0; i < l; i++)
flag[s[i]] = 1;
for (first = -1, i = 0; i < n; i++) {
if (flag[i] == 0) {
if (first < 0) {
first = i;
s[l] = i;
set_all_permutations_with_duplicates_helper(a, n, l + 1, s);
} else if (a[i] != a[first]) {
s[l] = i;
set_all_permutations_with_duplicates_helper(a, n, l + 1, s);
}
}
}
}
void set_all_permutations_with_duplicates(int a[], int n)
{
int s[n];
set_all_permutations_with_duplicates_helper(a, n, 0, s);
}
【在 i**9 的大作中提到】
: 看样子把 backtracking algorithm 改造成没有duplicate output有点困难，根据大家
: 的建议谢了一个简易版的 next_permutation (参考了 PuTTYshell 的 link
: http://code.google.com/p/sureinterview/source/browse/src/lib/co
: )
: void next_permutation(char a[],int n,bool & next,bool &first){
: int k=n-2;
: if(first){
: first = false;
: print(a,n);
: return;
| i**********e
发帖数: 1145 | 18 我写的代码供参考：
void permute(string out, string word, bool used[]) {
int n = word.length();
if (out.length() == n) {
cout << out << endl;
return;
}
for (int j = 0; j < n; j++) {
if (used[j]) continue;
used[j] = true;
permute(out+word[j], word, used);
used[j] = false;
// skip through duplicate characters
while (j+1 < n && word[j] == word[j+1])
j++;
}
}
void permute(string word) {
sort(word.begin(), word.end());
int n = word.length();
bool *used = new bool[n];
for (int i = 0; i < n; i++)
used[i] = false;
permute("", word, used);
delete[] used;
}
permute("aacc") returns:
aacc
acac
acca
caac
caca
ccaa
以上的代码是利用最基本的 generate all permutations 改造一下。你知道改了哪里吗？我个人觉得以上的解法比较简洁的，思路也比较清晰易懂。简洁的思路不容易出错，而且容易记。
有一个附加条件，就是所有字符必须是 sorted 来去除重复的 permutation set.
要去除重复的呢，就只要把以下的 while 语句（仅仅两行代码）加上就行。我说的“加上”意思是从原来不去除重复的 generate all permutations 的算法加上以下的代码就好了（记得有一个附加条件，就是字符必须排好序）。
// skip through duplicate characters
while (j+1 < n && word[j] == word[j+1])
j++;
好好的想一想，你知道为什么加了短短两行代码就能去除重复的 permutation set 吗？
当你搞明白这题了之后，做一做这提吧。同样的 backtracking 思路就能轻易解决。
Find all possible combination of numbers using a pre-defined candidate set.
Each number from the candidate set may be used only once in the combination.
For example,
Candidate Set = {10, 1, 2, 7, 6, 1, 5}
Target Number = 8
One possible output could be:
1+1+6
1+2+5
1+7
2+6
我博客有详细的思路供参考：
http://www.ihas1337code.com/2010/09/print-all-combinations-of-n
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | g*********s
发帖数: 1782 | 19 / skip through duplicate characters
while (j+1 < n && word[j] == word[j+1])
j++;
好好的想一想，你知道为什么加了短短两行代码就能去除重复的 permutation set 吗？
为啥呢？
【在 i**********e 的大作中提到】
: 我写的代码供参考：
: void permute(string out, string word, bool used[]) {
: int n = word.length();
: if (out.length() == n) {
: cout << out << endl;
: return;
: }
: for (int j = 0; j < n; j++) {
: if (used[j]) continue;
: used[j] = true;
| i**********e
发帖数: 1145 | 20 在字符都排好序的前提下，那么重复的字符都必定相连在一起。
给个例子：
aaabcc
进入递归，首先看到第一个的字符是 'a'。每一次标记位置用过，然后再进入下个
level 的递归。下一个 level 的时候，位置 0 的 'a' 已用过，所以我们跳到下一个
'a'，设位置 1 为用过，以此类推。
当递归回溯的时候，位置又被还原为没用过，照理应该跳到下一个位置的字符。但如果
下一个字符也是重复的字符，这样会产生重复的组合。例如，位置 0 的 'a'下一个字符
也是 'a'，这肯定是个重复的组合。
由于字符都排好序，只要跳到下一个不重复的字符就能跳过所有重复的组合。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | z*******0
发帖数: 30 | 21 void Recursion::permute(char a[], int n){
sort(a, a+n);
permute(a, 0, n);
}
void Recursion::permute(char a[],int i,int n){
if(i==n){
//print string;
cout << a << endl;
return;
}
for(int j=i;j
if (j > i && a[j]== a[j-1]) continue;
swap(a[i],a[j]);
permute(a,i+1,n);
swap(a[j],a[i]);
}
} | i**9
发帖数: 351 | 22 it is not working... ,
有个反例，input : ahhtt
只输出3个output:
ahhtt
hahtt
hhatt
apparently, should be much more than these
【在 z*******0 的大作中提到】
: void Recursion::permute(char a[], int n){
: sort(a, a+n);
: permute(a, 0, n);
: }
: void Recursion::permute(char a[],int i,int n){
: if(i==n){
: //print string;
: cout << a << endl;
: return;
: }
|
|
