实现一个全排列函数。

[问答题]

求一个全排列函数：
如p([1,2,3])输出：
[123]、[132]、[213]、[231]、[321]、[312]

查看答案及解析

推荐

fordchen

方法1：依次从字符串中取出一个字符作为最终排列的第一个字符，对剩余字符组成的字符串生成全排列，最终结果为取出的字符和剩余子串全排列的组合。

#include#includeusing namespace std;  
   
void permute1(string prefix, string str)  
{  
    if(str.length() == 0)  
        cout << prefix << endl; 
    else { 
    	for(int i = 0; i < str.length(); i++) 
    		permute1(prefix+str[i], str.substr(0,i)+str.substr(i+1,str.length())); 
    }
} 

void permute1(string s) 
{ 
	permute1("",s); 
} 

int main(void) {
	 //method1, unable to remove duplicate permutations. 
	 permute1("abc"); 
	 return 0;
}

优点：该方法易于理解，但无法移除重复的排列，如：s="ABA"，会生成两个“AAB”。

方法2：利用交换的思想，具体见实例，但该方法不如方法1容易理解。

	

	我们以三个字符abc为例来分析一下求字符串排列的过程。首先我们固定第一个字符a，求后面两个字符bc的排列。当两个字符bc的排列求好之后，我们把第一个字符a和后面的b交换，得到bac，接着我们固定第一个字符b，求后面两个字符ac的排列。现在是把c放到第一位置的时候了。记住前面我们已经把原先的第一个字符a和后面的b做了交换，为了保证这次c仍然是和原先处在第一位置的a交换，我们在拿c和第一个字符交换之前，先要把b和a交换回来。在交换b和a之后，再拿c和处在第一位置的a进行交换，得到cba。我们再次固定第一个字符c，求后面两个字符b、a的排列。 



	既然我们已经知道怎么求三个字符的排列，那么固定第一个字符之后求后面两个字符的排列，就是典型的递归思路了。 



	基于前面的分析，我们可以得到如下的参考代码： 



void Permutation(char* pStr, char* pBegin)  
{  
    assert(pStr && pBegin);  
    //if(!pStr || !pBegin)  
        //return ;  
    if(*pBegin == '\0')  
        printf("%s\n",pStr);  
    else  
    {  
	        char temp;  
	        for(char* pCh = pBegin; *pCh != '\0'; pCh++)  
	        {  
	            if(pCh != pBegin && *pCh == *pBegin)   //为避免生成重复排列，当不同位置的字符相同时不再交换  
	                continue;  
	            temp = *pCh;  
	            *pCh = *pBegin;  
	            *pBegin = temp;  
	  
	            Permutation(pStr, pBegin+1);  
	  
	            temp = *pCh;  
	            *pCh = *pBegin;  
	            *pBegin = temp;  
	        }  
	}  
}  
	  
int main(void)  
{  
	char str[] = "aba";  
	Permutation(str,str);  
	return 0;  
}  

如p([1,2,3])输出：

	 [1]、[2]、[3]、[1,2]、[2,3]、[1,3]、[1,2,3]

这两问可以用伪代码。

编辑于 2015-02-09 00:31:28 回复(0)

此番风景

def permutations(n):
    indices = list(range(n))
    yield indices
    while True:
        low_idx = n - 1
        while low_idx > 0 and indices[low_idx-1] > indices[low_idx]:
            low_idx -= 1
        if low_idx == 0:
            break
        # 排列中最后一个升序的首位
        low_idx -= 1
        high_idx = low_idx + 1
        # 找到最后一个比low_idx 对应大的最后一个数
        while high_idx < n and indices[high_idx] > indices[low_idx]:
            high_idx += 1
        high_idx -= 1
        indices[low_idx], indices[high_idx] = indices[high_idx], indices[low_idx]
        indices[low_idx+1:] = reversed(indices[low_idx+1:])
        yield indices

字典序排列，对字符串的全排列，可以简单理解为对字符串下标，求全排。http://www.nowcoder.com/profile/8481402/codeBookDetail?submissionId=5087693

编辑于 2016-08-18 16:13:10 回复(0)

Koen

//思路：拿数组的第一个字符和后面所有字符交换，递归地把后面的字符当作一个新的数组，再次把第一个字符和后面所有字符交换，直到新数组里只有一个元素，打印出字符串。

#include <iostream>
using namespace std;
#define N 5
void Print(int* arr, int length);
void swap(int &a, int &b);

void perm(int* arr, int* ptr, int length)
{
	if (length == 1)
	{
		Print(arr, N);
		return;
	}
		

	for (int i = 0; i < length; ++i)
	{
		swap(ptr[0], ptr[i]);
		perm(arr, ptr+1, length-1);
		swap(ptr[0], ptr[i]);
	}
}

void Print(int* arr, int length)
{
	for (int i = 0; i < length; ++i)
	{
		printf("%d ", arr[i]);
	}
	cout << endl;
}

void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

编辑于 2015-08-18 18:29:14 回复(0)

提交观点

问题信息

字符串百度

上传者：T-corb

难度：

3条回答 10收藏 3884浏览

实现一个全排列函数。

问题信息

热门推荐

相关试题