001 /*
002 * $Id: PowerSetTest.java 3295 2010-08-26 17:01:10Z kredel $
003 */
004
005 package edu.jas.util;
006
007
008 import java.util.ArrayList;
009 import java.util.List;
010
011 import junit.framework.Test;
012 import junit.framework.TestCase;
013 import junit.framework.TestSuite;
014
015 import edu.jas.arith.BigInteger;
016 import edu.jas.arith.Combinatoric;
017
018
019 /**
020 * PowerSet tests with JUnit.
021 * @author Heinz Kredel.
022 */
023
024 public class PowerSetTest extends TestCase {
025
026
027 /**
028 * main.
029 */
030 public static void main(String[] args) {
031 junit.textui.TestRunner.run(suite());
032 }
033
034
035 /**
036 * Constructs a <CODE>ListUtilTest</CODE> object.
037 * @param name String.
038 */
039 public PowerSetTest(String name) {
040 super(name);
041 }
042
043
044 /**
045 */
046 public static Test suite() {
047 TestSuite suite = new TestSuite(PowerSetTest.class);
048 return suite;
049 }
050
051
052 BigInteger ai;
053
054
055 @Override
056 protected void setUp() {
057 ai = null;
058 }
059
060
061 @Override
062 protected void tearDown() {
063 ai = null;
064 }
065
066
067 /**
068 * Test iterator.
069 *
070 */
071 public void testIterator() {
072 final int N = 10;
073 ai = new BigInteger();
074 List<BigInteger> list = new ArrayList<BigInteger>();
075 for (int i = 0; i < N; i++) {
076 list.add(ai.random(7));
077 }
078 //System.out.println("list = " + list);
079
080 PowerSet<BigInteger> ps = new PowerSet<BigInteger>(list);
081 long i = 0;
082 for (List<BigInteger> subs : ps) {
083 if (i < 0) {
084 System.out.println("subs = " + subs);
085 }
086 if (subs != null) {
087 assertTrue("size(subs) >= 0 ", subs.size() >= 0);
088 i++;
089 }
090 }
091 long j = 1;
092 for (int k = 0; k < N; k++) {
093 j *= 2;
094 }
095 assertEquals("size(ps) == 2**N ", i, j);
096 }
097
098
099 /**
100 * Test k-subset iterator.
101 *
102 */
103 public void noTestKSubsetIterator() {
104 final int N = 10;
105 ai = new BigInteger();
106 List<BigInteger> list = new ArrayList<BigInteger>();
107 for (int i = 0; i < N; i++) {
108 list.add(ai.random(7));
109 }
110 System.out.println("list = " + list);
111
112 KsubSet<BigInteger> ks = new KsubSet<BigInteger>(list, 0);
113 long i = 0;
114 for (List<BigInteger> subs : ks) {
115 if (i >= 0) {
116 System.out.println("subs = " + subs);
117 }
118 if (subs != null) {
119 assertTrue("size(subs) >= 0 ", subs.size() == 0);
120 i++;
121 }
122 }
123 long s = Combinatoric.binCoeff(N, 0).getVal().longValue();
124 assertEquals("size(ks) == " + s + " ", i, s);
125
126 ks = new KsubSet<BigInteger>(list, 1);
127 i = 0;
128 for (List<BigInteger> subs : ks) {
129 if (i >= 0) {
130 System.out.println("subs = " + subs);
131 }
132 if (subs != null) {
133 assertTrue("size(subs) >= 0 ", subs.size() == 1);
134 i++;
135 }
136 }
137 s = Combinatoric.binCoeff(N, 1).getVal().longValue();
138 assertEquals("size(ks) == " + s + " ", i, s);
139
140 ks = new KsubSet<BigInteger>(list, 2);
141 i = 0;
142 for (List<BigInteger> subs : ks) {
143 if (i >= 0) {
144 System.out.println("subs = " + subs);
145 }
146 if (subs != null) {
147 assertTrue("size(subs) >= 0 ", subs.size() == 2);
148 i++;
149 }
150 }
151 s = Combinatoric.binCoeff(N, 2).getVal().longValue();
152 assertEquals("size(ks) == " + s + " ", i, s);
153
154 ks = new KsubSet<BigInteger>(list, 3);
155 i = 0;
156 for (List<BigInteger> subs : ks) {
157 if (i >= 0) {
158 System.out.println("subs = " + subs);
159 }
160 if (subs != null) {
161 assertTrue("size(subs) >= 0 ", subs.size() == 3);
162 i++;
163 }
164 }
165 s = Combinatoric.binCoeff(N, 3).getVal().longValue();
166 assertEquals("size(ks) == " + s + " ", i, s);
167 }
168
169
170 /**
171 * Test any k-subset iterator.
172 *
173 */
174 public void testAnyKSubsetIterator() {
175 final int N = 10;
176 ai = new BigInteger();
177 List<BigInteger> list = new ArrayList<BigInteger>();
178 for (int i = 0; i < N; i++) {
179 list.add(ai.random(7));
180 }
181 //System.out.println("list = " + list);
182
183 for (int k = 0; k <= N; k++) {
184 KsubSet<BigInteger> ks = new KsubSet<BigInteger>(list, k);
185 long i = 0;
186 for (List<BigInteger> subs : ks) {
187 if (i < 0) {
188 System.out.println("subs = " + subs);
189 }
190 if (subs != null) {
191 assertTrue("size(subs) >= 0 ", subs.size() == k);
192 i++;
193 }
194 }
195 long s = Combinatoric.binCoeff(N, k).getVal().longValue();
196 assertEquals("size(ks) == " + s + " ", i, s);
197 }
198 }
199
200 }