001/*
002 * $Id$
003 */
004
005package edu.jas.util;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import junit.framework.Test;
012import junit.framework.TestCase;
013import junit.framework.TestSuite;
014
015import edu.jas.arith.BigInteger;
016import edu.jas.arith.Combinatoric;
017
018
019/**
020 * PowerSet tests with JUnit.
021 * @author Heinz Kredel
022 */
023
024public 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}