1<?php
2
3/**
4 * Hoa
5 *
6 *
7 * @license
8 *
9 * New BSD License
10 *
11 * Copyright © 2007-2017, Hoa community. All rights reserved.
12 *
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions are met:
15 *     * Redistributions of source code must retain the above copyright
16 *       notice, this list of conditions and the following disclaimer.
17 *     * Redistributions in binary form must reproduce the above copyright
18 *       notice, this list of conditions and the following disclaimer in the
19 *       documentation and/or other materials provided with the distribution.
20 *     * Neither the name of the Hoa nor the names of its contributors may be
21 *       used to endorse or promote products derived from this software without
22 *       specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
25 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS AND CONTRIBUTORS BE
28 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
29 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
30 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
31 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
32 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
33 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34 * POSSIBILITY OF SUCH DAMAGE.
35 */
36
37namespace Hoa\Math\Combinatorics\Combination;
38
39use Hoa\Iterator;
40
41/**
42 * Class \Hoa\Math\Combinatorics\Combination\Gamma.
43 *
44 * Gamma^n_k denotes the set of k-uples whose sum of elements is n. For example:
45 * Gamma^2_3 = {(2, 0, 0), (1, 1, 0), (1, 0, 1), (0, 2, 0), (0, 1, 1), (0, 0, 2)}.
46 * For any k-uple γ and any α in {1, …, k}, γ_α denotes the α-th element of γ.
47 * This class is identical to \Hoa\Math\Combinatorics\Combination::Gamma with a
48 * “yield” keyword.
49 *
50 * @copyright  Copyright © 2007-2017 Hoa community
51 * @license    New BSD License
52 */
53class Gamma implements Iterator
54{
55    /**
56     * n.
57     *
58     * @var int
59     */
60    protected $_n       = 0;
61
62    /**
63     * k.
64     *
65     * @var int
66     */
67    protected $_k       = 0;
68
69    /**
70     * For iterator.
71     *
72     * @var int
73     */
74    protected $_current = null;
75
76    /**
77     * For iterator.
78     *
79     * @var int
80     */
81    protected $_key     = -1;
82
83    /**
84     * For iterator.
85     *
86     * @var array
87     */
88    protected $_tmp     = null;
89
90    /**
91     * For iterator.
92     *
93     * @var int
94     */
95    protected $_i       = 0;
96
97    /**
98     * For iterator.
99     *
100     * @var int
101     */
102    protected $_o       = 0;
103
104    /**
105     * For iterator.
106     *
107     *
108     * @var bool
109     */
110    protected $_last    = false;
111
112
113
114    /**
115     * Constructor.
116     *
117     * @param   int  $n    n.
118     * @param   int  $k    k.
119     */
120    public function __construct($n, $k)
121    {
122        $this->_n = $n;
123        $this->_k = $k;
124
125        return;
126    }
127
128    /**
129     * Get current γ.
130     *
131     * @return  array
132     */
133    public function current()
134    {
135        return $this->_current;
136    }
137
138    /**
139     * Get current α.
140     *
141     * @return  int
142     */
143    public function key()
144    {
145        return $this->_key;
146    }
147
148    /**
149     * Compute γ_{α + 1}.
150     *
151     * @return  void
152     */
153    public function next()
154    {
155        return;
156    }
157
158    /**
159     * Rewind iterator.
160     *
161     * @return  void
162     */
163    public function rewind()
164    {
165        $this->_current = [];
166        $this->_tmp     = null;
167        $this->_i       = 0;
168        $this->_o       = 0 === $this->_n
169                              ? [0]
170                              : array_fill(0, $this->_n, 0);
171        $this->_o[0]    = $this->_k;
172        $this->_last    = false;
173
174        return;
175    }
176
177    /**
178     * Compute γ_α.
179     *
180     * @return  bool
181     */
182    public function valid()
183    {
184        if (true === $this->_last) {
185            return false;
186        }
187
188        if (0 === $this->_n) {
189            return false;
190        }
191
192        if ($this->_k == $this->_o[$this->_i = $this->_n - 1]) {
193            $this->_last    = true;
194            $this->_current = $this->_o;
195            ++$this->_key;
196
197            return true;
198        }
199
200        $this->_current = $this->_o;
201        ++$this->_key;
202
203        $this->_tmp          = $this->_o[$this->_i];
204        $this->_o[$this->_i] = 0;
205
206        while ($this->_o[$this->_i] == 0) {
207            --$this->_i;
208        }
209
210        --$this->_o[$this->_i];
211        $this->_o[$this->_i + 1] = $this->_tmp + 1;
212
213        return true;
214    }
215}
216