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\Consistency;
40
41/**
42 * Class \Hoa\Math\Combinatorics\Combination.
43 *
44 * Some functions related to combinatorics.
45 *
46 * @copyright  Copyright © 2007-2017 Hoa community
47 * @license    New BSD License
48 */
49class Combination
50{
51    /**
52     * Γ^n_k denotes the set of k-uples whose sum of elements is n. For example:
53     * Γ^3_2 = {(2, 0, 0), (1, 1, 0), (1, 0, 1), (0, 2, 0), (0, 1, 1), (0, 0,
54     * 2)}. For any k-uple γ and any α in {1, …, k}, γ_α denotes the α-th
55     * element of γ.
56     *
57     * @param   int   $n              n.
58     * @param   int   $k              k.
59     * @param   bool  $withoutZero    Do not produce solutions with a zero
60     *                                inside.
61     * @return  array
62     */
63    public static function Γ($n, $k, $withoutZero = false)
64    {
65        if (0 === $n) {
66            return [];
67        }
68
69        $out  = [];
70        $tmp  = null;
71        $i    = 0;
72        $o    = array_fill(0, $n, 0);
73        $o[0] = $k;
74
75        while ($k != $o[$i = $n - 1]) {
76            if (false === $withoutZero || !in_array(0, $o)) {
77                $out[] = $o;
78            }
79
80            $tmp   = $o[$i];
81            $o[$i] = 0;
82
83            while ($o[$i] == 0) {
84                --$i;
85            }
86
87            --$o[$i];
88            $o[$i + 1] = $tmp + 1;
89        }
90
91        if (false === $withoutZero || !in_array(0, $o)) {
92            $out[] = $o;
93        }
94
95        return $out;
96    }
97}
98
99/**
100 * Flex entity.
101 */
102Consistency::flexEntity('Hoa\Math\Combinatorics\Combination\Combination');
103