source: git/misc/subsets.cc @ 653073

spielwiese
Last change on this file since 653073 was fb1675, checked in by Hans Schoenemann <hannes@…>, 7 years ago
use include ".." for singular related .h, p8
  • Property mode set to 100644
File size: 1.9 KB
Line 
1#include "Singular/libsingular.h"
2
3#include <vector>
4
5void 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
26BOOLEAN 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
70extern "C" int SI_MOD_INIT(customstd)(SModulFunctions* p)
71{
72  p->iiAddCproc("subsets.so","subsets",FALSE,subsets);
73  return (MAX_TOK);
74}
Note: See TracBrowser for help on using the repository browser.