PHP实现笛卡尔积算法的实例讲解

时间:2022-11-18 11:07:30

概念

在数学中,两个集合X和Y的笛卡儿积(Cartesian product),又称直积,表示为 X × Y。设A、B是任意两个集合,在集合A中任意取一个元素x,在集合B中任意取一个元素y,组成一个有序对(x,y),把这样的有序对作为新的元素,他们的全体组成的集合称为集合A和集合B的直积,记为A×B,即 A×B={(x,y)|x∈A且y∈B}。

假设集合 A={a, b},集合 B={0, 1, 2},则两个集合的笛卡尔积为 {(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)}。

举例

给出三个域:

?
1
2
3
4
5
D1 = { 张清玫,刘逸 }
 
D2 = {计算机专业,信息专业}
 
D3 = {李勇,刘晨,王敏}

则 D1,D2,D3 的笛卡尔积 D = D1×D2×D3,等于:

?
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
{
 
  (张清玫, 计算机专业, 李勇),
 
  (张清玫, 计算机专业, 刘晨),
 
  (张清玫, 计算机专业, 王敏),
 
  (张清玫, 信息专业, 李勇),
 
  (张清玫, 信息专业, 刘晨),
 
  (张清玫, 信息专业, 王敏),
 
  (刘逸, 计算机专业, 李勇),
 
  (刘逸, 计算机专业, 刘晨),
 
  (刘逸, 计算机专业, 王敏),
 
  (刘逸, 信息专业, 李勇),
 
  (刘逸, 信息专业, 刘晨),
 
  (刘逸, 信息专业, 王敏)
 
}

这样就把D1、D2、D3这三个集合中的每个元素加以对应组合,形成庞大的集合群。本个例子中的D中就会有 2X2X3=12 个元素,如果一个集合有1000个元素,有这样3个集合,他们的笛卡尔积所组成的新集合会达到十亿个元素。假若某个集合是无限集,那么新的集合就将是有无限个元素。

PHP代码 - 输出数组形式

?
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
function Descartes()
 
{
 
  $t = func_get_args();                  // 获取传入的参数
 
  if (func_num_args() == 1) {                // 判断参数个数是否为1
 
    return call_user_func_array(__FUNCTION__, $t[0]); // 回调当前函数,并把第一个数组作为参数传入
 
  }
 
  $a = array_shift($t);    // 将 $t 中的第一个元素移动到 $a 中,$t 中索引值重新排序
 
  if ( !is_array($a)) {
 
    $a = [$a];
 
  }
 
  $a = array_chunk($a, 1);   // 分割数组 $a ,为每个单元1个元素的新数组
 
  do {
 
    $r = [];
 
    $b = array_shift($t);
 
    if ( !is_array($b)) {
 
      $b = [$b];
 
    }
 
    foreach ($a as $p) {
 
      foreach (array_chunk($b, 1) as $q) {
 
        $r[] = array_merge($p, $q);
 
      }
 
    }
 
    $a = $r;
 
  } while ($t);
 
  return $r;
 
}

使用:

?
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
28
29
30
31
$arr = [
 
  [
 
    '张清玫',
 
    '刘逸'
 
  ],
 
  [
 
    '计算机专业',
 
    '信息管理与信息系统专业',
 
    '电子商务专业'
 
  ],
 
  [
 
    '2018级',
 
    '2017级'
 
  ]
 
];
 
$r = Descartes($arr);

效果:

?
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
array(12) {
 
 [0]=>
 
 array(3) {
 
  [0]=>
 
  string(9) "张清玫"
 
  [1]=>
 
  string(15) "计算机专业"
 
  [2]=>
 
  string(7) "2018级"
 
 }
 
 [1]=>
 
 array(3) {
 
  [0]=>
 
  string(9) "张清玫"
 
  [1]=>
 
  string(15) "计算机专业"
 
  [2]=>
 
  string(7) "2017级"
 
 }
 
 [2]=>
 
 array(3) {
 
  [0]=>
 
  string(9) "张清玫"
 
  [1]=>
 
  string(33) "信息管理与信息系统专业"
 
  [2]=>
 
  string(7) "2018级"
 
 }
 
 [3]=>
 
 array(3) {
 
  [0]=>
 
  string(9) "张清玫"
 
  [1]=>
 
  string(33) "信息管理与信息系统专业"
 
  [2]=>
 
  string(7) "2017级"
 
 }
 
 [4]=>
 
 array(3) {
 
  [0]=>
 
  string(9) "张清玫"
 
  [1]=>
 
  string(18) "电子商务专业"
 
  [2]=>
 
  string(7) "2018级"
 
 }
 
 [5]=>
 
 array(3) {
 
  [0]=>
 
  string(9) "张清玫"
 
  [1]=>
 
  string(18) "电子商务专业"
 
  [2]=>
 
  string(7) "2017级"
 
 }
 
 [6]=>
 
 array(3) {
 
  [0]=>
 
  string(6) "刘逸"
 
  [1]=>
 
  string(15) "计算机专业"
 
  [2]=>
 
  string(7) "2018级"
 
 }
 
 [7]=>
 
 array(3) {
 
  [0]=>
 
  string(6) "刘逸"
 
  [1]=>
 
  string(15) "计算机专业"
 
  [2]=>
 
  string(7) "2017级"
 
 }
 
 [8]=>
 
 array(3) {
 
  [0]=>
 
  string(6) "刘逸"
 
  [1]=>
 
  string(33) "信息管理与信息系统专业"
 
  [2]=>
 
  string(7) "2018级"
 
 }
 
 [9]=>
 
 array(3) {
 
  [0]=>
 
  string(6) "刘逸"
 
  [1]=>
 
  string(33) "信息管理与信息系统专业"
 
  [2]=>
 
  string(7) "2017级"
 
 }
 
 [10]=>
 
 array(3) {
 
  [0]=>
 
  string(6) "刘逸"
 
  [1]=>
 
  string(18) "电子商务专业"
 
  [2]=>
 
  string(7) "2018级"
 
 }
 
 [11]=>
 
 array(3) {
 
  [0]=>
 
  string(6) "刘逸"
 
  [1]=>
 
  string(18) "电子商务专业"
 
  [2]=>
 
  string(7) "2017级"
 
 }
 
}

以上就是本次介绍的全部相关知识点,感谢大家的学习和对服务器之家的支持。

原文链接:https://www.php.cn/php-weizijiaocheng-439280.html