有重复的字符串全排列问题
如题，比如一个字符串“1232”,因为有两个重复的2,因此全排列有12种，而不是P(4,4)=24种，征求算法。
要求：最好不要使用辅助数组
[解决办法]
字典序法也适合多重集合。
C++源码：
#include <cstdlib>#include <iostream>#include <iterator>#include <algorithm>using namespace std;template<typename BidirectionalIterator>bool Next_permutation( BidirectionalIterator first, BidirectionalIterator last ){ if ( first == last) return false; BidirectionalIterator i = first; ++i; if (i == last) return false; i = last; --i; while( 1 ){ BidirectionalIterator ii = i; --i; if (*i < *ii){ BidirectionalIterator j = last; while (!(*i < *--j)); std::iter_swap(i, j); std::reverse(ii, last); return true; } if (i == first){ std::reverse(first, last); return false; } }} int main(int argc, char *argv[]){ char s[]="1232"; sort( s, s+sizeof(s)/sizeof(s[0])-1 ); do{ copy( s, s+sizeof(s)/sizeof(s[0])-1, ostream_iterator<char>(cout," ") ); cout<<endl; }while( Next_permutation( s, s+sizeof(s)/sizeof(s[0])-1 ) ); system("PAUSE"); return EXIT_SUCCESS;}
[解决办法]
这个是没考虑重复的全排列.
using System; using System.Collections.Generic; namespace Permulation { class Program { static void Main(string[] args) { List <AnyType > L = new List <AnyType >(); L.Add(new AnyType(1)); L.Add(new AnyType(2)); L.Add(new AnyType(3)); L.Add(new AnyType(4)); L.Add(new AnyType(5)); L.Add(new AnyType(6)); List <List <AnyType > > P = new List <List <AnyType > >(); P = Permulation(L); showPerm(P); Console.WriteLine(P.Count); Console.Read(); } /// <summary > /// 排列函数。 ///设R={r1,r2,...,rn}是要进行排列的n个元素,Ri=R-{ri}.集X中元素的全排列记为Perm(X), ///(ri)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列.R的全排列可归纳定义如下: ///当n=1时,Perm(R)={r},r是集合R中唯一的元素. ///当n >1时,Perm(R)由(r1)Perm(R1),(r2)Perm(R2),....(rn)Perm(Rn)构成 /// </summary > /// <param name="L" >输入的数字列表 </param > /// <returns >返回超集 </returns > static List <List <AnyType > > Permulation(List <AnyType > L) { List <List <AnyType > > P = new List <List <AnyType > >(); for (int i = 0; i < L.Count; i++) { P = SecondStep(L[i], P); } return P; } /// <summary > /// 第一步：求(ri)Perm(X) /// (ri)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列 /// </summary > /// <param name="ri" >输入数字 </param > /// <param name="PermX" >输入集合 </param > /// <returns >返回数字和集合合并后的超集 </returns > static List <List <AnyType > > FirstStep(AnyType ri, List <AnyType > PermX) { List <List <AnyType > > resultFirstStep = new List <List <AnyType > >(); for (int m = 0; m < PermX.Count + 1; m++) { List <AnyType > tempPerm1 = new List <AnyType >(PermX); if (m < PermX.Count) { tempPerm1.Insert(m, ri); } else { tempPerm1.Add(ri); } resultFirstStep.Add(tempPerm1); } return (resultFirstStep); } /// <summary > /// 第二步： /// 当n=1时,Perm(R)={r},r是集合R中唯一的元素. ///当n >1时,Perm(R)由(r1)Perm(R1),(r2)Perm(R2),....(rn)Perm(Rn)构成 /// </summary > /// <param name="r" >输入数字 </param > /// <param name="PermR" >输入集合的集合 </param > /// <returns >返回数字和集合合并后的超集 </returns > static List <List <AnyType > > SecondStep(AnyType r, List <List <AnyType > > PermR) { List <List <AnyType > > result = new List <List <AnyType > >(); if (PermR.Count == 0) { result.Add(new List <AnyType >(new AnyType[] { r })); } else { for (int i = 0; i < PermR.Count; i++) { result.AddRange(FirstStep(r, PermR[i])); } } return (result); } /// <summary > /// 显示结果的。 /// </summary > /// <param name="P" > </param > static void showPerm(List <List <AnyType > > P) { for (int i = 0; i < P.Count; i++) { for (int j = 0; j < P[i].Count; j++) { Console.Write(P[i][j].Value + " "); } Console.WriteLine(); } } } /// <summary > /// 用来试验的类 /// </summary > public class AnyType { public AnyType(int x) { v = x; } private int v; public int Value { get { return v; } set { v = value; } } } }
[解决办法]
就是字典序法嘛。
字典序法的一般框架：
1）：找最后的可以增加的元素a[i]
2）：将a[i]之后的排列最小化
也就是说，只要知道：
1：如何判断某排列是否是满足要求的最大排列（字典序下）
2：如何求满足要求的最小排列（字典序下）
就可以用字典序来解决。
字典序法比递归之类的方法要好许多，但比格雷码序之类的方法就差了不少了。
另外，C++ 中的STL已经用字典序法实现了排列算法:next_permutation( first, last )。也是适合于多重集合排列的。（因为它们判最大排列与求最小排列的方法一样）