Strategy or Iterator?

[Hendrik Maryns]

-----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.
--
Hendrik Maryns

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

iD8DBQFEBtWje+7xMGD3itQRAoqKAJ4gSNt8pP8SrGEWeznvgzARMSR9+wCfXPc6
KGYeHPWPFp+dauwiFBI6Ixk=
=mbJ3
-----END PGP SIGNATURE-----

 

[Robert Klemme]

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.

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

 

[Chris Uppal]

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.

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

 

[Hendrik Maryns]

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

Chris Uppal schreef:

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.

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.
--
Hendrik Maryns

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

iD8DBQFEBuE/e+7xMGD3itQRAkTsAJ9PMtG66XczmmP2okaB8Os/8AT77ACeLhwN
A2sAI49V53TDdHUWO+VfrKM=
=8tu3
-----END PGP SIGNATURE-----

 

[Chris Uppal]

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

 

[Roedy Green]

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

 

[Stefan Ram]

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. (...)
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.

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).

 

[Chris Uppal]

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 ); }}

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

 

[Hendrik Maryns]

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

Roedy Green schreef:

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 <[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 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:[email protected]">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;
}
}

/**
* 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 - 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
* | 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;
}

/**
* 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-----

 

[Stefan Ram]

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.

 

[Chris Uppal]

/**
* 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

 

[Hendrik Maryns]

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

Chris Uppal schreef:

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.

You?re right, I already changed that.

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:

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).

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.

--
Hendrik Maryns

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

iD8DBQFECG0ue+7xMGD3itQRAktKAJ91/gLxbU2ZgGKGYR3Llq5MFcHJTACfa8J/
+pt/zzoYloLy7d37oBD/wVU=
=JMNB
-----END PGP SIGNATURE-----

 

[Chris Uppal]

It is the most natural way to me, but if others do not
see it this way, I need to explain:

Thanks.

-- chris

 

[Roedy Green]

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?

 

[Chris Uppal]

Hendrik Maryns wrote:

[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.

 

[Stefan Ram]

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.

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.

 

[Stefan Ram]

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.

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; }}

 

[James McGill]

[*] 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.

 

[Roedy Green]

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.

 

[Chris Uppal]

James McGill wrote:

[me:]

[*] 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.

Aha! Thanks.

Experienced scrabble players can make the game almost as brutal as
backgammon.

<grin/>

-- chris