Re: Strategy or Iterator?



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

Roedy Green schreef:
On Thu, 2 Mar 2006 16:06:01 -0000, "Chris Uppal"
<chris.uppal@xxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote, quoted or indirectly
quoted someone who said :

then that's pretty easy to generate in an external iterator, using an int[N]
helper array. It's harder to describe in words than to code ;-) So I'll post
code if that's any help.

see http://mindprod.com/jgloss/permutation.html
http://mindprod.com/jgloss/combination.html

Many thanks again, Roedy! Your FAQ is really inexhaustible! I took the
Dijkstra Algorithm from the applet you linked to (though it is very
badly written IMHO), and turned it into a generic iterator class, which
allows for external iteration.

It isn?t perfect yet, but this is what resulted:

/*
* Permuter.java
*
* Created on 3-mar-2006, based on Permutations from Tim Tyler, implementing
* the Dijkstra algorithm.
*
* Copyright (C) 2005 Hendrik Maryns <hendrik@xxxxxxxxxxxxxxxxxxxx>.
*
* 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 java.util.Iterator;

/**
* A class that permutes a given array of elements. It can be used
either as an
* external or internal iterator. It implements the Dijkstra algorithm for
* finding permutations in lexicographic order (i.e., if T implements
* Comparable<T> and the elements are supplied in order, then they are
returned
* in lexicographical order). Thanks to Tim Tyler for the
* original implementation {@link http://mandala.co.uk/permutations/}.
*
* @author <a href="mailto:hendrik.maryns@xxxxxxxxxxxxxxxx";>Hendrik
Maryns</a>
* @param <T> The type of the array to be permuted.
*/
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.
*/
public Permuter(T[] elements) {
this.elements = elements.clone();
indexes = new int[elements.length];
initialiseIndexes();
count = factorial(elements.length);
}

/**
* Initialise the array of indexes with growing integers.
*/
private void initialiseIndexes() {
for (int i = 0; i < indexes.length; i++) {
indexes[i] = i;
}
}

/**
* The elements which are permuted.
*/
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 number of permutations to go.
*/
private int 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.
*
* @see java.util.Iterator#next()
*/
public T[] next() {
// a little trick is needed here: for the last call, computeNext may
// not be invoked, or it results in an ArrayIndexOutOfBoundsException.
// At the same time, ensure encapsulation.
T[] result = elements.clone();
count--;
if(hasNext()) {
computeNext();
}
return result;
}

/**
* Compute the next permutation. Algorithm due to Dijkstra, see also
* {@link http://www.cut-the-knot.org/do_you_know/AllPerm.shtml}.
*/
private void computeNext() {
int i = indexes.length - 1;

while (indexes[i - 1] >= indexes[i])
i = i - 1;

int j = indexes.length;

while (indexes[j - 1] <= indexes[i - 1])
j = j - 1;

swap(i - 1, j - 1);

i++;
j = indexes.length;

while (i < j) {
swap(i - 1, j - 1);
i++;
j--;
}
//TODO: understand this
}

/**
* 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[b]
* | new.indexes[b] = indexes[a]
* | new.elements[a] = elements[b]
* | new.elements[b] = elements[a]
*/
private void swap(int a, int b) {
int temp = indexes[a];
indexes[a] = indexes[b];
indexes[b] = temp;

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

/**
* Compute the factorial of n.
*/
private static int factorial(int n) {
int result = 1;
if (n > 1) {
for (int i = 1; i <= n; i++) {
result *= i;
}
}
return result;
}

/**
* 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 returned is smaller than the
* factorial of the size of the element array.
* @see java.util.Iterator#hasNext()
*/
public boolean hasNext() {
return count > 0;
}

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

/**
* Reset the iteration. The iteration restarts with the current
* permutation, i.e., there is no more guarantee about the lexicographic
* order.
*/
public void reset() {
count = factorial(elements.length);
initialiseIndexes();
}

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

}

Thanks and cheers, H.
--
Hendrik Maryns

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

iD8DBQFECEj/e+7xMGD3itQRAvEeAJsEd4VQsnKqytgk17sDDhcLITmJNACbB78o
vOMQZiT/gJatw2rGQscQ8Vc=
=zyKB
-----END PGP SIGNATURE-----
.



Relevant Pages

  • random number code
    ... Will it really compile exactly the same as mingw compiler used ... // initialization of static private members ... MSBs of the seed affect only MSBs of the array ... // constructor with 32 bit int as seed ...
    (comp.lang.cpp)
  • Re: N Things taken M at a time
    ... you're right about N^Q permutations. ... private boolean inc ... public Array(final int l, final java.lang.Objectarg) ...
    (comp.lang.java.programmer)
  • Re: Strategy or Iterator?
    ... Do you want me to add your code of the permutations entry? ... A class that permutes a given array of elements. ... private int[] indexes; ... private BigInteger total; ...
    (comp.lang.java.programmer)
  • Arrays!
    ... two dimensional array in my constructor of my class. ... array in the private area of the class I get an error. ... int TABLES::GetT2Value ...
    (microsoft.public.vc.language)
  • Re: sizeof() headaches
    ... > int main ... void SetArray(const string * array) ... ...tells the world SetArrayisn't going to be modifying 'SomeStringArray'. ... Often you'll find it better to have some private ...
    (alt.comp.lang.learn.c-cpp)