Combination and Permutation Algorithms (recursive)

Your teacher wants you to use recursion.

What is the answer, for a given X, if Y is zero? Solve this using your code.

What is the answer, for a given X, if I give you the solution for Y = some random whole number n for free, what is the solution for n + 1? In other words, if I tell you that the solution for X = 5, Y = 3 is { { ... }, { ... }, ... }, can you easily figure out the solution for X = 5, Y = 3 + 1 = 4?

Here is an example for a totally different problem:

Lets say you know the first previous two Fibonacci numbers are 1 and 1. Then finding the next one is easy, right? it's 2. Now lets say you know the previous two are 1 and 2, the next one is 3! If the previous two are 2 and 3, the next one is 5!

Some pseudocode:

public int fib(int stop) {
     if (stop < 2) return 1;
     return fibHelp(stop - 2, 1, 1);
}

public int fibHelp(int stop, int oneBelow, int twoBelow) {
   if (stop == 0) return oneBelow;

   return fibHelp(stop - 1, oneBelow + twoBelow, oneBelow);
}

See how fibHelp calls itself? That's recursion! Just make sure you have a stop condition (my if statement).

For your specific problem, don't return void, instead have comboNoRep return a Set<Set<Integer>>. When y=0, return a Set with one element (an empty Set). y=1, return a Set that builds a bunch of Sets by adding one element to each set in the larger set (in the case of y=1 that Set is empty, and so forth).

Use Set and not List because you want to make sure that you don't have duplicates.

You have to explore all the possible routes:

Create an empty list of "solutions"

For every card a, your first set of solutions start by having the card in each envelope - x*y solutions

For each card you picked: repeat, from the same set of cards removing the one you used until you run out of cards when you do your solution is completed and you put it in the array

print the array

For problem one, imagine your cards are named card_1 to card_x. Observe that every possible way to fill Y envelopes either includes card_1 or doesn't. If it does, you've reduced the problem to filling Y-1 envelopes with cards 2 through X; if it doesn't you've reduced the problem to filling Y envelopes with cards 2 through X.

Hopefully that's enough of a hint to help you out without being too much. Good luck!

You can use the Exeter Algorithm for the first Part. Refer below link for more information:

Visit Here: http://www.bearcave.com/random_hacks/permute.html

I don't know how to do it in JAVA but a snippet from my old C code may serve the purpose.

#include <stdio.h>

//Print Function
void print(const int *arr, const int size)
{
    int i;

    if (arr != 0) 
    {
        for (i = 0; i < size; i++)
            printf("%d ", arr[i]);
        printf("\n");
    }
}

//Permute Function
void permute(int *arr, const int start, const int sets, const int len)
{  
    int i,tmp;

    if (start == sets-1)
        print(arr, sets);
    else
    {
        for (i = start; i < len; i++)
        {
            tmp = arr[i];

            arr[i] = arr[start];
            arr[start] = tmp;

            permute(arr, start+1, sets, len);   //<-- Recursion

            arr[start] = arr[i];
            arr[i] = tmp;
        }
    }
}

int main()
{
  int sets,arr[] = {1, 2, 3, 4, 5};

  //Accept Number Of Sets To Form
  printf("Enter Number Of Sets: ");
  scanf("%d",&sets);

  //Call Permute Function
  permute(arr, 0, sets, sizeof(arr)/sizeof(int));

  return 0;
}