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