Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (769) Games in Android Showcase (230) games submitted by our members Games in WIP (855) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 help with simple recursion  (Read 4158 times) 0 Members and 1 Guest are viewing this topic.
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
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.

Kommi
kevglass

« JGO Spiffy Duke »

Medals: 319
Projects: 25
Exp: 22 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

kevglass

« JGO Spiffy Duke »

Medals: 319
Projects: 25
Exp: 22 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= 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

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!

If this is homework, shame on you! You're only cheating yourself.
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
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
* note: apperently this calculation is known as k-sets.
* @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]

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

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

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
Mr_Light

Senior Devvie

Medals: 1

shiny.

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

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