2

After about 7 hours in a row I really need some help , I need to return from recursion the amount of options that can be by setting numbers from 1 to chosen number(maximum number) , it's forbidden to use loops/arrays , only recursion , the numbers are all positive(more than 0) and goes only more positively , example : good one : {1,2} , bad one : {2,1}.

example :

n = 3 , max = 2

n : The numbers that should be in the row , max : The maximum number that can be in the row.

{1,1,1}
{1,1,2}
{1,2,2}
{2,2,2}

from that example that should return 4 because there are 4 options of 3 numbers that their value is maximum 2.

another one:

n=2
max=3

{1,1}
{1,2}
{1,3}
{2,2}
{2,3}
{3,3}

from that example it should return 6 because there are 6 options.

Daniel
  • 97
  • 10

3 Answers3

2

Without prior knowledge, this would probably be a challenging question even for an experienced mathematician. It is the count of multisets, one of the fundamental building blocks in combinatorics. I'll explain my understanding of the idea for the recurrence relation in Wikipedia.

Typically k is used for the multiset cardinality (what your question refers to as n), while n is used as the cardinality of the set (not multiset) to choose from (the max in your question).

For f(n, k), the base cases are:

f(n, 0) = 1
one way to fill the empty multiset

And,

f(0, k) = 0
no ways to choose from an empty set

For the regular case, we consider the nth element (from the set of choices). We'd like to count all the combinations that include it and all those where it's missing. Counting all combinations without the nth element is easy: we have the same multiset counting function applied to k with one less choice:

f(n - 1, k)

Now to count the combinations that include at least one nth element, we imagine taking all the ways of choosing from n items (some of which will not include an nth element) but saving one place in each combination where we will place an nth element, so we end up with:

f(n, k - 1)

Putting it all together:

function f(n, k){
  if (n == 0)
    return 0;
  if (k == 0)
    return 1;

  return f(n - 1, k) + f(n, k - 1);
}

console.log(f(2, 3));
console.log(f(3, 2));
גלעד ברקן
  • 23,602
  • 3
  • 25
  • 61
1

Recursion can be hard to comprehend at first, but it is very clear to read once you get to know it. The downside is that recursion requires way more space than the basic for-loop (Space complexity of recursive function). For some problems it can be easier to first write the recursive version and afterwards write it as for-loop. Also, if space is not a problem, it helps to make your code clean (no for-loops!)

I made some basic recursion that gives the correct answer for at least the two examples you wrote down. It may be possible that I missed an edge case: maybe a good practise to write every function call and some (edgy) test cases.

public int recursiveWrapper(int n, int max) {
    return recursive(n, max, 1, 1);
}

public int recursive(int n, int max, int lower, int current) {
//        // for your convenience
//        System.out.println("n:" + n + " max:" + max + " lowerbound:" + lower + " current:" + current);

    // Base case
    if (n <= 1 && lower == max) {
        return 1;
    }

    // Recursive step
    // Sequence complete, move to next column
    if (current == max) {
        // Make sure the lower bound does not go beyond the max. number
        int updatedLower = (lower + 1 > max) ?  lower : lower + 1;

        return 1 + recursive(n - 1, max, updatedLower, updatedLower);
    }

    return 1 + recursive(n, max, lower, current + 1);
}

In short: In the second example:

n=2 max=3

{1,1}
{1,2}
{1,3}
{2,2}
{2,3}
{3,3}

Note the pattern of the numbers that appears due to the rule that the numbers from left to right have to be equal or larger: Second column: 1>2>3 > 2>3 > 3 First column: 1>1>1 > 2>2 > 3

The 'lower bound' parameter in the recursion is basically the lowest possible number the new 'sequence' can take (where each sequence is lower bound -> max number). The base case is then when the lower bound equals the upper bound and each column has done all it 'sequences'. Possibly not a very clear explanation - maybe it helps when you see what is printed out by the commented line in the code I copy pasted.

Note: Maybe it is possible to do the recursion with less parameters. Make sure to read a lot about recursion (for example wikipedia or your studybook?). Recursions makes it easier to find solutions and understand complex and abstract problems.

P. van der Laan
  • 231
  • 1
  • 9
0

I have write some less efficient code due to time, try look at this, it will give you dir, i hope,

package com.exercise;

import java.util.Arrays;

public class Permutation {

public static void permutation(String str) {
    permutation("", str);
}

private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0)
        System.out.println(prefix);
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
    }
}

private static void permutationOnInt(String prefix, String str, int max) {

    int n = str.length();

    if (n == 0)
        System.out.println(prefix);
    else {
        for (int i = 0; i <= n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
    }
}

public static int[] return_Array(int length) {
    int[] a = new int[length];
    for (int i = 0; i < length; i++) {
        a[i] = i + 1;
    }
    return a;

}

public static void main(String[] args) {
    String fn = Arrays.toString(return_Array(3));
    String apple = String.join(",", fn.replace("[", "").replace("]", "").replace(",", "").replaceAll("\\s+", ""));
    permutationOnInt("", apple, 3);
}
}

After you get the result you can convert it back to the array. Importent : This code is totally not optimized. I will post optimized later

parlad
  • 1,143
  • 4
  • 23
  • 42