The problem is based on filling a square matrix of size 'n' with all possible combinations of 0 and 1.
With n = 2:
[[0,0],[0,1],[1,0],[1,1]]
n=3 :
[[0,0,0],[0,0,1],[0,1,0],...,[1,1,1]]
The problem is that I don't know why it enters the if if the size of the list is greater than the size, if someone can help me I would already appreciate it. I attach the code
global tam
tam=3
def matriz(candidato):
if(len(candidato)<tam):
auxi=candidato
auxi.append(0)
matriz(auxi)
print(candidato)
auxd=candidato
auxd.append(1)
matriz(auxd)
else:
print(candidato)
matriz([])
In any recursive function you have to be clear about two things:
n+1
fromn
If we have
matrix(n)
, the way to calculatematrix(n+1)
is:The cutoff condition will be what happens when
n==0
:Putting it all together:
Putting as a cut condition
matrix(0) == [[]]
usually gives some confusion. The matrix function must return a list of lists and the empty element[]
is not correct. (The[[]]
is called the initial element of the category from which the rest can be drawn).Well, seeing that the implementation is perhaps not the most appropriate, I propose the following:
We will pass three elements, which will be:
The operation is simple so I think that with a scheme it will be clearer after reading the code:
In this way, all the possible combinations will be extended in a tree. Once we have it, we will add it to fullMatrix where they will be sorted, the final result being:
Since this was a class exercise, I didn't want to give you the answer without first letting you try it for yourself. But since you have finally been given an answer and you have accepted it, I am forced to intervene.
The accepted answer, although using recursion in a literal sense (since the function
matrix()
contains calls to itself), is not using it in the correct way. As implemented, that recursion is nothing more than a mechanism to addn
ones orn
zeros to a list. Perfectly replaceable by a loop that repeatsn
times.The grace of recursion is that the implementation solves a problem recursively , that is, based on the solution to a smaller problem. Let me explain.
Approach
The "recursive" idea is: imagine that you have a function that solves the case N-1 for you . For example let's call
f()
that function and imagine that when you call it, it is able to give you all possible combinations of N-1 bits_.That is, suppose N is 3, and then you can call
f(2)
and it returns the list[[0,0], [0,1], [1,0], [1,1]]
. The question is how would we use that function as part of our solution for N?Think about it for a bit and read on.
Once we have the idea, we will implement a solution that uses
f(N-1)
as a base to build the solution for N:f()
). This trivial case will be used if N is 0.f(N-1)
.The thing would be like this (pseudocode):
N==0
return the list[[]]
. This is the trivial case that we can solve without usingf()
. It is a list that has only one element, the empty list. Since with N equal to 0 bits, that is the only combination we can form (the empty set).Otherwise we have to rely on the result returned by
f(N-1)
. We can do it like this.resultado = []
That list at the end will have all the N-bit combinations searched for.Use
f(N-1)
to get the list of N-1 bit combinations, that is:sol = f(N-1)
Each element of the list
sol
will be a different combination ofN-1
bits, just add the missing bit (which will give two more possibilities), so:elemento
ofsol
, add toresultado
the listelemento + [0]
and the listelemento + [1]
resultado
Example to see how it works
Let's check that it works for N=3. When calling
f(2)
we would have onsol
the list[[0,0], [0,1], [1,0], [1,1]]
. So by iterating through this list:[0,0]
, with which we add toresultado
the lists resulting from concatenating a 0 and a 1 at the end, therefore the lists[0,0,0]
and[0,0,1]
[0,1]
, which will add toresultado
the lists[0,1,0]
and[0,1,1]
resultado
?But...
Now there is an important detail . You will say "this is all very well, but I am assuming that I have a function
f()
capable of solving case N-1... where do I get that function from?"And here is the magic of recursion . Turns out we just wrote that function! It is the same function that calculates the case
f(N)
! Therefore, it suffices that it calls itself when it needs the solution forf(N-1)
.I think that with this you have the necessary theoretical ingredients to be able to code in python a correct solution to the problem that you have been asked.