My Project
subsets.cc
Go to the documentation of this file.
1 #include "Singular/libsingular.h"
2 
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 
9 #include <vector>
10 
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)
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]);
22  s_subset(arr,size,left-1,i+1,l,L);
23  l.pop_back();
24  }
25 }
26 
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
32 static BOOLEAN subsets(leftv res, leftv args)
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;
47  s_subset(array,n,k,0,ltemp,lt);
48 
50  Lt->Init(lt.size());
51  for (unsigned i=0; i<lt.size(); i++)
52  {
53  std::vector<int> lti = lt[i];
55  Lti->Init(k);
56  for(unsigned j=0; j<lti.size(); j++)
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
76 extern "C" int SI_MOD_INIT(subsets)(SModulFunctions* p)
77 {
78  p->iiAddCproc("subsets.so","subsets",FALSE,subsets);
79  return (MAX_TOK);
80 }
81 #endif
int BOOLEAN
Definition: auxiliary.h:87
#define TRUE
Definition: auxiliary.h:100
#define FALSE
Definition: auxiliary.h:96
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
int l
Definition: cfEzgcd.cc:100
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
int p
Definition: cfModGcd.cc:4078
Variable next() const
Definition: factory.h:146
Class used for (list of) interpreter objects.
Definition: subexpr.h:83
int Typ()
Definition: subexpr.cc:1011
int rtyp
Definition: subexpr.h:91
void * Data()
Definition: subexpr.cc:1154
leftv next
Definition: subexpr.h:86
void * data
Definition: subexpr.h:88
Definition: lists.h:24
sleftv * m
Definition: lists.h:46
INLINE_THIS void Init(int l=0)
CanonicalForm res
Definition: facAbsFact.cc:60
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
int j
Definition: facHensel.cc:110
void WerrorS(const char *s)
Definition: feFopen.cc:24
VAR omBin slists_bin
Definition: lists.cc:23
slists * lists
Definition: mpr_numeric.h:146
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
#define NULL
Definition: omList.c:12
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
static BOOLEAN subsets(leftv res, leftv args)
Definition: subsets.cc:32
static void s_subset(std::vector< int > &arr, int size, int left, int index, std::vector< int > &l, std::vector< std::vector< int > > &L)
Definition: subsets.cc:11
@ LIST_CMD
Definition: tok.h:118
@ INT_CMD
Definition: tok.h:96
@ MAX_TOK
Definition: tok.h:218