Recursive function that returns the number of possible combinations
I had an interview and was asked a question that I would like to understand.
Question
Create a recursive function that returns the number of possible combinations of arrays of a given length that can be made from an array of non-repeating sequential integers.
f (array, length) = combinations
Example 1
- array = [0,1,2,3]
- length = 2
- Combinations = 10 (all combinations: [0.0] [0.1] [0.2] [0.3] [1.1] [1.2] [1.3] [2.2] [2, 3] [3.3])
- Note that [0,0] is allowed, but [1,0] not because [0,1] is defined
Example 2
- array = [0,1]
- length = 3
- Combinations = 4 (all combinations: [0.0.0] [0.0.1] [0.1.1] [1.1.1])
One "hint" has been suggested. The interviewer said that the array itself is irrelevant; the length was all that was needed.
source to share
This algorithm can be expressed recursively because the solution can be expressed in terms of solutions for smaller inputs. "Less" has two meanings here:
-
A subset of an array; specifically the submatrix after the current index of the element
-
Solutions for shorter lengths; they can be combined together to give a solution for length + 1
Stop conditions:
-
When array size
A = 1
- only one combination can be generated -
When length
L = 1
is the number of combinations = the number of elements in the array
A fully recursive procedure is a surprisingly simple one-liner:
return [recursive call to rest of array, same length] +
[recursive call to same array, length - 1]
This is called dynamic programming.
code:
int F(int A, int L)
{
if (A <= 1) return 1;
if (L <= 1) return A;
return F(A - 1, L) + F(A, L - 1);
}
Tests:
-
F(4, 2) = 10
-
F(2, 3) = 4
-
F(3, 5) = 21
(trace it with pens and paper to see for yourself)
EDIT: I gave an elegant and simple solution, but I may not have explained this as well as @RoryDaulton. Consider giving him credit back.
source to share
You are not giving the target language and you are not saying what kind of help you need. Therefore, I will give a general idea of the algorithm, which should be easy to code if you know recursion in a specific language. Ask if you want more code in Python, my current preferred language.
You know that you need to recurse, and you have two things you can iterate on: the length of the given array, or the length of the required arrays. Let's recurse on the second, and let's say that the given array [0, 1, ..., n-1]
, since you know the actual content doesn't matter.
If the desired length r
is 1
, you know, there is only n
required arrays, namely [0]
, [1]
..., [n-1]
. So there is a base case for your recursion.
If you have a "combination" of length r-1
, how can you extend it to length r
and keep the requirements? Look at the last element of the length array r-1
- call it k
. The next element cannot be less than, so all possible arrays extended to length r
are an array r-1
added with k', 'k+1
, ..., n-1
. These are n-k
arrays of length r
.
Is it clear how to code this? Please note that you do not need to store all the length of the array r-1
, you only need to count how many there are arrays with the end of an element 0
, or 1
, or ... n-1
. This makes it easy to code for - not much memory. In fact, things can be shrunk longer - I'll leave that to you.
Note that the interviewer probably didn't want the code, he wanted your thought process to lead to the code to see how you think. This is one way to understand the problem.
source to share