iOS中排列组合算法的使用小结

时间:2021-08-28 05:48:30

前言

最近在项目中用到了排列组合计算,虽然比较简单,但是整个学习过程还是要记录下来的,以便以后可以吸取经验。

一般来说,排列组合就等于搜索。

注意点:

1.去重复:规定子集顺序必须升序;

2.候选数组的结果处理。必须深拷贝,否则最后的结果集里全是空的(加了一堆指针)。

3.在写递归的时候(DFS:深度优先搜索),思路是先把以 1 开头的都找出来,再把 2 开头的都找出来 …… 所有在递归之前做过的事情,之后都要把它抹回来。递归做的事情能一句话描述清楚。递归就是不断地把规模变小,但是都做的一件事情。

方法如下:

最开始的思路是用阶乘去解决排列组合的问题,所以就想到了递归。

?
1
2
3
4
5
6
7
8
9
10
long arithmetic(int n)
{
 if (n>1) {
 return n*arithmetic(n-1);
 }else if (n == 1){
 return 1;
 }else{
 return 1;
 }
}

但是递归的话,有一个弊端,数字达到一定程度的时候,它会出现值越界的情况,就算是用long long类型,也还是会出现越界的情况。所以用阶乘的这种方式,被暂时搁置。

想到的第二种思路是用for循环去解决问题。仅仅只用到排列这种算法,阶乘还是非用不可得,但是就组合而言,完全可以换另一种方式去解决。

解决的思路就是为了不让数字值越界,可以让分子和分母约分后,再乘下一个分子,再和分母约分。以此类推。话不多说,直接上代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 双色球 普通选注
 */
- (long)lotterySSQPTRecursiveWithRedBalls:(NSUInteger)redBalls blueBalls:(NSUInteger)blueBalls{
 if (redBalls > 5 && blueBalls > 0) {
 if (redBalls == 6) {
  return blueBalls;
 }else{
  NSUInteger count = (redBalls-6 > 6) ? 6 : redBalls-6;
  long number = 1;
  long molecular = 1;
  long denominator = 1;
  for (int i = 0; i < count; i++) {
  molecular = molecular*(redBalls-i);
  denominator = denominator * (i+1);
  number = (molecular*number)/denominator;
  molecular = 1;
  denominator = 1;
  }
  number = number*blueBalls;
  
  return number;
 }
 }else{
 return 0;
 }
}

相比于直接用阶乘,个人觉得还是for循环更好一些。如果有什么更好的解决思路,欢迎各位留言!

想要看Demo的小伙伴,点击此处传送

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对服务器之家的支持。

原文链接:https://www.jianshu.com/p/c190a41207f6