1 | /////////////////////////////////////////////////////////////////////////////// |
---|
2 | version="version sets.lib 4.1.1.0 Dec_2017 "; //$id$ |
---|
3 | category="Miscellaneous"; |
---|
4 | info=" |
---|
5 | LIBRARY: sets.lib Sets in Singular |
---|
6 | |
---|
7 | AUTHORS: J. Boehm, boehm @ mathematik.uni-kl.de |
---|
8 | D. Wienholz, wienholz @ mathematik.uni-kl.de |
---|
9 | S. Zillien, zillien @ rhrk.uni-kl.de |
---|
10 | |
---|
11 | OVERVIEW: |
---|
12 | |
---|
13 | We implement the new class set and all basic methods needed to work with sets. |
---|
14 | A set is generated from a list. After the generating of a set, the adding of an |
---|
15 | element or the union of two sets, automatically every double element is removed |
---|
16 | to secure that no element occurs in a set more than once. |
---|
17 | |
---|
18 | There is a comparison operator, we access the operator via the function isEqual. |
---|
19 | This function isEqual can be used to compare two elements of the same type |
---|
20 | (Set, list, int, bigint, string, intmat, bigintmat, intvec, ring, map, poly, matrix, |
---|
21 | ideal, module, vector, resolution) and also works for comparing of int, bigint and |
---|
22 | number with each other, similarily for matrix, bigintmat and intmat. |
---|
23 | |
---|
24 | The function size can be used to determine the number of elements. |
---|
25 | |
---|
26 | The + operator is used for the union, the * operator for the intersection. |
---|
27 | |
---|
28 | The operators < and > can be used for inclusion tests. |
---|
29 | |
---|
30 | The print function can be used for printing sets. |
---|
31 | |
---|
32 | Note that the implementation of the underlying data structure and algorithms is |
---|
33 | very trivial and will at some point be replaced with something more efficient. |
---|
34 | |
---|
35 | KEYWORDS: |
---|
36 | set, intersection, union, complement, equality, isEqual |
---|
37 | |
---|
38 | TYPES: |
---|
39 | Set The class of all sets |
---|
40 | |
---|
41 | PROCEDURES: |
---|
42 | set(list) general procedure to generate a set from a list |
---|
43 | union(Set,Set) union of sets |
---|
44 | intersection(Set,Set) intersection of sets |
---|
45 | complement(Set,Set) complement of sets |
---|
46 | isElement(def,Set) test whether an object is in a set |
---|
47 | isSubset(Set,Set) test whether a set is a subset of another set |
---|
48 | isSuperset(Set,Set) test whether a set is a superset of another set |
---|
49 | addElement(Set,def) adds an element to the set |
---|
50 | "; |
---|
51 | |
---|
52 | |
---|
53 | static proc mod_init() |
---|
54 | { |
---|
55 | LIB "methods.lib"; // mod_init needs Hashtable/Method from methods.lib |
---|
56 | newstruct("Set","list elements"); |
---|
57 | system("install","Set","print",printSet,1); |
---|
58 | system("install","Set","+",union,2); |
---|
59 | system("install","Set","*",intersection,2); |
---|
60 | system("install","Set","<",isSubset,2); |
---|
61 | system("install","Set","size",sizeSet,1); |
---|
62 | system("install","Set",">",isSuperset,2); |
---|
63 | system("install","Set","==",isEqualSet,2); |
---|
64 | HashTable F = hashTable( |
---|
65 | list( |
---|
66 | list("Set","Set"), list("int","number"), list("number","bigint"), |
---|
67 | list("poly","poly"), list("matrix","matrix"), list("ideal","ideal"), |
---|
68 | list("map","map"), list("ring","ring"), list("list","list"), |
---|
69 | list("bigint","int"), list("int","bigint"), list("bigint","bigint"), |
---|
70 | list("string","string"), list("vector","vector"), list("intvec","intvec"), |
---|
71 | list("intmat","intmat"), list("bigintmat","bigintmat"), list("matrix","intmat"), |
---|
72 | list("intmat","matrix"), list("intmat","bigintmat"), list("bigintmat","intmat"), |
---|
73 | list("int","int"), list("number","int"), list("bigint","number"), |
---|
74 | list("module","module"), list("number","number"), list("resolution","resolution"), |
---|
75 | list("vector","intvec"), list("intvec","vector") |
---|
76 | ), |
---|
77 | list( |
---|
78 | "isEqualSet", "isEqualInt", "isEqualInt", |
---|
79 | "isEqualInt", "isEqualInt", "isEqualIdeal", |
---|
80 | "isEqualMap", "isEqualRing", "isEqualList", |
---|
81 | "isEqualInt", "isEqualInt", "isEqualInt", |
---|
82 | "isEqualInt", "isEqualInt", "isEqualInt", |
---|
83 | "isEqualInt", "isEqualInt", "isEqualInt", |
---|
84 | "isEqualInt", "isEqualInt", "isEqualInt", |
---|
85 | "isEqualInt", "isEqualInt", "isEqualInt", |
---|
86 | "isEqualModule", "isEqualInt", "isEqualResolution", |
---|
87 | "isEqualInt","isEqualInt" |
---|
88 | ) |
---|
89 | ); |
---|
90 | Method isEqual_ = method(F); |
---|
91 | export(isEqual_); |
---|
92 | installMethod(isEqual_,"isEqual"); |
---|
93 | system("install","Set","=",set,1); |
---|
94 | } |
---|
95 | |
---|
96 | proc sizeSet(Set a) |
---|
97 | { |
---|
98 | list L =a.elements; |
---|
99 | return(size(L)); |
---|
100 | } |
---|
101 | |
---|
102 | |
---|
103 | proc isEqualInt(def a,def b) //exists for matrix, int, bigint, poly, string, vector, intvec, number, intmat, bigintmat, cone |
---|
104 | { |
---|
105 | return(a==b); |
---|
106 | } |
---|
107 | |
---|
108 | |
---|
109 | proc isEqualMap(def a, def b) |
---|
110 | { |
---|
111 | if(!(isEqualRing(preimage(a),preimage(b)))) //check the startring of the maps |
---|
112 | { |
---|
113 | return(0); |
---|
114 | } |
---|
115 | for(int i=1;i<=size(ringlist(preimage(a))[2]);i++){ //check if the two maps are the same |
---|
116 | if(a[i]!=b[i]){ //in every component |
---|
117 | return(0); |
---|
118 | } |
---|
119 | } |
---|
120 | return(1);} |
---|
121 | |
---|
122 | |
---|
123 | proc isEqualModule(def m0, def s0) |
---|
124 | { |
---|
125 | intvec o=option(get); |
---|
126 | option(redSB); |
---|
127 | module m=std(m0); |
---|
128 | module s=std(s0); |
---|
129 | option(set,o); |
---|
130 | if(size(m)!=size(s)){return(0);} |
---|
131 | for(int i=1;i<=size(m);i++){ |
---|
132 | if(m[i]!=s[i]){return(0);} |
---|
133 | } |
---|
134 | return(1); |
---|
135 | } |
---|
136 | |
---|
137 | |
---|
138 | proc isEqualResolution(def r, def s) |
---|
139 | { |
---|
140 | list l=r; |
---|
141 | list j=s; |
---|
142 | return(isEqual(l,j)); |
---|
143 | } |
---|
144 | |
---|
145 | proc isEqualRing(def r, def t) |
---|
146 | { |
---|
147 | list a=ringlist(r); //creating two lists with everything that defines the rings |
---|
148 | list b=ringlist(t); |
---|
149 | return(isEqual(a,b)); |
---|
150 | } |
---|
151 | |
---|
152 | proc isEqualList(def a, def b) |
---|
153 | { |
---|
154 | if(size(a)!=size(b)){ //check if the two lists have the same size |
---|
155 | return(0); |
---|
156 | } |
---|
157 | for(int i=1;i<=size(a);i++){ //checking every element of the two lists |
---|
158 | if(!(isEqual(a[i],b[i]))){ |
---|
159 | return(0); |
---|
160 | } |
---|
161 | } |
---|
162 | return(1); |
---|
163 | } |
---|
164 | |
---|
165 | proc isEqualSet(def a, def b) |
---|
166 | { |
---|
167 | if(size(a)!=size(b)){ //check if the two sets have the same size |
---|
168 | return(0); |
---|
169 | } |
---|
170 | list L = a.elements; |
---|
171 | for(int i=1;i<=size(a);i++){ //chek if every element of the first set occurs in |
---|
172 | if(!(isElement(L[i],b))){ //the second set |
---|
173 | return(0); |
---|
174 | } |
---|
175 | } |
---|
176 | return(1); |
---|
177 | } |
---|
178 | |
---|
179 | proc isEqualIdeal(def a, def b) |
---|
180 | { |
---|
181 | option(redSB); |
---|
182 | intvec o=option(get); |
---|
183 | ideal I = std(a); |
---|
184 | ideal J = std(b); |
---|
185 | option(set,o); |
---|
186 | if(size(I)!=size(J)){ |
---|
187 | return(0); |
---|
188 | } |
---|
189 | for(int i = 1;i<=size(I); i++){ |
---|
190 | if(I[i]!=J[i]){ |
---|
191 | return(0); |
---|
192 | } |
---|
193 | } |
---|
194 | return(1); |
---|
195 | } |
---|
196 | |
---|
197 | static proc removeDouble(list L) |
---|
198 | { |
---|
199 | int j; |
---|
200 | list L1; //creating a list tagging the first appearance with 1 and the following with 0 |
---|
201 | list Output; //creating an empty list for the return |
---|
202 | for(int i=1; i<=size(L); i++){ |
---|
203 | L1=insert(L1,1); //at the beginning every element is tagged with 1 |
---|
204 | } |
---|
205 | for(i=1; i<size(L); i++){ |
---|
206 | if(L1[i]){ //for every element tagged with 1 |
---|
207 | for(j=i+1; j<=size(L); j++){ //check if it appearace again |
---|
208 | if(isEqual(L[i],L[j])){ //and tag those appearances with 0 |
---|
209 | L1[j] = 0; |
---|
210 | } |
---|
211 | } |
---|
212 | } |
---|
213 | } |
---|
214 | for(i=1; i<=size(L); i++){ |
---|
215 | if(L1[i]){ //adding every element tagged with 1 to the list |
---|
216 | Output=insert(Output,L[i]); //for the return |
---|
217 | } |
---|
218 | } |
---|
219 | return(Output); |
---|
220 | } |
---|
221 | |
---|
222 | |
---|
223 | static proc complementOfLists(list L,list J) |
---|
224 | { |
---|
225 | int j; |
---|
226 | list L1; //create a list to tag the elements with 1 or 0 |
---|
227 | list Output; //create a list for the return |
---|
228 | for(int i=1; i<=size(J); i++){ |
---|
229 | L1=insert(L1,1); //every element of the second list is tagged with 1 |
---|
230 | } |
---|
231 | for(i=1; i<=size(L); i++){ //for every element of the first list |
---|
232 | for(j=1; j<=size(J); j++){ //test if it is equal to the elements of the |
---|
233 | if(isEqual(L[i],J[j])){ //second list |
---|
234 | L1[j] = 0; //and tag those with 0 |
---|
235 | break; |
---|
236 | } |
---|
237 | } |
---|
238 | } |
---|
239 | for(i=1; i<=size(J); i++){ //adding every element tagged with 1 to the set |
---|
240 | if(L1[i]){ //for the return |
---|
241 | Output=insert(Output,J[i]); |
---|
242 | } |
---|
243 | } |
---|
244 | return(Output); |
---|
245 | } |
---|
246 | |
---|
247 | proc addElement(Set M, def a) |
---|
248 | "USAGE: addElement(M,a) ; M Set, a freely chosen element |
---|
249 | RETURN: adds the Element a to the Set M |
---|
250 | EXAMPLE: example addElement, shows an example |
---|
251 | " |
---|
252 | { |
---|
253 | Set S=a; |
---|
254 | return(M+S); |
---|
255 | } |
---|
256 | example |
---|
257 | { "EXAMPLE:"; echo = 2; //example for addElement |
---|
258 | int a=4; |
---|
259 | list L = 1,2,3; |
---|
260 | Set S = L; |
---|
261 | S; |
---|
262 | a; |
---|
263 | addElement(S,a); |
---|
264 | } |
---|
265 | |
---|
266 | proc set(list L) |
---|
267 | "USAGE: set(l) or *=l (short form of * = set(l)); l list |
---|
268 | RETURN: Set, the set createt from the entered list |
---|
269 | EXAMPLE: example set, shows an example |
---|
270 | " |
---|
271 | { |
---|
272 | Set S; |
---|
273 | S.elements=removeDouble(L); //removing every element which occurs more then once |
---|
274 | return(S); |
---|
275 | } |
---|
276 | example |
---|
277 | { |
---|
278 | "EXAMPLE:"; echo = 2; //example for set |
---|
279 | Set S0a = list(list(1,2,3),list(list(1,2)),list(10,11)); |
---|
280 | Set S0b = list(list(10,11),list(list(1,2))); |
---|
281 | S0b<S0a; |
---|
282 | S0a<S0b; |
---|
283 | S0a==S0a; |
---|
284 | S0a==S0b; |
---|
285 | list L = 1,1,2,3; |
---|
286 | Set S1 = L; |
---|
287 | S1; |
---|
288 | ring R1; |
---|
289 | ring R2 = 0,(x,y),dp; |
---|
290 | Set S2 = list(R1,R1,R2); |
---|
291 | S2; |
---|
292 | ideal I1 = x+y; |
---|
293 | ideal I2 = y^2; |
---|
294 | ideal I3 = x+y, (x+y)^3; |
---|
295 | Set S3 = list(I1,I2,I3); |
---|
296 | S3; |
---|
297 | isEqual(I1,I3); |
---|
298 | isEqual(I1,I2); |
---|
299 | module M1 = x*gen(1), y*gen(1); |
---|
300 | module M2 = y^2*gen(2); |
---|
301 | module M3 = (x+y)*gen(1), (x-y)*gen(1); |
---|
302 | Set S4 = list(M1,M2,M3); |
---|
303 | S4; |
---|
304 | intmat m1[2][3]= 1,2,3,4,5,6; |
---|
305 | intmat m2[2][3]= 1,2,3,4,5,7; |
---|
306 | Set S5 = list(m1,m2,m1); |
---|
307 | S5; |
---|
308 | bigintmat b1[2][3]= 1,2,3,4,5,6; |
---|
309 | bigintmat b2[2][3]= 1,2,3,4,5,7; |
---|
310 | Set S6 = list(b1,b2,b1); |
---|
311 | S6; |
---|
312 | resolution r1 = res(maxideal(3),0); |
---|
313 | resolution r2 = res(maxideal(4),0); |
---|
314 | Set S7 = list(r1,r1,r2); |
---|
315 | size(S7); |
---|
316 | } |
---|
317 | |
---|
318 | proc printSet(Set M) |
---|
319 | { |
---|
320 | string st; |
---|
321 | list L = M.elements; |
---|
322 | if (size(L)==0) { |
---|
323 | print("Empty set"); //returning Empty Set if the set contains no elements |
---|
324 | } |
---|
325 | else |
---|
326 | { |
---|
327 | string s ="{"; //if the set isn't empty creating a string with |
---|
328 | for (int j=1; j<=size(L)-1; j++) //with every element of the set |
---|
329 | { |
---|
330 | s=s+string((L[j]))+"; "; |
---|
331 | } |
---|
332 | s=s+string((L[size(L)]))+"}"; |
---|
333 | print(s); //printing the string |
---|
334 | if (size(L)>1){st ="s";} |
---|
335 | print("Set with "+string(size(L))+" element"+st); //printing a string with the number |
---|
336 | } //of elements of the set |
---|
337 | } |
---|
338 | |
---|
339 | static proc setJoinOfLists(list L1,list L2) |
---|
340 | { |
---|
341 | for(int i=1; i<=size(L2); i++){ |
---|
342 | L1 = insert(L1,L2[i]); //adding every element of the second list to the first |
---|
343 | } |
---|
344 | return(L1); |
---|
345 | } |
---|
346 | |
---|
347 | |
---|
348 | proc union(Set N, Set M) |
---|
349 | "USAGE: union(N,M) or N+M; N,M sets |
---|
350 | RETURN: Set, the union of the sets N and M |
---|
351 | EXAMPLE: example union, shows an example |
---|
352 | " |
---|
353 | { |
---|
354 | Set S; |
---|
355 | list L1 = N.elements; //converting the sets into lists |
---|
356 | list L2 = M.elements; |
---|
357 | list L = setJoinOfLists(L1,L2); //creating the joint of the two lists |
---|
358 | S.elements = removeDouble(L); //removing every element which occurs more then once |
---|
359 | return(S); |
---|
360 | } |
---|
361 | example //example for union |
---|
362 | { "EXAMPLE:"; echo = 2; |
---|
363 | list l =1,2,3; |
---|
364 | list j =2,3,4; |
---|
365 | Set N=l; |
---|
366 | Set M=j; |
---|
367 | N; |
---|
368 | M; |
---|
369 | N+M; |
---|
370 | } |
---|
371 | |
---|
372 | |
---|
373 | static proc setIntersectionOfLists(list L1,list L2) |
---|
374 | { |
---|
375 | if(size(L1)>size(L2)){ //secure that the first list isn't bigger then the second |
---|
376 | list J = L1; |
---|
377 | L1=L2; |
---|
378 | L2=J; |
---|
379 | } |
---|
380 | list M; //creating an empty set, which will be returned |
---|
381 | if(size(L1)==0){ //if the first list is empty, the intersection is empty |
---|
382 | return(M); |
---|
383 | } |
---|
384 | Set S = set(L2); |
---|
385 | for(int i=1; i<=size(L1); i++){ //check for every element of the first list |
---|
386 | if(isElement(L1[i],S)){ //is in the second list |
---|
387 | M=insert(M,L1[i]); //an element of both lists, is added the set |
---|
388 | } |
---|
389 | } |
---|
390 | return(M); |
---|
391 | } |
---|
392 | |
---|
393 | proc intersection(Set N, Set M) |
---|
394 | "USAGE: intersection(N,M) or N*M; N,M sets |
---|
395 | RETURN: Set, the interseection of the sets N and M |
---|
396 | EXAMPLE: example intersection, shows an example |
---|
397 | " |
---|
398 | { |
---|
399 | Set S; |
---|
400 | list L1 = N.elements; |
---|
401 | list L2 = M.elements; |
---|
402 | list L = setIntersectionOfLists(L1,L2); |
---|
403 | S.elements = removeDouble(L); |
---|
404 | return(S); |
---|
405 | } |
---|
406 | example //example for intersection |
---|
407 | { "EXAMPLE:"; echo = 2; |
---|
408 | list l =1,2,3; |
---|
409 | list j =2,3,4; |
---|
410 | Set N=l; |
---|
411 | Set M=j; |
---|
412 | N; |
---|
413 | M; |
---|
414 | N*M; |
---|
415 | } |
---|
416 | |
---|
417 | proc isElement(def a, Set M) |
---|
418 | "USAGE: isElement(a,M); M set a def |
---|
419 | RETURN: bool, 1 if a is an element of M, 0 if not |
---|
420 | EXAMPLE: example isElement, shows an example |
---|
421 | " |
---|
422 | { |
---|
423 | list L = M.elements; |
---|
424 | for(int i=1; i<=size(L); i++){ //test for every element of the set, if it is the |
---|
425 | if(isEqual(a,L[i])){ //element to be checked |
---|
426 | return(1); |
---|
427 | } |
---|
428 | } |
---|
429 | return(0); |
---|
430 | } |
---|
431 | example //example for isElement |
---|
432 | { |
---|
433 | "EXAMPLE:"; echo = 2; |
---|
434 | int i=1; |
---|
435 | int j=5; |
---|
436 | list k =1,2,3,4; |
---|
437 | Set M=k; |
---|
438 | i; |
---|
439 | j; |
---|
440 | M; |
---|
441 | isElement(i,M); |
---|
442 | isElement(j,M); |
---|
443 | } |
---|
444 | |
---|
445 | proc complement(Set S, Set M) |
---|
446 | "USAGE: complement(N,M); N,M sets |
---|
447 | RETURN: Set, the complement of the set N in M |
---|
448 | EXAMPLE: example complement, shows an example |
---|
449 | " |
---|
450 | { |
---|
451 | if (!(S<M)){ //check if the complement can be created |
---|
452 | return("Error, first set isn't a subset of the second set."); |
---|
453 | } |
---|
454 | Set N; |
---|
455 | list L1 = S.elements; |
---|
456 | list L2 = M.elements; |
---|
457 | list L = complementOfLists(L1,L2); |
---|
458 | N.elements = L; |
---|
459 | return(N); |
---|
460 | } |
---|
461 | example //example for complement |
---|
462 | { "EXAMPLE:"; echo = 2; |
---|
463 | list l =1,2; |
---|
464 | list j =1,2,3,4; |
---|
465 | Set N=l; |
---|
466 | Set M=j; |
---|
467 | N; |
---|
468 | M; |
---|
469 | complement(N,M); |
---|
470 | } |
---|
471 | |
---|
472 | proc isSubset(Set S, Set M) |
---|
473 | "USAGE: isSubset(N,M) or N<M ; N,M sets |
---|
474 | RETURN: bool, 1 if N is a Subset of M or 0 if not |
---|
475 | EXAMPLE: example isSubset, shows an example |
---|
476 | " |
---|
477 | { |
---|
478 | list L = S.elements; |
---|
479 | list J = M.elements; |
---|
480 | if(size(L)>size(J)){ //check if the first set is smaller then the second |
---|
481 | return(0); |
---|
482 | } |
---|
483 | for(int i=1; i<=size(L); i++){ |
---|
484 | if(!isElement(L[i],M)){ //check if every element of the first set is in the |
---|
485 | return(0); //second set |
---|
486 | } |
---|
487 | } |
---|
488 | return(1); |
---|
489 | } |
---|
490 | example //example for isSubset |
---|
491 | { "EXAMPLE:"; echo = 2; |
---|
492 | list l =1,2; |
---|
493 | list j =1,2,3,4; |
---|
494 | Set N=l; |
---|
495 | Set M=j; |
---|
496 | N; |
---|
497 | M; |
---|
498 | N<M; |
---|
499 | M<N; |
---|
500 | } |
---|
501 | |
---|
502 | proc isSuperset(Set S, Set M) //opposite of isSubset |
---|
503 | "USAGE: isSuperset(N,M) or N>M ; N,M sets |
---|
504 | RETURN: bool, 1 if N is a Superset of M or 0 if not |
---|
505 | EXAMPLE: example isSuperset, shows an example |
---|
506 | " |
---|
507 | { |
---|
508 | return(M<S); |
---|
509 | } |
---|
510 | example //example for isSuperset |
---|
511 | { "EXAMPLE:"; echo = 2; |
---|
512 | list l =1,2; |
---|
513 | list j =1,2,3,4; |
---|
514 | Set N=l; |
---|
515 | Set M=j; |
---|
516 | N; |
---|
517 | M; |
---|
518 | N>M; |
---|
519 | M>N; |
---|
520 | } |
---|