← Back to branch summary

~ubuntu-branches/ubuntu/wily/octave-miscellaneous/wily

« back to all changes in this revision

Viewing changes to src/partint.h

  • Committer: Package Import Robot
  • Author(s): Sébastien Villemot, Rafael Laboissiere, Sébastien Villemot
  • Date: 2012-10-17 13:40:55 UTC
  • mfrom: (1.2.1) (12 sid)
  • mto: This revision was merged to the branch mainline in revision 13.
  • Revision ID: package-import@ubuntu.com-20121017134055-vatltexghy77fnv7
Tags: 1.2.0-1
[ Rafael Laboissiere ]
* Imported Upstream version 1.2.0
* Bump Standards-Version to 3.9.4 (no changes needed)
* Refresh for new upstream release
* Use Sébastien Villemot's @debian.org email address
* Remove obsolete DM-Upload-Allowed flag
* Add patch autoload-yes.patch
* Add copyright info for file lauchli.m (included in a Debian patch)
* Add patch partcnt-test-succeeds.patch
* Build-depends on octave-pkg-dev >= 1.0.3

[ Sébastien Villemot ]
* debian/control: fix versioned dependency on debhelper
* Add lintian override for false positive on hardening (fortify)

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/partint.h
 
1
// Copyright (C) 2006 Torsten Finke <fi@igh-essen.com>
 
2
//
 
3
// This program is free software; you can redistribute it and/or modify it under
 
4
// the terms of the GNU General Public License as published by the Free Software
 
5
// Foundation; either version 3 of the License, or (at your option) any later
 
6
// version.
 
7
//
 
8
// This program is distributed in the hope that it will be useful, but WITHOUT
 
9
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 
10
// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 
11
// details.
 
12
//
 
13
// You should have received a copy of the GNU General Public License along with
 
14
// this program; if not, see <http://www.gnu.org/licenses/>.
 
15
 
 
16
class int_partition
 
17
// Integer partitions
 
18
// Reference: 
 
19
//    Joerg Arndt: Algorithms for programmers
 
20
//    (http://www.jjj.de), 2006.
 
21
{
 
22
private:
 
23
    unsigned long *c_;  // partition:  c[1]* 1 + c[2]* 2 + ... + c[n]* n == n
 
24
    unsigned long *s_;  // cumulative sums:  s[j+1] = c[1]* 1 + c[2]* 2 + ... + c[j]* j
 
25
    unsigned long n_;   // partitions of n
 
26
 
 
27
public:
 
28
    int_partition(unsigned long n)
 
29
    {
 
30
        n_ = n;
 
31
        c_ = new unsigned long[n+1];
 
32
        s_ = new unsigned long[n+1];
 
33
        s_[0] = 0;  // unused
 
34
        c_[0] = 0;  // unused
 
35
        first();
 
36
    }
 
37
 
 
38
    ~int_partition()
 
39
    {
 
40
        delete [] c_;
 
41
        delete [] s_;
 
42
    }
 
43
 
 
44
    void first()
 
45
    {
 
46
        c_[1] = n_;
 
47
        for (unsigned long i=2; i<=n_; i++)  { c_[i] = 0; }
 
48
        s_[1] = 0;
 
49
        for (unsigned long i=2; i<=n_; i++)  { s_[i] = n_; }
 
50
    }
 
51
 
 
52
    const unsigned long *data() const  { return c_; }  // one-based!
 
53
 
 
54
    bool next()
 
55
    {
 
56
        // This algorithm was given by Torsten Finke
 
57
        if ( c_[n_]!=0 )  return false;  // last == 1* n (c[n]==1)
 
58
 
 
59
        // Find first coefficient c[i], i>=2 that can be increased:
 
60
        unsigned long i = 2;
 
61
        while ( s_[i]<i )  ++i;
 
62
 
 
63
        ++c_[i];
 
64
        s_[i] -= i;
 
65
        unsigned long z = s_[i];
 
66
        // Now set c[1], c[2], ..., c[i-1] to the first partition
 
67
        // of z into i-1 parts, i.e. set to  z, 0, 0, ..., 0:
 
68
        while ( --i > 1 )
 
69
        {
 
70
            s_[i] = z;
 
71
            c_[i] = 0;
 
72
        }
 
73
        c_[1] = z;  // z* 1 == z
 
74
        // s_[1] unused
 
75
 
 
76
        return true;
 
77
    }
 
78
};