计算一个数字有多少种排列可能
现有一数字，例如12345，问这个数字有多少种排列可能，最简单的就是位数的阶乘，5位数字等于5*4*3*2*1=120,这是理论上没有重复数字的情况下，如果现在是11234，11123，11112，11223有重复数字组成的数字怎么计算呢？
若一个数字由所有不相同的数字组成，则该数字的排列可能是该数组位数的阶乘，若该数字中存在重复的数字，例如，有m个1相同，结果就是n! / m!,n值是数字的位数，如果还存在p个相同的数字，那结果就是n! / m! /p!
根据上面的算法，上面的数字计算如下：
11234=5！ / 2！=60
11123=5! / 3!=20
11112=5! / 4! = 4
11223=5! / 2! / 2! = 30
附上C#实现
public class MathHelper
{
/// <summary>
/// 输入一个数字，算出该数值有多少种排列可能.
/// </summary>
/// <param name="num">The num.</param>
/// <returns></returns>
public static long CountPermutation(long num)
{
string number = num.ToString();
IDictionary<char, int> rptNum = new Dictionary<char, int>();
foreach (char ch in number)
{
if (rptNum.Keys.Where(it => it == ch).Count() > 0)
rptNum[ch] += 1;
else
rptNum.Add(ch, 1);
}
long totalFac = Factorial(number.Length);
foreach (var item in rptNum.Where(it => it.Value > 1))
{
totalFac /= Factorial(item.Value);
}
return totalFac;
}
/// <summary>
/// 计算阶乘.
/// </summary>
/// <param name="num">The num.</param>
/// <returns></returns>
public static long Factorial(int num)
{
if (num == 1) return num;
return num * Factorial(--num);
}
}
输出数字的全排列
上面计算出了一个数字有多少种排列可能，下面就要分别列出这些排列结果！网上已经有了很多的算法，最基础的还是迭代循环，但数字一大效率是一个问题，另外一点就是无法去除重复数字，例如计算1123，1122这样数字的全排列结果的时候，本人数学不太好，索性，在博客园找到一个同学的实现：
一组数字的全排列按序输出
再议“生成全排列算法”
C#实现
/// <summary>
/// 全排列算法类
/// </summary>
public class FullArrangementHelper
{
private int _length;
public IList<long> Result { get; private set; }
public FullArrangementHelper()
{
Result = new List<long>();
}
public IList<long> GetFullArrangement(long num)
{
string numStr = num.ToString();
int[] nums = new int[numStr.Length];
for (int i = 0; i < numStr.Length; i++)
nums[i] = int.Parse(numStr[i].ToString());
_length = nums.Length;
nums = nums.OrderBy(it => it).ToArray<int>();//排序
FullArrangement(nums, 0);
return Result;
}
/// <summary>
/// 计算全排列算法
/// </summary>
/// <param name="nums">要计算全排列的数字.</param>
/// <param name="pos">开始计算排列的位置，例如，现在的数字是1234，如果pos为0，就代表计算这四位的全排列，1的下标为0，
/// 如果为1，则计算后3位的全排列，依次下推.</param>
private void FullArrangement(int[] nums, int pos)
{
//将现在的数字添加到结果中
Result.Add(ConvertToNum(nums));
//最大是数字的长度-2是因为按照下标计算，此处pos-1是因为后续的步骤中需要+1来对相邻的两个数字做比较
for (int i = _length - 2; i > pos - 1; i--)
NextArrangement(nums, i);
}
/// <summary>
/// 计算下一轮全排列
/// </summary>
/// <param name="nums">数字的分解数组.</param>
/// <param name="pos">开始计算排列的位置.</param>
private void NextArrangement(int[] nums, int pos)
{
int[] cop = new int[_length];
//根据下标依次计算数字的全排列，实际就是大排列都由小排列一步步扩大
for (int i = pos + 1; i < _length; i++)
if (nums[i] > nums[pos] && nums[i] != nums[i - 1])
{
for (int t = 0; t < _length; t++)
cop[t] = nums[t];
//交换数字位
for (int j = i; j > pos; j--)
{
int temp = cop[j];
cop[j] = cop[j - 1];
cop[j - 1] = temp;
}
FullArrangement(cop, pos + 1);
}
}
private long ConvertToNum(int[] nums)
{
StringBuilder sb = new StringBuilder();
foreach (var n in nums)
sb.Append(n);
return long.Parse(sb.ToString());
}
}