help with simple recursion

Newbie & Debugging Questions
#1

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.

#2

any takers? I really need this solved by tomorrow. :’(

#3

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

#4

Here’s a way:


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

#5

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:

#6

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.

#7 

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

ps. yes I get off on elegant-ness :stuck_out_tongue:

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

#8

[quote]Thanks Kev. Oh and this is not homework, but actually my real job.
[/quote]
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.

#9

Maybe the company is worried about under-utilising the call stack.
It’s a real untapped revenue stream :wink:

#10

ok, that you gotta explain to me.

#11

[quote]ok, that you gotta explain to me.
[/quote]
I had hoped that the wink emoticon would convey my levity, but perhaps i should have used sarcasm tags.

#12

[quote]ok, that you gotta explain to me.
[/quote]
He was being clever and sarcastic and coming up with a totally rediculous “explaination” :slight_smile:

Thats all.

#13

;D oh sorry, didn’t pick it up.

I’ll go stand in this quiet corner now.

#14

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