 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Java Forum / General / March 2006Strategy or Iterator?
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 NotDashEscaped: You need GnuPG to verify this message Hi, as some of you might have read, I have this little method which computes the cartesian product of a set up to a certain number. Now, of course, this gets rather memory intensive, and I can?t get past about 20^5. So, I will have to use a trick to build the cartesian product, use its values, and discard them again while I am still building it. I see two options: - Not build the whole CP first, but rather build it incrementally. - Give the ?stuff? to be done to the function building the CP. Once again, I see a Lisp construct which sort of does the last, with mapcan and mapcar like stuff, which gets a function as argument, to be executed on each value of a list. In Java, this is a candidate for the Strategy pattern: make a class which does the stuff, and give it as a parameter to the function that builds the CP. Other option: have a separate class that builds the CP and have it return the values incrementally. This sounds like an Iterator: it keeps track of information, and gives the next() if it is asked for it. Which of these both approaches is best for this problem? Does anybody see (dis)advantages to one of those approaches? The Iterator approach fits better into the code I already have, but it is not too late yet to rewrite parts of it. Thanks for some thoughts, H.  SignatureHendrik Maryns ================== www.lieverleven.be http://aouw.org > as some of you might have read, I have this little method which > computes the cartesian product of a set up to a certain number. Now, [quoted text clipped - 13 lines] > which does the stuff, and give it as a parameter to the function that > builds the CP. Dunno whether this is actually Strategy Pattern but that's what I'd most likely do. Note, I'd doing quite a lot of Ruby and there we have anonymous callbacks which fit perfect into the picture: here's how a Ruby version probably would look like: def cartesian(set_a, set_b) set_a.each {|a| set_b.each {|b| yield a,b}} end catesian mySet, mySet do |x,y| # do whatever you have to do with x and y end In Java you'd have to define an interface for the block. And of course you might want to encapsulate the whole thing in a class. HTH Kind regards robert > In Java, this is a candidate for the Strategy pattern: make a class > which does the stuff, and give it as a parameter to the function that [quoted text clipped - 3 lines] > return the values incrementally. This sounds like an Iterator: it keeps > track of information, and gives the next() if it is asked for it. This is the choice between an internal or external iterator. I.e. the choice between telling some object (internal iteration): This is what I want done. Do it for every element in the sequence. and (external iteration): If you haven't run out, then give me the next element in the sequence. I don't think there's much to choose between them myself. External iteration is probably somewhat clearer in Java than internal (just because of the way that Java works, it wouldn't necessarily be true in other languages). Also you can implement internal iteration easily and efficiently on top of external, but the reverse is not true (in a language without coroutines). Counter to that, if you use external iteration, then you may have to introduce a new kind of object to hold the elements of the sequence rather than being able to pass the compound data explicitly as multiple arguments to the "operation" object. Another reason why external iteration might not be so good is if the algorithm for producing the elements of the sequence is naturally recursive, then it may be a pain to convert that to an iterative form. -- chris -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 NotDashEscaped: You need GnuPG to verify this message Chris Uppal schreef: >> In Java, this is a candidate for the Strategy pattern: make a class >> which does the stuff, and give it as a parameter to the function that [quoted text clipped - 26 lines] > is if the algorithm for producing the elements of the sequence is naturally > recursive, then it may be a pain to convert that to an iterative form. If I understand correctly, you say: use external, except when the inherent recursiveness of the problem forces you to do it internal? I?m afraid that could be the case, ah well... Thanks, H. SignatureHendrik Maryns ================== www.lieverleven.be http://aouw.org > If I understand correctly, you say: use external, except when the > inherent recursiveness of the problem forces you to do it internal? That sounds like a reasonable summary ;-) > I?m afraid that could be the case, ah well... If what you are doing is processing all possible N-tuples of elements choosen from a fixed list. E.g: A A A A A B A A C A A D A B A ... D D C D D D 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. -- chris On Thu, 2 Mar 2006 16:06:01 -0000, "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> 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 SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching. -----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@metagnostic.REMOVE-THIS.org> wrote, quoted or indirectly [quoted text clipped - 6 lines] > 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@sfs.uni-tuebingen.de>. * * 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@uni-tuebingen.de">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. SignatureHendrik Maryns ================== www.lieverleven.be http://aouw.org > /** > * The number of permutations to go. > */ > private int count; Note that using an int to hold the size of the output stream (N factorial) will limit you to inputs with no more than 12 elements. If you used a long, then you could get up to 20. If you want more, then you'll have to switch to counting with BigIntegers, or use a different technique to detect the end of the sequence. > * Permuter.java Another point, do you actually want the /permutations/ ? I though you wanted to iterate over the tuples defined by the Cartesian product of a set (or list) with itself R times. For instance, if the input is { A B C } and R is 2, then that sequence would be: A A A B A C B A B B B C C A C B C C Dijkstra's algorithm generates permutations, which is a different concept. Note that there is no R that you can set in his algorithm (and the way the algorithm works makes it impossible to add an R parameter, you have to take a completely different approach). Dijkstra's algorithm would give (in some order): A B C A C B B A C B C A C A B C B A FWIW, there are at least 5 different kinds of combination/permutation-like sequences one can derive from an input list of size N. We can generate: All possible subsets of size R of the input (itself considered to be a Set), i.e. not caring about the ordering. R must be <= N. Usually called the "combinations" of the input. There are N choose R (nCr) outputs. All possible subsequences of length N of the input (considered to be a list), preserving the ordering of the elements in the input. R must be <= N. There are nCr outputs (there are algorithms which can be used for both this and combinations). All possible tuples of R elements taken from the input. Duplications are allowed. (The case illustrated above). R may be > N. There are N**R outputs. All possible re-orderings of the input. The R parameter is not meaningful. Usually called the "permutations" of the input. This is what Dijkstra's algorithm produces. There are N! outputs. All possible subsequences of length R of the input, subsequences are considered to be different if the elements occur in different orders. R may be > N. There are N perm R (nPr) outputs. They can all be computed by external iterators. The first three can be implemented easily; permutations requires something like Dijkstra's algorithm; the last is a bit of a bugger to do elegantly (you can do it inelegantly by applying Dijkstra to each R-combination in turn). -- chris -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 NotDashEscaped: You need GnuPG to verify this message Chris Uppal schreef: >> /** >> * The number of permutations to go. [quoted text clipped - 6 lines] > counting with BigIntegers, or use a different technique to detect the end of > the sequence. You?re right, I already changed that. >> * Permuter.java > > Another point, do you actually want the /permutations/ ? I though you wanted > to iterate over the tuples defined by the Cartesian product of a set (or list) > with itself R times. Again, you?re right. I am working on a similar class that gives me combinations of a certain length instead of permutations, based on a similar class I found on the net. But I trust that the Permuter class will be useful too. Didn?t want to keep it for myself, you know... > FWIW, there are at least 5 different kinds of combination/permutation-like > sequences one can derive from an input list of size N. We can generate: [quoted text clipped - 31 lines] > the last is a bit of a bugger to do elegantly (you can do it inelegantly by > applying Dijkstra to each R-combination in turn). Thanks, you?re right, I need the third option, indeed. I don?t really see what you mean by the last one, though. I really should do some more thinking before I happily start hacking (thought that last is more fun, of course). I will apply the same frame to make some iterator classes doing this stuff. Thanks a lot. H. SignatureHendrik Maryns ================== www.lieverleven.be http://aouw.org [me:] > > All possible subsequences of length R of the input, subsequences > > are considered to be different if the elements occur in different > > orders. R may be > N. > > There are N perm R (nPr) outputs. [...] > I don?t really see what you mean by the last one, though. 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. -- chris [*] I assume that's the best strategy for Scrabble, I don't play the game myself. >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[*]. [quoted text clipped - 3 lines] >Say you consider 5-letter words: that's my last kind of >"permutation" -- what I call permutations of length 5. In German, this is called a »Variation ohne Zurücklegen« (358 Google hits). I believe that the English translation is »variation without repetition«, but this has only 19 Google hits. >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[*]. [quoted text clipped - 3 lines] >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. First, the output for three letters "T", "H", and "E": [ T ] [ H ] [ E ] [ T H ] [ H T ] [ T E ] [ E T ] [ H E ] [ E H ] [ T H E ] [ T E H ] [ H T E ] [ H E T ] [ E T H ] [ E H T ] Then, the source code: public class Main { public static void main( final java.lang.String[] args ) { java.lang.Object[] hand = new java.lang.Object[]{ "T", "H", "E" }; for( int i = 1; i <= hand.length; ++i ) for( java.lang.Object[] j : new Combinations( i, hand )) for( java.lang.Object[] k : new Permutations( j )) arrayPrint( k ); } public static void arrayPrint( final java.lang.Object[] array ) { java.lang.System.out.print( "[ " ); for( int i = 0; i < array.length; ++i ) { java.lang.System.out.print( array[ i ] + " " ); } java.lang.System.out.print( "]\n" ); }} class Permutations implements java.lang.Iterable<java.lang.Object[]>, java.util.Iterator<java.lang.Object[]> { public final java.lang.Object[] zzBase; public final int zzLength; public final int[] zzC; public final java.lang.Object[] zzResult; public boolean zzHasNext = true; static void swap( final int array[], final int i, final int j ) { final int tmp = array[ i ]; array[ i ]= array[ j ]; array[ j ]= tmp; } public Permutations ( final java.lang.Object[] base ) { this.zzBase = base; this.zzLength = this.zzBase.length; this.zzResult = new java.lang.Object[ this.zzLength ]; zzC = new int[ this.zzLength ]; for( int i = 0; i < this.zzLength; ++i )zzC[ i ]= i; } public final boolean hasNext(){ return this.zzHasNext; } public void copyToResult() { for( int i = 0; i < this.zzLength; ++i ) this.zzResult[ i ]=this.zzBase[ this.zzC[ i ]]; } 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; } 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; l = this.zzLength; while( k < l ){ swap( this.zzC, k - 1, l - 1 ); ++k; --l; }}} return this.zzResult; } public void remove() { throw new java.lang.UnsupportedOperationException(); } public java.util.Iterator<java.lang.Object[]> iterator(){ return this; }} class Combinations implements java.lang.Iterable<java.lang.Object[]>, java.util.Iterator<java.lang.Object[]> { public final int zzSize; public final java.lang.Object[] zzBase; public final int zzLength; public final int[] zzC; public final java.lang.Object[] zzResult; public boolean zzHasNext = true; public Combinations ( final int size, final java.lang.Object[] base ) { this.zzSize = size; assert this.zzSize >= 0; this.zzBase = base; this.zzLength = this.zzBase.length; assert this.zzLength >= this.zzSize; this.zzResult = new java.lang.Object[ this.zzSize ]; zzC = new int[ this.zzSize + 3 ]; { int j; for( j = 1; j <= this.zzSize; ++j )zzC[ j ]= j - 1; zzC[ this.zzSize + 1 ]= this.zzLength; zzC[ this.zzSize + 2 ]= 0; } advance(); } public final boolean hasNext(){ return this.zzHasNext; } public void advance() { for( int i = 1; i <= this.zzSize; ++i ) this.zzResult[ i - 1 ]=this.zzBase[ this.zzC[ i ]]; } public final java.lang.Object[] next() { advance(); if( this.zzHasNext ) { int j; { for( j = 1; this.zzC[ j ]+ 1 == this.zzC[ j + 1 ]; ++j ) this.zzC[ j ]= j - 1; } if( j > this.zzSize ){ this.zzHasNext = false; } else{ this.zzC[ j ]= this.zzC[ j ]+ 1; }} else { throw new java.util.NoSuchElementException(); } return this.zzResult; } public void remove() { throw new java.lang.UnsupportedOperationException(); } public java.util.Iterator<java.lang.Object[]> iterator(){ return this; }} -----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[*]. [quoted text clipped - 9 lines] > combinator in my library, which can combine them to a new > iterator, but for this post I will use nested loops. <snip> > 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. SignatureHendrik Maryns ================== www.lieverleven.be http://aouw.org > [*] I assume that's the best strategy for Scrabble, I don't play the > game > myself. Well, it makes a good example for the topic of discussion, but, there are very often times in Scrabble that you would strategically avoid playing a letter in order to keep it out of play, or to save it for a more advantageous play. Practically any time you see an opportunity to play all seven of your letters in one turn, you should certainly consider it, but there are several other compelling strategic considerations, especially, point value of the board, and also, what opportunities you're giving to the next player. Experienced scrabble players can make the game almost as brutal as backgammon. On Sun, 05 Mar 2006 15:15:18 -0700, James McGill <jmcgill@cs.arizona.edu> wrote, quoted or indirectly quoted someone who said : >Experienced scrabble players can make the game almost as brutal as >backgammon. It is like croquet. The most genteel people turn cutthroat with sufficient exposure. SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching. > On Sun, 05 Mar 2006 15:15:18 -0700, James McGill > <jmcgill@cs.arizona.edu> wrote, quoted or indirectly quoted someone [quoted text clipped - 5 lines] > 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. Signaturewww.EdmundKirwan.com - Home of The Fractal Class Composition. Download Fractality, free Java code analyzer: www.EdmundKirwan.com/servlet/fractal/frac-page130.html [me:] > > [*] I assume that's the best strategy for Scrabble, I don't play the > > game [quoted text clipped - 4 lines] > playing a letter in order to keep it out of play, or to save it for a > more advantageous play. Aha! Thanks. > Experienced scrabble players can make the game almost as brutal as > backgammon. <grin/> -- chris On Fri, 03 Mar 2006 14:47:43 +0100, Hendrik Maryns <hendrik_maryns@despammed.com> wrote, quoted or indirectly quoted someone who said : >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. Do you want me to add your code of the permutations entry? SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching. -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 NotDashEscaped: You need GnuPG to verify this message Roedy Green schreef: > On Fri, 03 Mar 2006 14:47:43 +0100, Hendrik Maryns > <hendrik_maryns@despammed.com> wrote, quoted or indirectly quoted [quoted text clipped - 6 lines] > > 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:hendrik.maryns@uni-tuebingen.de">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 = 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[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; } /** * 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] = 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:hendrik.maryns@uni-tuebingen.de">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] = 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[i] == n - r + i) { i--; } a[i] = a[i] + 1; for (int j = i + 1; j < r; j++) { a[j] = a[i] + 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[i] == elements[a[i]] */ @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[i] = elements[indices[i]]; } 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] = 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. SignatureHendrik Maryns ================== www.lieverleven.be http://aouw.org -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 NotDashEscaped: You need GnuPG to verify this message Hendrik Maryns schreef: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 [quoted text clipped - 25 lines] > > 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 <hendrik@sfs.uni-tuebingen.de>. * * 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:hendrik.maryns@uni-tuebingen.de">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] = 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[i] == elements[indexes[i]] */ @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[i] = elements[indexes[i]]; } 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 <hendrik@sfs.uni-tuebingen.de>. * * 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:hendrik.maryns@uni-tuebingen.de">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[i] == n - r + i) { i--; } indices[i] = indices[i] + 1; for (int j = i + 1; j < r; j++) { indices[j] = indices[i] + j - i; } // TODO: understand this. } } /* * Permuter.java * * Created on 3-mar-2006, based on Permutations from Tim Tyler. * * Copyright (C) 2005 Hendrik Maryns <hendrik@sfs.uni-tuebingen.de>. * * 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:hendrik.maryns@uni-tuebingen.de">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 = 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[b] * | new.indexes[b] = indexes[a] */ private void swap(int a, int b) { int temp = indices[a]; indices[a] = indices[b]; indices[b] = temp; } } /* * VariatorWithRepetition.java * * Created on 7-mrt-2006 * * Copyright (C) 2006 Hendrik Maryns <hendrik@sfs.uni-tuebingen.de>. * * 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:hendrik.maryns@uni-tuebingen.de">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[i] == n && i > 0) { indices[i--] = 0; } } } package de.uni_tuebingen.sfb.macke; /* * PermuterTest.java * * Created on 3-mrt-2006 * * Copyright (C) 2006 Hendrik Maryns <hendrik@sfs.uni-tuebingen.de>. * * 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:hendrik.maryns@uni-tuebingen.de">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] = 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. SignatureHendrik Maryns ================== www.lieverleven.be http://aouw.org On Tue, 07 Mar 2006 15:22:59 +0100, Hendrik Maryns <hendrik_maryns@despammed.com> wrote, quoted or indirectly quoted someone who said : >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. SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching. -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 NotDashEscaped: You need GnuPG to verify this message Roedy Green schreef: > On Tue, 07 Mar 2006 15:22:59 +0100, Hendrik Maryns > <hendrik_maryns@despammed.com> wrote, quoted or indirectly quoted [quoted text clipped - 8 lines] > 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. SignatureHendrik Maryns ================== www.lieverleven.be http://aouw.org On Tue, 07 Mar 2006 18:02:18 +0100, Hendrik Maryns <hendrik_maryns@despammed.com> wrote, quoted or indirectly quoted someone who said : >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. SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching. -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 NotDashEscaped: You need GnuPG to verify this message Roedy Green schreef: > On Tue, 07 Mar 2006 18:02:18 +0100, Hendrik Maryns > <hendrik_maryns@despammed.com> wrote, quoted or indirectly quoted [quoted text clipped - 3 lines] > 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. SignatureHendrik Maryns ================== www.lieverleven.be http://aouw.org > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 [quoted text clipped - 26 lines] > =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 >as some of you might have read, I have this little method which computes >the cartesian product of a set up to a certain number. Now, of course, [quoted text clipped - 4 lines] >return the values incrementally. This sounds like an Iterator: it keeps >track of information, and gives the next() if it is asked for it. First, I show a simple numeric range iteration: for( java.lang.Integer i : new de.dclj.ram.system.iteration.IntegralRange( 10, 12 )) java.lang.System.out.println( i ); 10 11 12 Next, I show how to build the cartesian product of two iterations, which does not need memory to store all parts at the same time. It does not even store all the value of the inner iteration. So both ranges might be large without exceeding memory limits (the second value for now must be less than java.lang.Integer.MAX_VALU). for( de.dclj.ram.type.tuple.DefaultComparableTuple i : new de.dclj.ram.system.iteration.TupleNesting <java.lang.Integer,java.lang.Integer> ( new de.dclj.ram.system.iteration.IntegralRange( 1, 3 ), new de.dclj.ram.system.iteration.IntegralRange( 100, 102 ))) java.lang.System.out.println( i ); ( 1; 100 ) ( 1; 101 ) ( 1; 102 ) ( 2; 100 ) ( 2; 101 ) ( 2; 102 ) ( 3; 100 ) ( 3; 101 ) ( 3; 102 ) The complete program is public class Main { public static void main( final java.lang.String[] args ) { for( java.lang.Integer i : new de.dclj.ram.system.iteration.IntegralRange( 10, 12 )) java.lang.System.out.println( i ); for( de.dclj.ram.type.tuple.DefaultComparableTuple i : new de.dclj.ram.system.iteration.TupleNesting <java.lang.Integer,java.lang.Integer> ( new de.dclj.ram.system.iteration.IntegralRange( 1, 3 ), new de.dclj.ram.system.iteration.IntegralRange( 100, 102 ))) java.lang.System.out.println( i ); }} You'd need ram.jar to actually compile and run this: http://www.purl.org/stefan_ram/pub/ram-jar This is the distribution version not identical to my internal version, but I hope that all classes needed for the above program are included. -- The library is »pre-alpha« (not stable, not documented, and not tested). > public class Main > { public static void main( final java.lang.String[] args ) [quoted text clipped - 7 lines] > new de.dclj.ram.system.iteration.IntegralRange( 100, 102 ))) > java.lang.System.out.println( i ); }} Stefan, I had assumed that you used that highly compressed format, as an "optimisation" for posts here. But I see you use it for real code too. It's not a style I've encountered anywhere else (although it's not dissimilar to Kent Beck's suggested Smalltalk style. I'd interested to know where it comes from ? On a somewhat related note. How you format your own code is quite definitely your own affair, but you may not be aware that at least some people (or at least one person ;-) find it totally unreadable. I'm not suggesting you change (and I'm certainly not going increase the risk of starting another fruitless layout thread by mentioning any other layouts), but I am curious about this one -- where it came from and why you prefer it. -- chris >Stefan, I had assumed that you used that highly compressed >format, as an "optimisation" for posts here. But I see you use >it for real code too. Actually, I do /not/ (always). For an example, see http://www.purl.org/stefan_ram/java/de/dclj/ram/system/iteration/TupleNesting.java This code was formatted using an automatic "Java reformatter" so as to look more like the code most Java programmers prefer. This was done so, in order to help programmers to read my code. The distributed source within my open source library »ram.jar« was also reformatted using a reformatted with default settings. I internally still write and edit the code in my preferred formatting and filter it through a reformatter in order to publish as part of ram.jar. I also would not mind applying such a reformatter to my usenet postings or other web pages, but right now, this would take to much time. However, the creation of the library distribution is automated and therefore, it was not a problem to include this reformatting step. >It's not a style I've encountered anywhere else (although it's >not dissimilar to Kent Beck's suggested Smalltalk style. I'd >interested to know where it comes from ? I am not aware of someone with exactly the same style, but I assume that I might have read something in this style a long time ago and then have adopted it. It is the most natural way to me, but if others do not see it this way, I need to explain: Indentation within Braces An indentation of just one space often is too small to be seen clearly, because the natural width and form of characters often varies by an amount that is not very much smaller than a space. Therefore, the indentation should amount to at least two positions. In order not to waste horizontal spaces, an indentation of exactly two positions is chosen. This means, that the left position of the next level is two larger than the position of the directly enclosing level. Indentation by two positions within a block { ++x; ++x; } ^ ^ 0 2 Bad A small indentation by one position is not always visible clearly {++x; ++x; } Good The indentation by two positions is visible clearly { ++x; ++x; } Bad A large indentation by more than two positions wastes horizontal space with no additional benefit { ++x; ++x; } Spaces within braces In mathematics, there are often no spaces at the inner side of parentheses or braces in expressions, but spaces are used indeed at the inner side of braces in set notation, when the braces contain a description (not when they contain a list). Spaces in set notation { x | x > 2 } This style is adopted here: One space is written at the inner side of braces. Spaces at the inner side of parentheses within a block { ++x; } This style is consistent with the indentation by two positions, because only using this style, corresponding parts of two lines have the same position. Bad No space after the first brace, the two statements are misaligned {++x; ++x; } Good One space after the first brace, the two statements are properly aligned { ++x; ++x; } Bad Two spaces after the first brace, the two statements are misaligned { ++x; ++x; } There are some exceptions to this rule: No spaces are used within empty braces "{}" and between two or more closing braces of the same direction "}}", except, when the first one of them is part of an empty pair "{} }" (an empty pair of braces if treated like a single non-braces character). Unified rules for all Brackets For simplicity and uniformity, the rules from above apply to all kinds of brackets, including parentheses, braces (curly brackets), square brackets, and angle brackets. Spaces within parentheses and square brackets { y = f( x )+ g() + a[ 2 ]; } Binary operators are surrounded by a space, but the space is omitted, when there already is a space on the other side of a sequence of bracket directly beside the operator: By this rule " )+" is written instead of " ) +". Representation of the Syntactical Structure A method declaration in Java consists of a head and a body. The following representation shows this structure: Good formatting according to the structure void alpha() // head { beta(); } // body The following formatting is misleading, because the line break does not match the structural break: Bad line break within the body void alpha() { // head and the beginning of the body beta(); } // the rest of the body This formatting also would make no sense for blocks within blocks. So it is often not used for such blocks. Therefore even the adopters of this style can not use it uniformly. Left Braces Look Like "bullets" There is a well known style to publish lists in typography using bullets sticking out on the left, looking like this: Common list representation with bullets in typography o This is the first point of this list, it is written here just as an example. o Here is another entry o This is another example given just as an example to show an example The braces of the beginnings of blocks stand out on the left just the same, when the formatting being described here is used, so they look quite naturally as beginning-of-a-block markers, when one is used to the typographical list notation: Left braces look like bullets to mark blocks { printf(); printf(); printf(); printf(); printf(); printf(); printf(); } { printf(); printf(); } { printf(); printf(); printf(); printf(); printf(); printf(); } Neutrality Someone wrote this C code: Code someone wrote while( fgets( eingabe, sizeof eingabe, stdin )) if( sscanf( eingabe, "%d", &wert )!= 1 ) fprintf( stderr, "Please enter a number!\n" ); else summe += wert; It amazes me that I can add braces by my style conventions without the need to change the position of any character of the given code: The code from above plus braces while( fgets( eingabe, sizeof eingabe, stdin )) { if( sscanf( eingabe, "%d", &wert )!= 1 ) { fprintf( stderr, "Please enter a number!\n" ); } else { summe += wert; }} ~~ Some of my rules regarding "microformatting" (regarding spaces around operators and so) are being described on http://www.purl.org/stefan_ram/pub/c_format_en But this web page does not include a rationale. > It is the most natural way to me, but if others do not > see it this way, I need to explain: Thanks. -- chris Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
Reply to this Message
|
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2008 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.