001/** 002 * BinomialCoef -- A class that represents a set of binomial coefficients of a specified 003 * size. 004 * 005 * Copyright (C) 2011-2025, by Joseph A. Huwaldt. All rights reserved. 006 * 007 * This library is free software; you can redistribute it and/or modify it under the terms 008 * of the GNU Lesser General Public License as published by the Free Software Foundation; 009 * either version 2 of the License, or (at your option) any later version. 010 * 011 * This library is distributed in the hope that it will be useful, but WITHOUT ANY 012 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A 013 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. 014 * 015 * You should have received a copy of the GNU Lesser General Public License along with 016 * this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - 017 * Suite 330, Boston, MA 02111-1307, USA. Or visit: http://www.gnu.org/licenses/lgpl.html 018 */ 019package jahuwaldt.js.math; 020 021import jahuwaldt.js.util.SizedObject; 022import jahuwaldt.js.util.SizedObjectFactory; 023import javolution.lang.ValueType; 024import javolution.text.Text; 025import javolution.text.TextBuilder; 026 027/** 028 * <p> 029 * This class represents an immutable matrix of binomial coefficients (n/k) defined up to 030 * a specified maximum index. 031 * </p> 032 * <pre> 033 * ( n ) n! 034 * ( ) = -------- 0 ≤ k ≤ n 035 * ( k ) k!(n-k)! 036 * </pre> 037 * 038 * <p> Reference: http://en.wikipedia.org/wiki/Binomial_coefficient</p> 039 * 040 * <p> Modified by: Joseph A. Huwaldt </p> 041 * 042 * @author Joseph A. Huwaldt, Date: May 11, 2011 043 * @version February 22, 2025 044 */ 045public final class BinomialCoef implements ValueType, SizedObject { 046 047 /** 048 * The coefficients are stored in the this matrix. 049 */ 050 private final double[][] _coefs; 051 052 /** 053 * Returns a {@link BinomialCoef} instance holding the coefficients (at least) up to 054 * the specified size. The returned instance may be recycled and may contain more 055 * coefficients than the requested size. 056 * 057 * @param size the desired size to compute coefficients for: 058 * <code>N = size - 1 ==> (N/N)</code> or <code>size = N + 1</code>. 059 * @return The binomial coefficient matrix having at least specified size. 060 */ 061 public static BinomialCoef newInstance(int size) { 062 BinomialCoef M = FACTORY.object(size); 063 return M; 064 } 065 066 /** 067 * Return the size of the binomial coefficient matrix (the maximum binomial index 068 * value: (N/N)). 069 */ 070 @Override 071 public int size() { 072 return _coefs.length; 073 } 074 075 /** 076 * Return the specified binomial coefficient (n / k) 077 * 078 * @param n The 1st index into the binomial coefficient matrix (n / k). Must be < 079 * size(). 080 * @param k The 2nd index into the binomial coefficient matrix (n / k). Must be < 081 * size(). 082 * @return The specified binomial coefficient as a double. 083 */ 084 public double get(int n, int k) { 085 return _coefs[n][k]; 086 } 087 088 /** 089 * Returns a copy of this binomial coefficient matrix 090 * {@link javolution.context.AllocatorContext allocated} by the calling thread 091 * (possibly on the stack). 092 * 093 * @return an identical and independent copy of this binomial coefficient matrix. 094 */ 095 @Override 096 public BinomialCoef copy() { 097 return copyOf(this); 098 } 099 100 /** 101 * Recycles a <code>BinomialCoef</code> instance immediately (on the stack when 102 * executing in a StackContext). 103 * 104 * @param instance The instance of this class to be recycled. 105 */ 106 public static void recycle(BinomialCoef instance) { 107 FACTORY.recycle(instance); 108 } 109 110 /** 111 * Returns the text representation of this binomial coefficient matrix. 112 * 113 * @return the text representation of this binomial coefficient matrix. 114 */ 115 public Text toText() { 116 TextBuilder tmp = TextBuilder.newInstance(); 117 118 tmp.append('{'); 119 int size = size() + 1; 120 for (int i = 0; i < size; i++) { 121 tmp.append('{'); 122 for (int j = 0; j < size; ++j) { 123 tmp.append(get(i, j)); 124 if (j != size - 1) 125 tmp.append(", "); 126 } 127 tmp.append('}'); 128 } 129 tmp.append('}'); 130 131 Text txt = tmp.toText(); 132 TextBuilder.recycle(tmp); 133 return txt; 134 } 135 136 /** 137 * Method that actually allocates a new array and fills it with binomial coefficients. 138 */ 139 private static double[][] binomial(int size) { 140 double[][] bin = new double[size][size]; 141 142 // Setup the first line 143 @SuppressWarnings("MismatchedReadAndWriteOfArray") 144 double[] row0 = bin[0]; 145 row0[0] = 1.0; 146 for (int k = 1; k < size; ++k) 147 row0[k] = 0.; 148 149 // Setup the other lines 150 for (int n = 0; n < size - 1; n++) { 151 @SuppressWarnings("MismatchedReadAndWriteOfArray") 152 double[] binnp1 = bin[n + 1]; 153 binnp1[0] = 1.0; 154 double[] binn = bin[n]; 155 for (int k = 1; k < size; k++) { 156 if (n + 1 < k) 157 binn[k] = 0.0; 158 else 159 binnp1[k] = binn[k] + binn[k - 1]; 160 } 161 } 162 return bin; 163 } 164 165 /////////////////////// 166 // Factory creation. // 167 /////////////////////// 168 @SuppressWarnings("unchecked") 169 private static SizedObjectFactory<BinomialCoef> FACTORY = new SizedObjectFactory<BinomialCoef>() { 170 @Override 171 protected BinomialCoef create(int size) { 172 BinomialCoef M = new BinomialCoef(size); 173 return M; 174 } 175 }; 176 177 @SuppressWarnings("unchecked") 178 private static BinomialCoef copyOf(BinomialCoef original) { 179 int size = original.size(); 180 BinomialCoef M = BinomialCoef.newInstance(size); 181 return M; 182 } 183 184 private BinomialCoef() { 185 _coefs = null; 186 } 187 188 private BinomialCoef(int size) { 189 _coefs = binomial(size); 190 } 191 192}