一道算法问题描述:
给定一组数字, 排列后得到的集合, 去掉重复的数, 求其和.(15)
例如: 313, 133 + 313+331 = 777
笔者有两种思路:
- 最直接的想法就是排列出所有的情况, 然后去掉重复的, 求和
- 直接求和, 先求出不考虑出现重复的和, 然后再去掉重复的数的和, 得到不重复的数的和
第一种想法是思路简单, 但是需要先排列, 可不可以不排列就得出结果?
第二种方式就不需要排列, 分析有重复的情况对于结果的影响
在有数重复的时候,
例如, 221, 2重复了一次, 就是2出现了两次, 本来6(3!)个排列结果, 但是由于2有两个, 去掉重复后变成了3个, 结果是导致其排列重复了2倍
例如, 3331, 3重复两次, 就是3出现了三次, 本来24(4!)个排列结果, 但是由于3有三个, 去掉重复后变成了4个, 结果是导致排列重复了6倍.
可以验证上面两种情况, 所有排列的和是不重复的和的倍数, 这个倍数和重复次数有关, 就是某个数出现不只一次, 就会导致重复, 设出现的次数为m, 倍数就为m!
求出所有排列的和除以m!, 就可以得到不重复的和.
例如, 上面的221, 就需要除以2!, 3331就需要除以3!, 1122这种两个重复的数, 就要除以2!再除以2!.
下面是代码实现
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;
public class PermutationNumber {
/**
* 递归的方式实现对给定数的排列, 会去掉所有重复的
* @param n 给定的数字
* @return 没有重复的给定数的排列
*/
public static Set<Integer> permutationNumber(int n) {
String strN = String.valueOf(n);
Set<Integer> result = new LinkedHashSet<Integer>(); // 集合可以去掉重复
if (strN.length() == 1) { // 长度为1的时候, 排列情况只有一种
result.add(n);
} else if (strN.length() == 2) { // 长度为2的时候, 排列情况只有两种
result.add(n);
StringBuffer buffer = new StringBuffer();
buffer.append(strN.charAt(1));
buffer.append(strN.charAt(0));
result.add(Integer.parseInt(buffer.toString()));
} else {
StringBuffer number = new StringBuffer(strN);
for (int i = 0; i < strN.length(); ++i) {
String temp = number.substring(i, i + 1); // 取第i个数为一个数, 其他的数递归着取
Set<Integer> set = permutationNumber(Integer.parseInt(number.substring(0, i) + number.substring(i + 1))); // 取剩余数的排列结果
for (Iterator<Integer> iterator = set.iterator(); iterator.hasNext();) {
result.add(Integer.parseInt(temp + iterator.next().toString()));
}
}
}
return result;
}
/**
* 求出某个数排列所有数的和, 排列中重复的数去掉
* @param n 给定的数
* @return 给定数的所有排列(不包含重复)的和
*/
public static int permutationSum(int n) {
String strN = String.valueOf(n);
Map<Character, Integer> numbers = new HashMap<Character, Integer>();
int sum = 0; // 结果
// 记录每个数字出现的次数
for (int i = 0; i < strN.length(); ++i) {
if (numbers.containsKey(strN.charAt(i))) {
numbers.put(strN.charAt(i), numbers.get(strN.charAt(i)) + 1);
} else {
numbers.put(strN.charAt(i), 1);
}
// 计算全部排列组合得到数的和
int number = strN.charAt(i) - '0';
for (int len = strN.length(); len > 0; --len) {
int magnification = 1;
for (int j = 1; j < len; ++j) {
magnification *= 10;
}
sum += number * magnification;
}
}
sum *= factorial(strN.length() - 1); // 所有数之和, 每个数在一个位置, 剩下的数排列组合就是阶乘
// 出现了两次及以上的数
for (Iterator<Map.Entry<Character, Integer>> iterator = numbers.entrySet().iterator(); iterator.hasNext();) {
Map.Entry<Character, Integer> entry = iterator.next();
sum /= factorial(entry.getValue());
}
return sum;
}
/**
* 递归的阶乘
* @param n 阶乘的参数
* @return 阶乘的结果
*/
public static int factorial(int n) {
if (n == 0) {
return 1;
} else {
return factorial(n - 1) * n;
}
}
/**
* 测试函数
* @param args
*/
public static void main(String[] args) {
// 修改n, 查看结果并验证第二种方法的正确性
int n = 14444;
Set<Integer> result = permutationNumber(n);
int sum = 0;
for(Iterator<Integer> iterator = result.iterator(); iterator.hasNext();) {
int temp = iterator.next();
System.out.println(temp);
sum += temp;
}
// 比较两个的结果, 证明起正确性
System.out.println("Sum: " + sum);
System.out.println("Sum2: " + permutationSum(n));
}
}
