[分享]计算组合的代码

liyupeng

前几天因为业务需要，写了一段计算排列组合的代码，今天整理了一下，拿出来和大家分享，还请大家多多指教

1. 
   
2. <?php
   
3. /**
   
4. * 要解决的数学问题：
   
5. *       算出C(a,1) * C(b, 1) * ... * C(n, 1)的组合情况，
   
6. *       其中C(n, 1)代表从n个元素里任意取一个元素
   
7. *
   
8. * 要解决的实际问题样例：
   
9. *       某年级有m个班级，每个班的人数不同，
   
10. *        现在要从每个班里抽选一个人组成一个小组，
    
11. *        由该小组来代表该年级参加学校的某次活动。
    
12. *        请给出所有可能的组合
    
13. */
    
14. 
    
15. /* ###### 开始计算 ####### */
    
16. 
    
17. /**
    
18. * 需要进行排列组合的数组
    
19. *
    
20. * 数组说明：
    
21. *       该数组是一个二维数组，
    
22. *       第一维索引代表班级编号，第二维索引代表学生编号
    
23. */
    
24. $CombinList = array(1 =>; array("Student10", "Student11"),
    
25.                     2 =>; array("Student20", "Student21", "Student22"),
    
26.                     3 =>; array("Student30"),
    
27.                     4 =>; array("Student40", "Student41", "Student42", "Student43"));
    
28. 
    
29. /* 计算C(a,1) * C(b, 1) * ... * C(n, 1)的值 */
    
30. $CombineCount = 1;
    
31. foreach($CombinList as $Key =>; $Value)
    
32. {
    
33.     $CombineCount *= count($Value);
    
34. }
    
35. 
    
36. $RepeatTime = $CombineCount;
    
37. foreach($CombinList as $ClassNo =>; $StudentList)
    
38. {
    
39.     // $StudentList中的元素在拆分成组合后纵向出现的最大重复次数
    
40.     $RepeatTime = $RepeatTime / count($StudentList);
    
41. 
    
42.     $StartPosition = 1;
    
43. 
    
44.     // 开始对每个班级的学生进行循环
    
45.     foreach($StudentList as $Student)
    
46.     {
    
47.         $TempStartPosition = $StartPosition;
    
48. 
    
49.         $SpaceCount = $CombineCount / count($StudentList) / $RepeatTime;
    
50. 
    
51.         for($J = 1; $J <= $SpaceCount; $J ++)
    
52.         {
    
53.             for($I = 0; $I < $RepeatTime; $I ++)
    
54.             {
    
55.                $Result[$TempStartPosition + $I][$ClassNo] = $Student;
    
56.             }
    
57.             $TempStartPosition += $RepeatTime * count($StudentList);
    
58.         }
    
59.         $StartPosition += $RepeatTime;
    
60.     }
    
61. }
    
62. 
    
63. /* 打印结果 */
    
64. echo "<pre>;";
    
65. print_r($Result);
    
66. ?>;
    

复制代码