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

Discussion in 'Java' started by index, May 3, 2006.

  1. index

    index Guest

    suppose there are n elements,how can you use recursive algorithm to
    determine all of the n elements' arrangements.
    for example,if there is 1 element,say, A1,there is only one
    arrangement, namely,{A1};
    if there are 2 elements,say,A1 and A2,there are two
    arrangements,namely, {A1,A2},{A2,A1};
    3 elements, A1,A2 and A3, six arrangements
    exist,{A1,A2,A3},{A2,A1,A3},{A3,A1,A2},{A3,A2,A1},{A1,A3,A2},{A2,A3,A1};
    .......
    so if there are n elements, how can we use recursive algorithm to
    determine all of these arrangements?
     
    index, May 3, 2006
    #1
    1. Advertising

  2. index

    index Guest

    of course We know that there are n! permutations of n elements,but i
    just want to make a program to print what does every permutation look
    like,like
    this,{A1,A2,A3},{A2,A1,A3},{A3,A1,A2},{A3,A2,A1},{A1,A3,A2},{A2,A3,A1}.
    can anyone give me some tips?
     
    index, May 3, 2006
    #2
    1. Advertising

  3. index

    James McGill Guest

    Graphics2D rotation

    I'm stumped on this one. I draw a circular figure in my panel, with the
    midpoint of the circle being (radius, radius). Then I want to draw
    another circle over it in another layered pane, but rotated with respect
    to the midpoint of the circles, not with respect to the panel.

    I've tried lots and lots of combinations of translate and rotate, but I
    just can't figure out what to do to make this happen. How do you rotate
    a circle with respect to its midpoint?
     
    James McGill, May 3, 2006
    #3
  4. index

    Rhino Guest

    Re: Graphics2D rotation

    "James McGill" <> wrote in message
    news:...
    > I'm stumped on this one. I draw a circular figure in my panel, with the
    > midpoint of the circle being (radius, radius). Then I want to draw
    > another circle over it in another layered pane, but rotated with respect
    > to the midpoint of the circles, not with respect to the panel.
    >
    > I've tried lots and lots of combinations of translate and rotate, but I
    > just can't figure out what to do to make this happen. How do you rotate
    > a circle with respect to its midpoint?
    >

    Uhh, how do you tell if it worked? If I draw a circle of radius 5 units
    centered on (0,0), then rotate the circle 90 degrees, how does the second
    circle look any different that the first?

    If this is a homework assignment, maybe you've read it incorrectly??

    --
    Rhino
     
    Rhino, May 3, 2006
    #4
  5. index

    Simon Guest

    index wrote:
    > of course We know that there are n! permutations of n elements,but i
    > just want to make a program to print what does every permutation look
    > like,like
    > this,{A1,A2,A3},{A2,A1,A3},{A3,A1,A2},{A3,A2,A1},{A1,A3,A2},{A2,A3,A1}.
    > can anyone give me some tips?


    Remove the last element An and consider all arrangements for the reduced set.
    Then insert An at every possible position.

    Cheers,
    Simon
     
    Simon, May 3, 2006
    #5
  6. index

    Simon Guest

    Re: Graphics2D rotation

    James McGill wrote:
    > I'm stumped on this one. I draw a circular figure in my panel, with the
    > midpoint of the circle being (radius, radius). Then I want to draw
    > another circle over it in another layered pane, but rotated with respect
    > to the midpoint of the circles, not with respect to the panel.


    I'm not sure about your question, so let me restate it as I understand it. I
    assume that you do not want to rotate the circle itself (because that doesn't
    make much sense) but rather the center of a second object (which is again a
    circle?) with respect to the origin of the first.

    You have a circle at point (r,r) with radius r, i.e., it looks like this:
    (use a fixed width font)

    | o
    | ________/
    | / / \
    |/ / \
    | / |
    r| x |
    | |
    |\ /
    |_\_________/____
    r

    Now you want to draw another figure that is positioned relative to the center of
    the circle at position o given in terms of an angle and a distance d from the
    center x (perhaps you want it on the circumference, i.e., d=r)? Then you can do
    the following:

    1. Translate the graphics context to the center of the circle, i.e. translate(r,r)
    2. Perform your rotation (around the origin which now coincides with the center
    of the circle)
    3. Translate the origin again to move away from the origin by d arriving at "o"
    in the above drawing. (E.g., call translate(d,0).)
    4. Draw the second object.

    Is that what you want to do?

    > I've tried lots and lots of combinations of translate and rotate, but I
    > just can't figure out what to do to make this happen. How do you rotate
    > a circle with respect to its midpoint?

    ^^^^^^^^
    Just to be sure: Maybe your problems are caused by a misunderstaning in the
    usage of Graphics: calling translate() or rotate() or any other method of
    Graphics does not move or rotate the things you have already drawn. You cannot
    translate or rotate the circle but rather the graphics context itself. This has
    an influence only on the objects you draw afterwards.

    Hope this helps,
    Simon
     
    Simon, May 3, 2006
    #6
  7. index

    James McGill Guest

    Re: Graphics2D rotation

    On Wed, 2006-05-03 at 09:59 +0200, Simon wrote:
    > James McGill wrote:
    > > I'm stumped on this one. I draw a circular figure in my panel, with the
    > > midpoint of the circle being (radius, radius). Then I want to draw
    > > another circle over it in another layered pane, but rotated with respect
    > > to the midpoint of the circles, not with respect to the panel.

    >
    > I'm not sure about your question, so let me restate it as I understand it. I
    > assume that you do not want to rotate the circle itself (because that doesn't
    > make much sense) but rather the center of a second object (which is again a
    > circle?) with respect to the origin of the first.


    Thanks for your answer, which already has helped, but let me clarify:

    I make a buffered image for the base layer, which is a circle.
    Then I make another buffered image for the top layer, which is also a
    circle, the same size.

    I want to animate the second image on top of the first, I guess I'd call
    it a "pinwheel" effect. So each timer tick, the top layer should be
    redrawn in its next step of rotation.
    This worked for my purpose:

    ...
    // first translate
    g2.translate(radius, radius);
    // then rotate
    g2.rotate(stepRadians);
    // then translate back
    g2.translate(-radius, -radius);
    g2.drawImage(topLayerImage, 0, 0, this);
    ...


    So I think I have to translate the origin back after rotating becuase
    the image itself is oriented to that space, correct?
     
    James McGill, May 3, 2006
    #7
  8. index

    James McGill Guest

    Re: Graphics2D rotation

    On Wed, 2006-05-03 at 00:25 -0400, Rhino wrote:

    > > I've tried lots and lots of combinations of translate and rotate, but I
    > > just can't figure out what to do to make this happen. How do you rotate
    > > a circle with respect to its midpoint?
    > >

    > Uhh, how do you tell if it worked? If I draw a circle of radius 5 units
    > centered on (0,0), then rotate the circle 90 degrees, how does the second
    > circle look any different that the first?


    It's a circular image with a pattern, not just a circle. I was trying
    to keep my question simple and focused on how to do rotates.

    > If this is a homework assignment, maybe you've read it incorrectly??


    I'm writing a game and I'm fairly new with the Java2D api. I'm just now
    figuring out how to deal with JLayeredPanes. So one of the elements of
    my game is an image on one layer with another moving image on its own
    layer.


    Thanks,

    James
     
    James McGill, May 4, 2006
    #8
  9. index

    Simon Guest

    Re: Graphics2D rotation

    James McGill wrote:
    > I make a buffered image for the base layer, which is a circle.
    > Then I make another buffered image for the top layer, which is also a
    > circle, the same size.
    >
    > I want to animate the second image on top of the first, I guess I'd call
    > it a "pinwheel" effect. So each timer tick, the top layer should be
    > redrawn in its next step of rotation.
    > This worked for my purpose:
    >
    > ...
    > // first translate
    > g2.translate(radius, radius);
    > // then rotate
    > g2.rotate(stepRadians);
    > // then translate back
    > g2.translate(-radius, -radius);
    > g2.drawImage(topLayerImage, 0, 0, this);
    > ...
    >
    >
    > So I think I have to translate the origin back after rotating becuase
    > the image itself is oriented to that space, correct?


    Ok, now I see the problem. You are drawing an image and that does not have the
    center at the "origin" but at the upper left corner. I thought you were drawing
    a Shape which typically has the center at the origin. Therefore, you need the
    second translation. I would assume that your code should actually solve the
    problem, doesn't it?

    One suggestion: Once you are sure about which transformations you need,
    aggregate all of them into a single AffineTransform and apply it once when
    rendering the image. There are also variants of the drawImage methods that
    accept an AffineTransform. Depending on how quickly your wheel rotates and how
    much memory you can affort, it might be even better to generate rotated copies
    of the image in a preprocessing phase so you don't have to perform the time
    consuming rotation for each frame.

    Cheers,
    Simon
     
    Simon, May 4, 2006
    #9
  10. Re: Graphics2D rotation

    James McGill wrote:
    > I make a buffered image for the base layer, which is a circle.
    > Then I make another buffered image for the top layer, which is also a
    > circle, the same size.
    >
    > I want to animate the second image on top of the first,


    I would pre-calculate a set of rotated images. The number of
    pre-calculated images should depend on the desired animation speed, and
    the fps rate with which your game works.

    Once you have them pre-calcualated you just have to select the one
    matching the the current desired wheel position and draw it with a fixed
    x/y offset.

    As a general hint, you are suggesting you are using JLayeredPane to
    construct your animation. This doesn't sound too good. Java games
    typically use multi-buffers, all manged by the game, and flip the
    buffers manually. In your case one would probably compose each frame
    from a fixed background buffer, plus the current animation and then flip
    the buffer.

    /Thomas
    --
    The comp.lang.java.gui FAQ:
    ftp://ftp.cs.uu.nl/pub/NEWS.ANSWERS/computer-lang/java/gui/faq
    http://www.uni-giessen.de/faq/archiv/computer-lang.java.gui.faq/
     
    Thomas Weidenfeller, May 4, 2006
    #10
  11. index

    James McGill Guest

    Re: Graphics2D rotation

    On Thu, 2006-05-04 at 10:03 +0200, Thomas Weidenfeller wrote:
    >
    >
    > As a general hint, you are suggesting you are using JLayeredPane to
    > construct your animation. This doesn't sound too good.


    It's not. I need to move away from Swing/AWT entirely, I think.


    Thanks,

    James.
     
    James McGill, May 4, 2006
    #11
  12. index

    Oliver Wong Guest

    "index" <> wrote in message
    news:...
    > of course We know that there are n! permutations of n elements,but i
    > just want to make a program to print what does every permutation look
    > like,like
    > this,{A1,A2,A3},{A2,A1,A3},{A3,A1,A2},{A3,A2,A1},{A1,A3,A2},{A2,A3,A1}.
    > can anyone give me some tips?
    >


    How would you, as a human being, solve this problem? I.e. how did you
    come up with the above list of 6 elements?

    - Oliver
     
    Oliver Wong, May 8, 2006
    #12
  13. 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 = map[current];
    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 = set;
    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;
    }
    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 == (n - k + i)) // find next item to
    increment
    --i;

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

    for (int j = i + 1; j < k; j++)
    set[j] = set + 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));
    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=perm;
    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--;
    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;
    perm = temp;
    }
    private boolean thereAreMorePermutationsInCurrentSet() {
    int i = k - 1;
    while (i>=1 && (perm[i-1] >= perm))
    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));
    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()));
    }
    }
     
    opalinski from opalpaweb, May 9, 2006
    #13
  14. opalinski from opalpaweb, May 9, 2006
    #14
  15. index

    Chris Uppal Guest

    wrote:

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


    You might find the book mentioned in the class JavaDoc for java.lang.Integer
    intersting.

    -- chris
     
    Chris Uppal, May 9, 2006
    #15
  16. index

    Oliver Wong Guest

    <> wrote in message
    news:...
    >
    > btw, How do I check for overflow on multiplication in Java (or any
    > other arithmetic operation)?


    The simplest way is to check for integer overflow is to do the
    multiplication in floating point precision, and check if the result is
    larger than what would fit in whatever primitive type you're trying to store
    the value in.

    e.g.

    <pseudocode>
    int a, b, result;
    double temp = (double)a * (double)b;
    if (temp > max_int_value) {
    handleOverFlow();
    } else {
    result = (int)temp;
    }
    </pseudocode>

    In the case of int, you could use long instead of double.

    - Oliver
     
    Oliver Wong, May 9, 2006
    #16
  17. Oliver Wong wrote:
    > <> wrote in message
    > news:...
    >
    >>
    >> btw, How do I check for overflow on multiplication in Java (or any
    >> other arithmetic operation)?

    >
    >
    > The simplest way is to check for integer overflow is to do the
    > multiplication in floating point precision, and check if the result is
    > larger than what would fit in whatever primitive type you're trying to
    > store the value in.
    >
    > e.g.
    >
    > <pseudocode>
    > int a, b, result;
    > double temp = (double)a * (double)b;
    > if (temp > max_int_value) {
    > handleOverFlow();
    > } else {
    > result = (int)temp;
    > }
    > </pseudocode>
    >
    > In the case of int, you could use long instead of double.
    >
    > - Oliver


    Note that this should only be used, as written, for int and smaller
    types, not long. It depends on all int values being exactly
    representable as doubles, so that if there is no overflow temp does
    contain the exact answer.

    This program:

    public class TestMult {
    public static void main(String[] args) {
    long a = 0x0fffffffffffffffL;
    long b = 3;
    long result=0;
    double temp = (double)a * (double)b;
    if (temp > Long.MAX_VALUE) {
    handleOverFlow();
    System.exit(3);
    } else {
    result = (long)temp;
    }
    System.out.println("result="+result+" correct answer="+a*b);
    }
    private static void handleOverFlow() {
    System.out.println("Overflow detected");
    }
    }

    prints:

    result=3458764513820540928 correct answer=3458764513820540925

    For long, using BigInteger instead of double would be slower but more
    reliable.

    Patricia
     
    Patricia Shanahan, May 9, 2006
    #17
  18. index

    Chris Uppal Guest

    Patricia Shanahan wrote:

    > Note that this should only be used, as written, for int and smaller
    > types, not long. It depends on all int values being exactly
    > representable as doubles, so that if there is no overflow temp does
    > contain the exact answer.


    I think you can get a lot closer while still staying with the same basic
    approach:

    =============
    private static final double
    fmax = (double)Long.MAX_VALUE,
    fmin = (double)Long.MIN_VALUE;

    public static final long
    multiply(long a, long b)
    throws OverflowException
    {
    double
    floatA = (double)a,
    floatB = (double)b,
    floatC = floatA * floatB;

    if (floatC < fmin
    || floatC > fmax)
    throw new OverflowException("" + floatC);

    return a * b;
    }

    =============

    I don't think that can ever fail to notice an overflow condition, and whenever
    it does return a value that value is correct. I think it can only get it wrong
    (i.e. throw when it doesn't have to) are for values of floatC which are > fmax
    due /only/ to rounding, and similarly at the other end of the range. I'm not
    sure how many such values there are (nor how many floating-point
    multiplications can actually yield them) but an ULP is only 2048 at that range,
    so I don't think there can be many.

    An alternative formulation which is very marginally slower, but which I don't
    think has the false-negative problem at all is:

    =============
    public final long
    multiply(long a, long b)
    throws OverflowException
    {
    long c = a * b;
    double fTrue = (double)a * (double)b;
    double fMaybe = (double)c;

    if (fTrue != fMaybe)
    throw throwable;

    return c;
    }

    =============

    But I'm not really sure whether that is actually correct for all possible
    multiplications...

    -- chris
     
    Chris Uppal, May 9, 2006
    #18
  19. opalinski from opalpaweb, May 11, 2006
    #19
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Alex Vinokur
    Replies:
    2
    Views:
    2,812
    Alex Vinokur
    May 13, 2004
  2. Replies:
    0
    Views:
    3,139
  3. jacksu

    Look for recursive algorithm

    jacksu, Jun 15, 2006, in forum: Java
    Replies:
    11
    Views:
    890
    jacksu
    Jun 16, 2006
  4. n00m
    Replies:
    12
    Views:
    1,122
  5. vamsi
    Replies:
    21
    Views:
    2,113
    Keith Thompson
    Mar 9, 2009
Loading...

Share This Page