带重复数字的全排列

上次gx同学问我一道又重复数字的全排列的问题，我当时用set保存，然后直接回溯。这这种做法，效率比较低，没有去剪枝，从而像1,1,1,1,1这样的序列都需要回溯很多次。今天写了一个剪枝的。

public class Permutation
{
    private int[] a;
    
    public Permutation(int[] a)
    {
        this.a = a;
    }
    public  boolean isOk(int b,int e){//判断是否重复
        if(b < e){
            for(int i = b; i < e; i++){
                if(a[i] == a[e])
                    return false;
            }
        }
        return true;
    }
    
    public void permutation(int k){
        if(k >= a.length){
            print();
        }else{
            for(int i = k; i < a.length; i++){
                if(isOk(k,i)){
                    swap(i,k);
                    permutation( k+1 );
                    swap(i,k);
                }
            }
        }
        
    }
    
    private void swap( int i, int k )
    {
        int temp = a[i];
        a[i] = a[k];
        a[k] = temp;
    }
    
    private void print()
    {
        for( int i = 0; i < a.length; i++ )
        {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
    
    public static void main( String[] args )
    {
        Permutation p = new Permutation(new int[]{1,2,2,2});
        p.permutation( 0 );
    }
}

c++ STL algorithm中有next_permutation可以直接调用，ACM的时候经常偷懒用这个，呵呵。
学以致用：poj 1731
http://acm.pku.edu.cn/JudgeOnline/problem?id=1731

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;

string goods;
vector<string> v;

void swap(string &str,int i, int j){
	char temp = str[i];
	str[i] = str[j];
	str[j] = temp;
}

bool ok(int i, int j){
	if( i < j){
		for(int k = i; k < j; k++){
			if(goods[k] == goods[j])
				return false;
		}
	}
	return true;
}
void backtrack(int i){
	if(i >= goods.length()){
		 v.push_back(goods);
	}
	
	for(int j = i; j < goods.length(); j++){
		if(ok(i,j)){
			swap(goods,i,j);
			backtrack(i + 1);
			swap(goods,i,j);
		}
	}
}

int main(){
	cin >> goods;
	backtrack(0);
	sort(v.begin(),v.end());
	for(int i = 0; i < v.size(); i++){
		cout << v[i] << endl;
	}
}

poj1256 http://acm.pku.edu.cn/JudgeOnline/problem?id=1256
这道题需要一种特殊的数序输出：
An upper case letter goes before the corresponding lower case letter.
So the right order of letters is 'A'<'a'<'B'<'b'<...<'Z'<'z'.
我们只需要定义一个正确的比较函数就可以了

bool cmp(const string &str1,const string &str2){  
    int i;  
    int m_len = min(str1.length(), str2.length());  
    for(i = 0; i < m_len; i++){  
        if(str1[i] != str2[i])  
            break;  
    }  
  
    if(i == m_len){  
        return str1.length() < str2.length();  
    }else if(tolower(str1[i]) == tolower(str2[i])) {  
        return str1[i] < str2[i];  
    }else{  
        return tolower(str1[i]) < tolower(str2[i]);  
    }  
}  

或者

bool cmp(char c1,char c2){
	if(tolower(c1) == tolower(c2)) 
		return c1 < c2;
	else
		return tolower(c1) < tolower(c2);
}

这样我们的代码就出来了：

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;

string str;
vector<string> permutations;

bool cmp(const string &str1,const string &str2){
	int i;
	int m_len = min(str1.length(), str2.length());
	for(i = 0; i < m_len; i++){
		if(str1[i] != str2[i])
			break;
	}

	if(i == m_len){
		return str1.length() < str2.length();
	}else if(tolower(str1[i]) == tolower(str2[i])) {
		return str1[i] < str2[i];
	}else{
		return tolower(str1[i]) < tolower(str2[i]);
	}
}

void swap(int i,int j){
	char temp = str[i];
	str[i] = str[j];
	str[j] = temp;
}

bool isOk(int i,int j){
	if(i < j){
		int k;
		for(k = i; k < j; k++){
			if(str[k] == str[j])
				return false;
		}
	}
	return true;
}

void backtrack(int i){
	if( i >= str.length()){
		permutations.push_back(str);
		return;
	}

	int j;
	for(j = i; j < str.length(); j++){
		if(isOk(i,j)){
			swap(i,j);
			backtrack(i+1);
			swap(i,j);
		}
	}
}

int main(){
	int n;
	cin >> n;
	int i,j;
	for(i = 0; i < n; i++){
		cin >> str;
		permutations.clear();
		backtrack(0);
		sort(permutations.begin(),permutations.end(),cmp);
		for(j = 0; j < permutations.size(); j++){
			cout << permutations[j] << endl;
		}
	}
}

我们还是用STL来爽爽这道题吧：

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;

string str;

bool cmp(char c1,char c2){
	if(tolower(c1) == tolower(c2)) 
		return c1 < c2;
	else
		return tolower(c1) < tolower(c2);
}

int main(){
	int n;
	cin >> n;
	int i,j;
	for(i = 0; i < n; i++){
		cin >> str;
		sort(str.begin(),str.end(),cmp);
		cout << str << endl;
		while(next_permutation(str.begin(),str.end(),cmp)){
			cout << str << endl;
		}
	}
	return 0;
}