Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (539)
Games in Android Showcase (133)
games submitted by our members
Games in WIP (603)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  help with simple recursion  (Read 2252 times)
0 Members and 1 Guest are viewing this topic.
Offline Kommi

Junior Devvie




All opinions will be lined up and shot!


« Posted 2005-04-22 20:02:16 »

The problem: I have the sequence 01234
I need to generate the following permutations of the sequence using recursion.
012
013
014
023
024
034
123
124
134
234

THe other problem is that I have no idea how to do anything recursively besides factorial.


Kommi
Offline Kommi

Junior Devvie




All opinions will be lined up and shot!


« Reply #1 - Posted 2005-04-23 16:35:14 »

any takers? I really need this solved by tomorrow.  Cry

Kommi
Offline kevglass

« JGO Spiffy Duke »


Medals: 212
Projects: 24
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #2 - Posted 2005-04-23 16:36:41 »

What is the pattern? I mean, is there a defined pattern to the numbers?

Doh: you just want the possible 3 digit permitations from 0123?

Kev

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline kevglass

« JGO Spiffy Duke »


Medals: 212
Projects: 24
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #3 - Posted 2005-04-23 16:51:22 »

Here's a way:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
import java.util.ArrayList;


/**
 * Oops. Forgot to document this one.
 *
 * @author Kevin Glass
 */

public class Perms {
      private int[] seq = new int[] {0,1,2,3,4};
      private ArrayList matches = new ArrayList();
     
      public Perms() {
            find(0,1,2);
           
            for (int i=0;i<matches.size();i++) {
                  System.out.println(matches.get(i));
            }
      }
     
      public void find(int a,int b,int c) {
            if ((a >= seq.length) || (b >= seq.length) || (c >= seq.length)) {
                  // invalid leg
                  return;
            }
                 
            String match = seq[a]+""+seq[b]+""+seq[c];
            if (matches.contains(match)) {
                  // already got this one, so don't bother to go any further
                  return;
            }
           
            matches.add(match);
           
            if (c < seq.length-1) {
                  find(a,b,c+1);
            }
            if (b < seq.length-1) {
                  find(a,b+1,b+2);
            }
            if (a < seq.length-1) {
                  find(a+1,a+2,a+3);
            }
      }
     
      public static void main(String[] argv) {
            new Perms();
      }
}


I'm sure there are better ways, far more elegant, this is just a first hack. However, its recursive and does find the sequence.

Kev

Offline ryanm

Senior Devvie


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #4 - Posted 2005-04-23 17:02:44 »

What you wanting is to generate the k-subsets of {0,1,2,3,4}, for k=3.

A google for "java k-subsets", and...

BAM!

With source downloaded from here.

If this is homework, shame on you! You're only cheating yourself. Wink
Offline Kommi

Junior Devvie




All opinions will be lined up and shot!


« Reply #5 - Posted 2005-04-23 20:32:47 »

Thanks Kev. Oh and this is not homework, but actually my real job.

OK question, I am looking at the public void find(int a,int b,int c) method and was wondering what the code would be for a dynamic version of this? So you are not limited to sequences of 3 for example. Can that pat be handled recursevly as well? Or do I just set it up to pass an array.

Kommi
Offline Mr_Light

Senior Devvie


Medals: 1


shiny.


« Reply #6 - Posted 2005-04-24 00:09:46 »

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
/**
 * @author Michael 'Mr_Light' bischoff
 */

public class MakeUpAName {

    private static final String SPACER = " ";

      public static void main(String[] args) {
            int numberOfElements = 5;
            int sizeOfset = 3;
            
            System.out.println("total: " + factorial(numberOfElements)/(factorial(sizeOfset)*factorial(numberOfElements-sizeOfset)));
            System.out.println("---------------------");
            printKSet(sizeOfset,numberOfElements);
      }
      
      public static int factorial(int i) {
            if(i<0) throw new IllegalArgumentException("attempted to (n<0)!");
            if(i==0 || i==1) return 1;
            return i*factorial(i-1);
      }

      /**
       * note: sizeResult is apperently represented in math consepts as K <br>
       * note: apperently this calculation is known as k-sets. <br>
       * @param sizeResult - size of the result-set/combination
       * @param elements - number of elements to choose from
       */

      //
      public static void printKSet(int sizeResult, int elements) {
            printCombination(sizeResult, elements, "");
            if(sizeResult!=elements) printKSet(sizeResult, elements-1);
      }
      
    // TODO : wonder if a stringbuffer would be usefull;
      private static void printCombination(int sizeResult, int elements, String base) {
            elements -= 1;
            
            if(sizeResult==1) {
                  System.out.println(base + elements); //adapt this like String[elements] for funky-er output
                  return;
            }
            base += elements; //adapt this like String[elements] for funky-er output
            base += SPACER;
            
            for(int i=elements;i>0;i--) {
                  printCombination(sizeResult-1,i,base);
            }
      }      
}


took me a bit, hf
[size=1]
ps. yes I get off on elegant-ness[/size]  Tongue

// edit
do you also have a difficuld time keeping http://mathworld.wolfram.com/Permutation.html and http://mathworld.wolfram.com/Combination.html appart  Lips Sealed

It's harder to read code than to write it. - it's even harder to write readable code.

The gospel of brother Riven: "The guarantee that all bugs are in *your* code is worth gold." Amen brother a-m-e-n.
Offline Jeff

JGO Coder




Got any cats?


« Reply #7 - Posted 2005-04-24 04:40:18 »

Quote
Thanks Kev. Oh and this is not homework, but actually my real job.


Call me a cynic, but this smells like doubling down on the sin.....


I know of no job where someone would specifically state that something had to be solved recursively.

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline ryanm

Senior Devvie


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #8 - Posted 2005-04-24 09:46:47 »

Quote

I know of no job where someone would specifically state that something had to be solved recursively.

Maybe the company is worried about under-utilising the call stack.
It's a real untapped revenue stream Wink
Offline Mr_Light

Senior Devvie


Medals: 1


shiny.


« Reply #9 - Posted 2005-04-24 14:40:35 »

ok, that you gotta explain to me.

It's harder to read code than to write it. - it's even harder to write readable code.

The gospel of brother Riven: "The guarantee that all bugs are in *your* code is worth gold." Amen brother a-m-e-n.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline ryanm

Senior Devvie


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #10 - Posted 2005-04-24 15:20:26 »

Quote
ok, that you gotta explain to me.

I had hoped that the wink emoticon would convey my levity, but perhaps i should have used sarcasm tags.
Offline Jeff

JGO Coder




Got any cats?


« Reply #11 - Posted 2005-04-24 16:02:37 »

Quote
ok, that you gotta explain to me.



He was being clever and sarcastic and coming up with a totally rediculous "explaination" Smiley

Thats all.

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline Mr_Light

Senior Devvie


Medals: 1


shiny.


« Reply #12 - Posted 2005-04-24 21:32:13 »

Grin oh sorry, didn't pick it up.

I'll go stand in this quiet corner now.

It's harder to read code than to write it. - it's even harder to write readable code.

The gospel of brother Riven: "The guarantee that all bugs are in *your* code is worth gold." Amen brother a-m-e-n.
Offline Malohkan

Senior Devvie




while (true) System.out.println("WOO!!!!");


« Reply #13 - Posted 2005-04-25 21:23:56 »

what I wanna know is how much are you being payed for this?

Admin and Game Developer at
GameLizard.com
Play Rimscape!    |    Play Conquer!
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

rwatson462 (37 views)
2014-12-15 09:26:44

Mr.CodeIt (31 views)
2014-12-14 19:50:38

BurntPizza (62 views)
2014-12-09 22:41:13

BurntPizza (99 views)
2014-12-08 04:46:31

JscottyBieshaar (60 views)
2014-12-05 12:39:02

SHC (74 views)
2014-12-03 16:27:13

CopyableCougar4 (77 views)
2014-11-29 21:32:03

toopeicgaming1999 (138 views)
2014-11-26 15:22:04

toopeicgaming1999 (127 views)
2014-11-26 15:20:36

toopeicgaming1999 (38 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!