1 | #include "Singular/libsingular.h" |
---|
2 | |
---|
3 | #include <vector> |
---|
4 | |
---|
5 | void subset(std::vector<int> &arr, int size, int left, int index, std::vector<int> &l, std::vector<std::vector<int> > &L) |
---|
6 | { |
---|
7 | if(left==0) |
---|
8 | { |
---|
9 | L.push_back(l); |
---|
10 | return; |
---|
11 | } |
---|
12 | |
---|
13 | for(int i=index; i<size;i++) |
---|
14 | { |
---|
15 | l.push_back(arr[i]); |
---|
16 | subset(arr,size,left-1,i+1,l,L); |
---|
17 | l.pop_back(); |
---|
18 | } |
---|
19 | } |
---|
20 | |
---|
21 | // USAGE: subsets(n,k) n int, k int |
---|
22 | // RETURN: list, a list of lists, |
---|
23 | // representing subsets of {1,...,n} of cardinality k |
---|
24 | // NOTE: the lists will be sorted lexicographically |
---|
25 | // and the elements in each of the lists are sorted naturally |
---|
26 | BOOLEAN subsets(leftv res, leftv args) |
---|
27 | { |
---|
28 | leftv u = args; |
---|
29 | if ((u!=NULL) && (u->Typ()==INT_CMD)) |
---|
30 | { |
---|
31 | leftv v = u->next; |
---|
32 | if ((v!=NULL) && (v->Typ()==INT_CMD) && (v->next==NULL)) |
---|
33 | { |
---|
34 | int n = (int)(long) u->Data(); |
---|
35 | int k = (int)(long) v->Data(); |
---|
36 | std::vector<int> array(n); |
---|
37 | for (int i=0; i<n; i++) |
---|
38 | array[i]=i+1; |
---|
39 | std::vector<int> ltemp; |
---|
40 | std::vector<std::vector<int> > lt; |
---|
41 | subset(array,n,k,0,ltemp,lt); |
---|
42 | |
---|
43 | lists Lt = (lists) omAllocBin(slists_bin); |
---|
44 | Lt->Init(lt.size()); |
---|
45 | for (int i=0; i<lt.size(); i++) |
---|
46 | { |
---|
47 | std::vector<int> lti = lt[i]; |
---|
48 | lists Lti = (lists) omAllocBin(slists_bin); |
---|
49 | Lti->Init(k); |
---|
50 | for(int j=0; j<lti.size(); j++) |
---|
51 | { |
---|
52 | Lti->m[j].rtyp = INT_CMD; |
---|
53 | Lti->m[j].data = (void*)(long)lti[j]; |
---|
54 | } |
---|
55 | Lt->m[i].rtyp = LIST_CMD; |
---|
56 | Lt->m[i].data = (void*) Lti; |
---|
57 | } |
---|
58 | |
---|
59 | res->rtyp = LIST_CMD; |
---|
60 | res->data = (void*) Lt; |
---|
61 | return FALSE; |
---|
62 | } |
---|
63 | } |
---|
64 | WerrorS("subsets: unexpected parameter"); |
---|
65 | return TRUE; |
---|
66 | } |
---|
67 | |
---|
68 | //------------------------------------------------------------------------ |
---|
69 | // initialisation of the module |
---|
70 | extern "C" int SI_MOD_INIT(customstd)(SModulFunctions* p) |
---|
71 | { |
---|
72 | p->iiAddCproc("subsets.so","subsets",FALSE,subsets); |
---|
73 | return (MAX_TOK); |
---|
74 | } |
---|