Strategy or Iterator?

[Ed Kirwan]

It is like croquet. The most genteel people turn cutthroat with
sufficient exposure.

I played croquet once. I found the experience of having my balls whacked
with mallets most distressing.

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Stefan Ram schreef:

Think of the Scrabble game; if you have seven letters in your
hand then ideally you'd like to use up all seven of them[*].
So that would mean considering all possible permutations of
those letters. But if there isn't a suitable word, then you
have to consider shorter words that don't use all the letters.
Say you consider 5-letter words: that's my last kind of
"permutation" -- what I call permutations of length 5.

OK, you want all permutations of all combinations.

To implement this, one can nest two iterators. I have a
combinator in my library, which can combine them to a new
iterator, but for this post I will use nested loops.

Then, the source code:

public class Main

Didn?t someone say something about not calling you class Main? Whatever ;-)

class Permutations
implements
java.lang.Iterable<java.lang.Object[]>,
java.util.Iterator<java.lang.Object[]>

Almost the same as mine, except that I made the class itself generic.

public final java.lang.Object[] next()
{ copyToResult();
int j = this.zzLength - 1;
while( j > 0 && this.zzC[ j - 1 ]>= this.zzC[ j + 1 - 1 ])--j;
if( j == 0 ){ this.zzHasNext = false; }

Nice trick, saves the counting.

else
{ int l = this.zzLength;
while( this.zzC[ j - 1 ]>= this.zzC[ l - 1 ])--l;
swap( this.zzC, j - 1, l - 1 );
{ int k = j + 1;

You can just reuse j here.

class Combinations
implements
java.lang.Iterable<java.lang.Object[]>,
java.util.Iterator<java.lang.Object[]>

Idem.

H.
--
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFEDET8e+7xMGD3itQRAnVwAJ9JAec8PSsmFrnc/w8Rd0S8g3xDhgCeIOg6
Mbi9SuxI2XDCu4E8Ck3Ho5w=
=y/YT
-----END PGP SIGNATURE-----

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Roedy Green schreef:

Do you want me to add your code of the permutations entry?

As you wish. Basically, it is very much the same as the code Stefan Ram
posted, except that I didn?t implement the algorithms myself -p),
made my class generic, and it is documented (very elaborately; you can
see I am still an idealistic beginner).

It would be possible to write a class that returns the variations
without repetition, but that is rather pointless, as Stefan pointed out:
you can just combine the Permuter and Combinator. The one thing still
to do is variations with repetition.

I thought about lifting some code to a superclass, but that didn?t
really seem useful (yet).

Here are my two classes and a little test:

import java.math.BigInteger;
import static java.math.BigInteger.ZERO;
import static java.math.BigInteger.ONE;
import java.util.Iterator;

/**
* A class that permutes a given array of elements. It is an iterator that
* returns all permutations, successively. Thanks to Tim Tyler for the
* original implementation {@link http://mandala.co.uk/permutations/}.
*
* @author <a href="mailto:[email protected]">Hendrik
Maryns</a>
* @param <T> The type of the array to be permuted.
* TODO: extract these two into superclass.
*/
public class Permuter<T> implements Iterator<T[]>, Iterable<T[]> {

/**
* Initialise a new permuter, with given array of elements to permute.
*
* @param elements
* The elements to permute.
* @post The total number is set to the factorial of the number of
* elements.
* | new.getTotal() == factorial(elements.length)
* @post The number of permutations left is set to the total number.
* | new.getNumLeft() == new.getTotal()
*/
public Permuter(T[] elements) {
this.elements = elements.clone();
indexes = new int[elements.length];
total = factorial(elements.length);
reset();
}

/**
* The elements the permutor works upon.
*/
private T[] elements;

/**
* A backing array which takes care of the algorithm (needed because I
don't
* want to demand that T extends Comparable<T>).
*/
private int[] indexes;

/**
* The total number of permutations to be computed.
*/
private BigInteger total;

/**
* The number of permutations to go.
*/
private BigInteger count;

/**
* Returns the next element in the iteration. After the last element is
* reached, this will keep on returning the same element, until the
reset()
* method is called. </p>
* <p>Algorithm due to Dijkstra, see also
* {@link http://www.cut-the-knot.org/do_you_know/AllPerm.shtml}.
*
* @see java.util.Iterator#next()
*/
public T[] next() {
if (!count.equals(total)) {
// find the rightmost element that is smaller than the element at
its right
int i = indexes.length - 1;
while (indexes[i - 1] >= indexes)
i = i - 1;
// find the rightmost element that is bigger then the other one
int j = indexes.length;
while (indexes[j - 1] <= indexes[i - 1])
j = j - 1;
// swap them (always is i < j)
swap(i - 1, j - 1);
// now the elements at the right of i are in descending order, so
reverse them all
i++;
j = indexes.length;
while (i < j) {
swap(i - 1, j - 1);
i++;
j--;
}
// TODO: try other algorithms, see
http://www.cut-the-knot.org/Curriculum/Combinatorics/JohnsonTrotter.shtml
}
count = count.subtract(ONE);
return elements.clone();
}

/**
* Swap the elements at positions a and b, both from the index array and
* from the element array.
*
* @param a, b
* The indices of the elements to be swapped.
* @post The elements at indices a and b of indexes and elements are
* swapped.
* | new.indexes[a] = indexes
* | new.indexes = indexes[a]
* | new.elements[a] = elements
* | new.elements = elements[a]
*/
private void swap(int a, int b) {
int temp = indexes[a];
indexes[a] = indexes;
indexes = temp;

T tempT = elements[a];
elements[a] = elements;
elements = tempT;
}

/**
* Returns <tt>true</tt> if the iteration has more elements. This is the
* case if not all n! permutations have been covered.
*
* @return The number of permutations to go is bigger than zero.
* | result == getNumLeft().compareTo(BigInteger.ZERO) > 0;
* @see java.util.Iterator#hasNext()
*/
public boolean hasNext() {
return count.compareTo(ZERO) > 0;
}

/**
* Return number of permutations not yet generated.
*/
public BigInteger getNumLeft() {
return count;
}

/**
* Return the total number of combinations.
*
* @return The factorial of the number of elements.
* That is, with the number of elements = n: n!
*/
public BigInteger getTotal() {
return total;
}

/**
* Not supported.
*
* @see java.util.Iterator#remove()
*/
public void remove() {
throw new UnsupportedOperationException();
}

/**
* Reset the iteration.
*/
public void reset() {
count = total;
for (int i = 0; i < indexes.length; i++) {
indexes = i;
}
}

/**
* Return an iterator over the permutations of the elements. Since a
* Permuter also implements Iterator<T[]>, it just returns itself.
*
* @return Itself.
* | result == this
* @see java.lang.Iterable#iterator()
*/
public Iterator<T[]> iterator() {
return this;
}

/**
* Compute the factorial of n.
*/
public static BigInteger factorial(int n) {
BigInteger fact = ONE;
for (int i = n; i > 1; i--) {
fact = fact.multiply(BigInteger.valueOf(i));
}
return fact;
}

}

import static java.math.BigInteger.ONE;
import static java.math.BigInteger.ZERO;

import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.Iterator;

/**
* A class that sequentially returns all combinations of a certain
number out of
* an array of given elements. Thanks to Michael Gillegand for the base
* implementation: {@link http://www.merriampark.com/comb.htm}
*
* @author <a href="mailto:[email protected]">Hendrik
Maryns</a>
* @param <T> The type of the elements of which combinations are to be
* returned.
*/
public class Combinator<T> implements Iterator<T[]>, Iterable<T[]> {

/**
* Initialise a new Combinator, with given elements and size of the
arrays
* to be returned.
*
* @param elements
* The elements of which combinations have to be computed.
* @param r
* The size of the combinations to compute.
* @pre r should not be greater than the length of the elements, and
* not smaller than 0.
* | 0 <= r <= elements.length
* @post The total number of iterations is set to the correct
number, see
* {@link #getTotal()}.
* | new.getTotal() == factorial(elements.length).divide(
* | factorial(r).multiply(factorial(elements.length-r))
* @post The number of combinations left is set to the total number.
* | new.getNumLeft() == new.getTotal()
* @throws IllegalArgumentException
* If r is bigger than the length of the elemet array.
* | r > elements.length
*/
public Combinator(T[] elements, int r) {
assert 0 <= r && r <= elements.length;
this.r = r;
a = new int[r];
this.elements = elements.clone();
BigInteger nFact = factorial(elements.length);
BigInteger rFact = factorial(r);
BigInteger nminusrFact = factorial(elements.length - r);
total = nFact.divide(rFact.multiply(nminusrFact));
reset();
}

/**
* The elements the permutor works upon.
*/
private T[] elements;

/**
* An integer array backing up the original one to keep track of the
* combinations.
*/
private int[] a;

/**
* The size of the combinations to compute.
*/
private int r;

/**
* The combinations still to go.
*/
private BigInteger numLeft;

/**
* The total number of combinations to be computed.
*/
private BigInteger total;

/**
* Reset the iteration.
*/
public void reset() {
for (int i = 0; i < a.length; i++) {
a = i;
}
numLeft = total;
}

/**
* Return number of combinations not yet generated.
*/
public BigInteger getNumLeft() {
return numLeft;
}

/**
* Return the total number of combinations.
*
* @return The factorial of the number of elements divided by the
* factorials of the size of the combinations and the number of
* elements minus the size of the combinations.
* That is, with the number of elements = n and the size of the
* combinations = r:
* n n!
* ( ) = ---------
* r (n-r)!r!
*/
public BigInteger getTotal() {
return total;
}

/**
* Returns <tt>true</tt> if the iteration has more elements. This is the
* case if not all n! permutations have been covered.
*
* @return The number of permutations to go is bigger than zero.
* | result == getNumLeft().compareTo(BigInteger.ZERO) > 0;
* @see java.util.Iterator#hasNext()
*/
public boolean hasNext() {
return numLeft.compareTo(ZERO) == 1;
}

/**
* Compute the next combination.
*
* @see java.util.Iterator#next()
*/
public T[] next() {
if (!numLeft.equals(total)) {
int i = r - 1;
int n = elements.length;
while (a == n - r + i) {
i--;
}
a = a + 1;
for (int j = i + 1; j < r; j++) {
a[j] = a + j - i;
}
}
numLeft = numLeft.subtract(ONE);
return getResult(a);

}

/**
* Compute the result, based on the given array of indices.
*
* @param indices
* An array of indices into the element array.
* @return An array consisting of the elements at positions of the given
* array.
* | result == elements[a]
*/
@SuppressWarnings("unchecked")
private T[] getResult(int[] indices) {
T[] result = (T[]) Array.newInstance(elements.getClass()
.getComponentType(), indices.length);
for (int i = 0; i < result.length; i++) {
result = elements[indices];
}
return result;
}

/**
* Not supported.
*
* @see java.util.Iterator#remove()
*/
public void remove() {
throw new UnsupportedOperationException();
}

/**
* A combinator is itself an iterator.
*
* @return Itself.
* | result == this
* @see java.lang.Iterable#iterator()
*/
public Iterator<T[]> iterator() {
return this;
}

/**
* Compute the factorial of n.
*/
public static BigInteger factorial(int n) {
BigInteger fact = ONE;
for (int i = n; i > 1; i--) {
fact = fact.multiply(BigInteger.valueOf(i));
}
return fact;
}

}

import java.util.Arrays;

public class PermuterTest {

public static void main(String args[]) {
final Integer[] data = new Integer[5];
for (int i = 0; i < data.length; i++) {
data = i;
}
for (int i = 0; i <= data.length; i++) {

for (Integer[] combination: new Combinator<Integer>(data, i)) {
for (Integer[] variation: new Permuter<Integer>(combination))
System.out.println(Arrays.toString(variation));
}
}
}

}


Thanks all & have fun using this, H.
--
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFEDEuce+7xMGD3itQRAj4rAJsFxV+4ZckqekcdpW5fAX5GDKVvmwCfXJlo
QK0p+hRYcRvSkNMKt4I6Hw0=
=6nKl
-----END PGP SIGNATURE-----

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Hendrik Maryns schreef:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Roedy Green schreef:

As you wish. Basically, it is very much the same as the code Stefan Ram
posted, except that I didn?t implement the algorithms myself -p),
made my class generic, and it is documented (very elaborately; you can
see I am still an idealistic beginner).

It would be possible to write a class that returns the variations
without repetition, but that is rather pointless, as Stefan pointed out:
you can just combine the Permuter and Combinator. The one thing still
to do is variations with repetition.

I thought about lifting some code to a superclass, but that didn?t
really seem useful (yet).

Here are my two classes and a little test:

It was obvious that those classes suffered from many copy-paste. I
found a nicer way to combine them, by using the template method
approach. It makes Permuter a bit less performant, I guess, but much
clearer. I also added a class VariationsWithRepetition. This last one
is the one I actually needed, it returns the r-times cartesian product
of the supplied array.

Here is the result. Other classes such as combinations with repetition
can easily be added by deriving from the CombinatoricOperation class and
implementing the two abstract methods. Sometimes, you will have to
override initialiseIndices too. I know I do not use assertions the way
Sun intended them to be used.

/*
* CombinatoricOperator.java
*
* Created on 7-mrt-2006
*
* Copyright (C) 2006 Hendrik Maryns <[email protected]>.
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA.
*/
package de.uni_tuebingen.sfb.macke.utilities;

import static java.math.BigInteger.ONE;
import static java.math.BigInteger.ZERO;

import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.Iterator;

/**
* A common superclass for all combinatoric operators. Makes use of the
* template method pattern to define all others.
*
* @author <a href="mailto:[email protected]">Hendrik
Maryns</a>
*/
public abstract class CombinatoricOperator<T> implements Iterator<T[]>,
Iterable<T[]> {

/**
* Initialise a new operator, with given elements and size of the arrays
* to be returned.
*
* @param elements
* The elements on which this combinatoric operator has to act.
* @param r
* The size of the arrays to compute.
* @pre r should not be smaller than 0.
* | 0 <= r
* @post The total number of iterations is set to the correct number.
* | new.getTotal() == initialiseTotal();
* @post The number of variations left is set to the total number.
* | new.getNumLeft() == new.getTotal()
*/
protected CombinatoricOperator(T[] elements, int r) {
assert 0 <= r;
indices = new int[r];
this.elements = elements.clone();
total = initialiseTotal(elements.length, r);
reset();
}

/**
* The elements the operator works upon.
*/
protected T[] elements;

/**
* An integer array backing up the original one to keep track of the
* indices.
*/
protected int[] indices;

/**
* Initialise the array of indices. By default, it is initialised with
* incrementing integers.
*/
protected void initialiseIndices() {
for (int i = 0; i < indices.length; i++) {
indices = i;
}
}

/**
* The variations still to go.
*/
private BigInteger numLeft;

/**
* The total number of variations to be computed.
*/
private BigInteger total;

/**
* Compute the total number of elements to return.
*
* @param n
* The number of elements the operator works on.
* @param r
* The size of the arrays to return.
* @return The total number of elements is always bigger than 0.
* | result >= 0
*/
protected abstract BigInteger initialiseTotal(int n, int r);

/**
* Reset the iteration.
*
* @post The number of iterations to go is the same as the total number
* of iterations.
* | new.getNumLeft() == getTotal()
*/
public void reset() {
initialiseIndices();
numLeft = total;
}

/**
* Return number of variations not yet generated.
*/
public BigInteger getNumLeft() {
return numLeft;
}

/**
* Return the total number of variations.
*
* @return The factorial of the number of elements divided by the
* factorials of the size of the variations and the number of
* elements minus the size of the variations.
* That is, with the number of elements = n and the size of the
* variations = r: n^r
*/
public BigInteger getTotal() {
return total;
}

/**
* Returns <tt>true</tt> if the iteration has more elements. This is the
* case if not all n! permutations have been covered.
*
* @return The number of permutations to go is bigger than zero.
* | result == getNumLeft().compareTo(BigInteger.ZERO) > 0;
* @see java.util.Iterator#hasNext()
*/
public boolean hasNext() {
return numLeft.compareTo(ZERO) == 1;
}

/**
* Compute the next combination.
*
* @see java.util.Iterator#next()
*/
public T[] next() {
if (!numLeft.equals(total)) {
computeNext();
}
numLeft = numLeft.subtract(ONE);
return getResult(indices);
}

/**
* Compute the next array of indices.
*/
protected abstract void computeNext();

/**
* Compute the result, based on the given array of indices.
*
* @param indexes
* An array of indices into the element array.
* @return An array consisting of the elements at positions of the given
* array.
* | result == elements[indexes]
*/
@SuppressWarnings("unchecked")
private T[] getResult(int[] indexes) {
T[] result = (T[]) Array.newInstance(elements.getClass()
.getComponentType(), indexes.length);
for (int i = 0; i < result.length; i++) {
result = elements[indexes];
}
return result;
}

/**
* Not supported.
*
* @see java.util.Iterator#remove()
*/
public void remove() {
throw new UnsupportedOperationException();
}

/**
* A combinatoric operator is itself an iterator.
*
* @return Itself.
* | result == this
* @see java.lang.Iterable#iterator()
*/
public Iterator<T[]> iterator() {
return this;
}

/**
* Compute the factorial of n.
*/
public static BigInteger factorial(int n) {
BigInteger fact = ONE;
for (int i = n; i > 1; i--) {
fact = fact.multiply(BigInteger.valueOf(i));
}
return fact;
}
}

/*
* Combinator.java
*
* Created on 3-mrt-2006, based on CombinationGenerator from Michael
Gilleland.
*
* Copyright (C) 2006 Hendrik Maryns <[email protected]>.
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA.
*/
package de.uni_tuebingen.sfb.macke.utilities;

import java.math.BigInteger;

/**
* A class that sequentially returns all combinations of a certain
number out of
* an array of given elements. Thanks to Michael Gillegand for the base
* implementation: {@link http://www.merriampark.com/comb.htm}
*
* @author <a href="mailto:[email protected]">Hendrik
Maryns</a>
* @param <T> The type of the elements of which combinations are to be
* returned.
*/
public class Combinator<T> extends CombinatoricOperator<T> {

/**
* Initialise a new Combinator, with given elements and size of the arrays
* to be returned.
*
* @param elements
* The elements of which combinations have to be computed.
* @param r
* The size of the combinations to compute.
* @pre r should not be greater than the length of the elements, and
* not smaller than 0.
* | 0 <= r <= elements.length
* @post The total number of iterations is set to the factorial of the
* number of elements divided by the factorials of the size of the
* combinations and the number of elements minus the size of the
* combinations. That is, with the number of elements = n and the
* size of the combinations = r:
* n n!
* ( ) = ---------
* r (n-r)!r!
* | new.getTotal() == factorial(elements.length).divide(
* | factorial(r).multiply(factorial(elements.length-r))
* @post The number of combinations left is set to the total number.
* | new.getNumLeft() == new.getTotal()
*/
public Combinator(T[] elements, int r) {
super(elements, r);
assert r <= elements.length;
}

/**
* Compute the total number of elements to return.
*
* @return The factorial of the number of elements divided by the
* factorials of the size of the combinations and the number of
* elements minus the size of the combinations.
* That is, with the number of elements = n and the size of the
* combinations = r:
* n n!
* ( ) = ---------
* r (n-r)!r!
* @see CombinatoricOperator#initialiseTotal(int, int)
*/
@Override
protected BigInteger initialiseTotal(int n, int r) {
BigInteger nFact = factorial(n);
BigInteger rFact = factorial(r);
BigInteger nminusrFact = factorial(n - r);
return nFact.divide(rFact.multiply(nminusrFact));
}

/**
* Compute the next array of indices.
*
* @see CombinatoricOperator#computeNext()
*/
@Override
protected void computeNext() {
int r = indices.length;
int i = r - 1;
int n = elements.length;
while (indices == n - r + i) {
i--;
}
indices = indices + 1;
for (int j = i + 1; j < r; j++) {
indices[j] = indices + j - i;
}
// TODO: understand this.
}

}

/*
* Permuter.java
*
* Created on 3-mar-2006, based on Permutations from Tim Tyler.
*
* Copyright (C) 2005 Hendrik Maryns <[email protected]>.
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA.
*/
package de.uni_tuebingen.sfb.macke.utilities;

import java.math.BigInteger;

/**
* A class that permutes a given array of elements. It is an iterator that
* returns all permutations, successively. Thanks to Tim Tyler for the
* original implementation {@link http://mandala.co.uk/permutations/}.
*
* @author <a href="mailto:[email protected]">Hendrik
Maryns</a>
* @param <T> The type of the array to be permuted.
*/
public class Permuter<T> extends CombinatoricOperator<T> {

/**
* Initialise a new permuter, with given array of elements to permute.
*
* @param elements
* The elements to permute.
* @post The total number is set to the factorial of the number of
* elements.
* | new.getTotal() == factorial(elements.length)
* @post The number of permutations left is set to the total number.
* | new.getNumLeft() == new.getTotal()
*/
public Permuter(T[] elements) {
super(elements, elements.length);
}

/**
* Compute the total number of elements to return.
*
* @return The factorial of the number of elements.
* | result == factorial(n)
* @see CombinatoricOperator#initialiseTotal(int, int)
*/
@Override
protected BigInteger initialiseTotal(int n, int r) {
return factorial(n);
}

/**
* Compute the next array of indices.
*
* @see CombinatoricOperator#computeNext()
*/
@Override
protected void computeNext() {
// find the rightmost element that is smaller than the element at its
right
int i = indices.length - 1;
while (indices[i - 1] >= indices)
i = i - 1;
// find the rightmost element that is bigger then the other one
int j = indices.length;
while (indices[j - 1] <= indices[i - 1])
j = j - 1;
// swap them (always is i < j)
swap(i - 1, j - 1);
// now the elements at the right of i are in descending order, so
reverse them all
i++;
j = indices.length;
while (i < j) {
swap(i - 1, j - 1);
i++;
j--;
}
// TODO: try other algorithms, see
http://www.cut-the-knot.org/Curriculum/Combinatorics/JohnsonTrotter.shtml
}

/**
* Swap the elements at positions a and b, both from the index array and
* from the element array.
*
* @param a, b
* The indices of the elements to be swapped.
* @post The elements at indices a and b of the array of indices are
* swapped.
* | new.indexes[a] = indexes
* | new.indexes = indexes[a]
*/
private void swap(int a, int b) {
int temp = indices[a];
indices[a] = indices;
indices = temp;
}

}

/*
* VariatorWithRepetition.java
*
* Created on 7-mrt-2006
*
* Copyright (C) 2006 Hendrik Maryns <[email protected]>.
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA.
*/
package de.uni_tuebingen.sfb.macke.utilities;

import java.math.BigInteger;
import java.util.Arrays;

/**
* A class that sequentially returns all variations with repetition of a
certain
* number out of an array of given elements.
*
* @author <a href="mailto:[email protected]">Hendrik
Maryns</a>
* @param <T> The type of the elements of which variations are to be
* returned.
*/
public class VariatorWithRepetition<T> extends CombinatoricOperator<T> {

/**
* Initialise a new variator, with given elements and size of the arrays
* to be returned.
*
* @param elements
* The elements of which variations have to be computed.
* @param r
* The size of the variations to compute.
* @pre r should not be smaller than 0.
* | 0 <= r
* @post The total number of iterations is set to the number of elements
* to the rth power.
* | new.getTotal() == BigInteger.valueOf(elements.length).pow(r)
* @post The number of variations left is set to the total number.
* | new.getNumLeft() == new.getTotal()
*/
public VariatorWithRepetition(T[] elements, int r) {
super(elements, r);
}

/**
* Initialise the array of indices. For variations with repetition, it
* needs to be initialised with all 0s
*/
@Override
protected void initialiseIndices() {
Arrays.fill(indices, 0);
}

/**
* Compute the total number of elements to return.
*
* @see CombinatoricOperator#initialiseTotal()
*/
@Override
protected BigInteger initialiseTotal(int n, int r) {
return BigInteger.valueOf(n).pow(r);
}

/**
* Compute the next array of indices.
*
* @see CombinatoricOperator#computeNext()
*/
@Override
protected void computeNext() {
int i = indices.length - 1;
int n = elements.length;
while (++indices == n && i > 0) {
indices[i--] = 0;
}
}

}

package de.uni_tuebingen.sfb.macke;
/*
* PermuterTest.java
*
* Created on 3-mrt-2006
*
* Copyright (C) 2006 Hendrik Maryns <[email protected]>.
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA.
*/

import de.uni_tuebingen.sfb.macke.utilities.*;

import java.util.Arrays;

/**
* A class for testing the combinatoric operators.
*
* @author <a href="mailto:[email protected]">Hendrik
Maryns</a>
*/
public class PermuterTest {

/**
*
*
* @param args
*/
public static void main(String args[]) {
final Integer[] data = new Integer[3];
for (int i = 0; i < data.length; i++) {
data = i;
}
for (Integer[] variation : new Permuter<Integer>(data)) {
System.out.println(Arrays.toString(variation));
}
System.out.println();
for (int i = 0; i <= data.length; i++) {
for (Integer[] combination : new Combinator<Integer>(data, i)) {
System.out.println(Arrays.toString(combination));
}
}
System.out.println();
for (int i = 0; i <= data.length; i++) {
for (Integer[] variation : new VariatorWithRepetition<Integer>(data,i)) {
System.out.println(Arrays.toString(variation));
}
}
}

}

Cheers, H.

--
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD4DBQFEDZdDe+7xMGD3itQRAoYPAJjOEJ89YjMlajH7xmKJKYa9/Yf+AJ9YepPD
TIOeIktL3WU0T+xU8t4+BQ==
=AI6S
-----END PGP SIGNATURE-----

 

[Roedy Green]

public class Combinator<T> extends CombinatoricOperator<T> {

now included at http://mindprod.com/jgloss/permutation.html
and http://mindprod.com/jgloss/combination.html

Some of your lines were a little long and a newsreader improperly
wrapped them. Other than fixing that, I have left your code identical
to how you posted it.

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Roedy Green schreef:

now included at http://mindprod.com/jgloss/permutation.html
and http://mindprod.com/jgloss/combination.html

Some of your lines were a little long and a newsreader improperly
wrapped them. Other than fixing that, I have left your code identical
to how you posted it.

Waaw. I?m very honored. You might want to remove the few // TODO lines.

Cheers, H.

--
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFEDbyae+7xMGD3itQRAhbeAJ9llehlJr3124tvIkBVly6tLctL4ACfV0YI
90NQudumInyu5TGK3ZY28AU=
=/DWn
-----END PGP SIGNATURE-----

 

[Roedy Green]

Waaw. I?m very honored. You might want to remove the few // TODO lines.

Who knows, perhaps finished code will arrive in the mail like the
story of the shoemaker and elves.

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Roedy Green schreef:

Who knows, perhaps finished code will arrive in the mail like the
story of the shoemaker and elves.

You'll have to clear me up on that one.

H.

--
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFEDsb9e+7xMGD3itQRAsLZAJ0U5Bm7vY+kvOdCwkAaJFxR+McOGwCdGcKb
+kjG+3Ga5aGX4XLwKI/psGg=
=lA2R
-----END PGP SIGNATURE-----

 

[James Snow, Software Developer]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Roedy Green schreef:

You'll have to clear me up on that one.

H.

--
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFEDsb9e+7xMGD3itQRAsLZAJ0U5Bm7vY+kvOdCwkAaJFxR+McOGwCdGcKb
+kjG+3Ga5aGX4XLwKI/psGg=
=lA2R
-----END PGP SIGNATURE-----

streaming.. woooo... those Itialns wrties in senate robes shur is smrtert
thatn the old ultra mortals in the mythy days of ontario.. oohh