1 #if !defined HAVE_MSET_PERM_LEX_REC_H__ 2 #define HAVE_MSET_PERM_LEX_REC_H__ 3 // This file is part of the FXT library. 4 // Copyright (C) 2010, 2012, 2014, 2019 Joerg Arndt 5 // License: GNU General Public License version 3 or later, 6 // see the file COPYING.txt in the main directory. 7 8 9 #include "fxttypes.h" 10 11 class mset_perm_lex_rec 12 // Multiset permutations in lexicographic order, recursive algorithm. 13 { 14 public: 15 ulong k_; // number of different sorts of objects 16 ulong *r_; // number of elements '0' in r[0], '1' in r[1], ..., 'k-1' in r[k-1] 17 ulong n_; // number of objects 18 ulong *ms_; // multiset data in ms[0], ..., ms[n-1] 19 ulong *nn_; // position of next nonempty bucket 20 // nn[k] points initially to the first bucket 21 void (*visit_)(const mset_perm_lex_rec &); // function to call with each permutation 22 ulong ct_; // count objects 23 ulong rct_; // count recursions (==work) 24 25 mset_perm_lex_rec(const mset_perm_lex_rec&) = delete; 26 mset_perm_lex_rec & operator = (const mset_perm_lex_rec&) = delete; 27 28 public: mset_perm_lex_rec(ulong * r,ulong k)29 explicit mset_perm_lex_rec(ulong *r, ulong k) 30 { 31 k_ = k; 32 r_ = new ulong[k]; 33 for (ulong j=0; j<k_; ++j) r_[j] = r[j]; // get buckets 34 35 n_ = 0; 36 for (ulong j=0; j<k_; ++j) n_ += r_[j]; 37 ms_ = new ulong[n_]; 38 39 nn_ = new ulong[k_+1]; // incl sentinel 40 for (ulong j=0; j<k_; ++j) nn_[j] = j+1; 41 nn_[k] = 0; // pointer to first nonempty bucket 42 } 43 ~mset_perm_lex_rec()44 ~mset_perm_lex_rec() 45 { 46 delete [] ms_; 47 delete [] r_; 48 delete [] nn_; 49 } 50 generate(void (* visit)(const mset_perm_lex_rec &))51 void generate(void (*visit)(const mset_perm_lex_rec &)) 52 { 53 visit_ = visit; 54 ct_ = 0; 55 rct_ = 0; 56 mset_perm_rec(0); 57 } 58 59 private: 60 void mset_perm_rec(ulong d); 61 }; 62 // ------------------------- 63 64 65 #endif // !defined HAVE_MSET_PERM_LEX_REC_H__ 66