My Project
Loading...
Searching...
No Matches
subsets.cc
Go to the documentation of this file.
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
11static 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
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
76extern "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: variable.h:52
Class used for (list of) interpreter objects.
Definition: subexpr.h:83
int Typ()
Definition: subexpr.cc:1019
int rtyp
Definition: subexpr.h:91
void * Data()
Definition: subexpr.cc:1162
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