Re: how to use recursive algorithm to determine all of the arrangements?

The following code is not recursive. There are three files involved:

IndexMapper.java Permutations.java PossibleSets.java

btw, How do I check for overflow on multiplication in Java (or any
other arithmetic operation)?

One aspect I like about this code is that returned items are of same
type as passed in items, that is one can give an array of integers and
get arrays of integers, or one can give strings and get back strings.

Here is IndexMapper:
import java.util.*;
import java.lang.reflect.Array;
class IndexMapper implements Iterator {
private Object map[];
private Iterator it;
private Class type = null;
IndexMapper(Object map[], Iterator indicies) {
this.map = map;
this.it = indicies;
type = map.getClass().getComponentType();
}
public Object next() {
int current[] = (int []) it.next();
Object trans[] = null;
trans = (Object[]) Array.newInstance(type,current.length);

for (int i=0; i<trans.length; i++)
trans[i] = map[current[i]];
return trans;
}
public boolean hasNext() {
return it.hasNext();
}
public void remove() {
it.remove();
}
}

Here is PossibleSets:
import java.util.*;
/**
This class enumerates subsets of arbitrary sets;
The iterator operations are not synchronized.
*/
final public class PossibleSets {
private int n, k;
private Object map[];
public PossibleSets(int from, int choose) {
n = from;
k = choose;
if (n<=0 || k<=0)
throw new IllegalArgumentException(
"Cannot generate sets from zero or negative parameters.");
if (k>n)
throw new IllegalArgumentException(
"Too many elements asked for.");
map = null;
}
public PossibleSets(Object from[], int choose) {
this(from.length,choose);
map = from;
}

public long count() {
long c = 1;
long local_n = n;
long local_k = k;

while (local_k > 0)
{
c = c * local_n;
if (c < 0)
throw new IllegalArgumentException("Number too large.");
--local_n;
--local_k;
}
local_k = k;
while (local_k > 0)
{
c = c / local_k;
--local_k;
}

return c;
}

public Iterator iterator() {
if (map == null)
return new Provider(n,k);
else
return new IndexMapper(map, new Provider(n,k));
}
private class Provider implements Iterator {
private int set[];
private boolean primedWithAValue = false;
/** @return int [] */
public Object next() {
if (! primedWithAValue)
throw new NoSuchElementException("No more sets to access.");
int returnSet[] = new int[k];
for (int i=0;i<k;i++)
returnSet[i] = set[i];
prepareForCalls();
return returnSet;
}
public boolean hasNext() {
return primedWithAValue;
}
Provider(int n, int k) {
set = new int[k];
for (int i=0; i<k; i++) {
set[i] = i;
}
primedWithAValue = true;
}

private void prepareForCalls() {
if ( thereAreMorePossibleSets() )
{
primedWithAValue = true;
}
else
{
primedWithAValue = false;
}
}
private boolean thereAreMorePossibleSets() {
// generate next combination in lexicographical order
int i = k - 1; // start at last item

while (i>=0 && set[i] == (n - k + i)) // find next item to
increment
--i;

if (i < 0) return false;
++set[i];

for (int j = i + 1; j < k; j++)
set[j] = set[i] + j - i;
return true;
}
public void remove() { throw new UnsupportedOperationException(); }
}
static private ArrayList arrayOfIntegers(Object o) {
int a[] = (int []) o;
ArrayList al = new ArrayList();
for (int i=0; i<a.length; i++)
al.add(new Integer(a[i]));
return al;
}
static public void main(String args[]) {
PossibleSets s = new PossibleSets(new Integer(args[0]).intValue(),
new Integer(args[1]).intValue());
System.out.println("setcounts="+s.count());
for (Iterator it=s.iterator(); it.hasNext(); )
System.out.println("next="+arrayOfIntegers(it.next()));
}
}


Here is Permutations:
import java.util.*;
final public class Permutations {
private int n, k;
private Object map[];
public Permutations(int from, int choose) {
n = from;
k = choose;
if (n<=0 || k<=0)
throw new IllegalArgumentException("Cannot generate permutations
from zero or negative parameters.");
if (k>n)
throw new IllegalArgumentException("Too many elements asked
for.");
map = null;
}
public Permutations(Object o[], int choose) {
this(o.length,choose);
map = o;
}
public long count() {
long c = 1;
long local_n = n;
long local_k = k;

while (local_k > 0)
{
c = c * local_n;
if (c<0)
throw new IllegalArgumentException("Number too large.");
--local_n;
--local_k;
}

return c;
}

public Iterator iterator() {
if (map == null)
return new Provider(n,k);
else
return new IndexMapper(map, new Provider(n,k));
}
private class Provider implements Iterator {
private int perm[];
private boolean primedWithAValue = false;
private Iterator sets = null;
/** @return int [] */
public Object next() {
if (! primedWithAValue)
throw new NoSuchElementException("No more permutations to
access.");
int returnPerm[] = new int[k];
for (int i=0; i<k; i++)
returnPerm[i]=perm[i];
prepareForCalls();
return returnPerm;
}
public boolean hasNext() {
return primedWithAValue;
}
Provider(int n, int k) {
sets = new PossibleSets(n,k).iterator();
perm = (int []) sets.next();
primedWithAValue = true;
}

private void prepareForCalls() {
if ( thereAreMorePermutationsInCurrentSet() )
{
int i = k - 1;
while (perm[i-1] >= perm[i])
i--;
int j = k;
while (perm[j-1] <= perm[i-1])
j--;

swap(i - 1, j - 1);

i++;
j = k;

while (i < j)
{
swap(i - 1, j - 1);
i++;
j--;
}
primedWithAValue = true;
}
else if (thereAreMoreSets())
{
perm = (int[]) sets.next();
primedWithAValue = true;
}
else
{
primedWithAValue = false;
}
}
private void swap(int a, int b)
{
int temp = perm[a];
perm[a] = perm[b];
perm[b] = temp;
}
private boolean thereAreMorePermutationsInCurrentSet() {
int i = k - 1;
while (i>=1 && (perm[i-1] >= perm[i]))
i--;

return i >= 1;
}
private boolean thereAreMoreSets() {
return sets.hasNext();
}
public void remove() { throw new UnsupportedOperationException(); }
}


static private ArrayList arrayOfIntegers(Object o) {
int a[] = (int []) o;
ArrayList al = new ArrayList();
for (int i=0; i<a.length; i++)
al.add(new Integer(a[i]));
return al;
}
static public void main(String args[]) {
Permutations p = new Permutations(new Integer(args[0]).intValue(),
new Integer(args[1]).intValue());
System.out.println("permcounts="+p.count());
for (Iterator it=p.iterator(); it.hasNext(); )
System.out.println("next="+arrayOfIntegers(it.next()));
}
}

.

Relevant Pages

  • Law of Demeter, am I doing it right?
    ... int getPrice() const ... iterator begin ... const_iterator beginconst ...
    (comp.object)
  • Iterator in a particular order
    ... (control_id int, control_name varchar(50)) ... I have 2 classes Form and Control. ... private String formName; ... Then I issue an iterator on it and loop ...
    (comp.lang.java.help)
  • poker odds
    ... public static final int HIGH_CARD = 0; ... private static Logger logger; ... public Poker(int numCard, Card deck) ... public void maxSimulation ...
    (comp.lang.java.programmer)
  • problem with vmr9 image compositor - method Draw
    ... I play video with playlist, if i play video about 5x it is ... but so 6round of video playing throw exception int ... private void ConfigureVMR9InWindowlessMode() ... Surface renderTarget = new Surface; ...
    (microsoft.public.win32.programmer.directx.managed)
  • Re: using ref keyword performance
    ... // private fields... ... int valueCount = values.Length; ... static void TestWithRefLoop() ...
    (microsoft.public.dotnet.languages.csharp)