CODEWITHSUNDEEP
python-3.xrecursion
DSL
DSL

Reputation: 167

Recursive function

Let S be the subset of the set of ordered pairs of integers defined recursively by

Basis step: (0, 0) ∈ S.

Recursive step: If (a,b) ∈ S,

then (a,b + 1) ∈ S, (a + 1, b + 1) ∈ S, and (a + 2, b + 1) ∈ S.

List the elements of S produced by the first four application 

def subset(a,b):
base=[]
if base == []:
    base.append((a,b))
    return base

elif (a,b) in base:
    base.append(subset(a,b+1))
    base.append(subset(a+1,b+1))
    base.append(subset(a+2,b+1))
    return base


for number in range(0,5):
    for number2 in range(0,5):
        print(*subset(number,number2))

The output is

(0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (1, 0) (1, 1) (1, 2) (1, 3) (1, 4) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 0) (3, 1) (3, 2) (3, 3) (3, 4) (4, 0) (4, 1) (4, 2) (4, 3) (4, 4)

But the correct answer is more than what I got.

(0, 1), (1, 1), and (2, 1) are all in S. If we apply the recursive step to these we add (0, 2), (1, 2), (2, 2), (3, 2), and (4, 2). The next round gives us (0, 3), (1, 3), (2, 3), (3, 3), (4, 3), (5, 3), and (6, 3). And a fourth set of applications adds (0,4), (1,4), (2,4), (3,4), (4,4), (5,4), (6,4), (7,4), and (8,4).

What did I do wrong with my code?

Upvotes: 0

Views: 277

Answers (1)

Sygmei
Sygmei

Reputation: 465

Is this what you want ? Based on the result you wanted :

def subset(a):
  #Returns a list that contains all (i, a + 1) from i = 0 to i = (a + 1) * 2 + 1
  return [(i, a + 1) for i in range((a + 1) * 2 + 1)]

setList = []
for i in range(4):
  setList += subset(i) #Fill a list with subset result from i = 0 -> 3

print(setList)

If you want to use a recursive function, you can do that too :

def subset(a, b):
  if a < b * 2:
    #Returns a list that contains (a, b) and unzipped result of subset(a + 1, b) 
    #Otherwise it would add a list in the list
    return [(a, b), *subset(a + 1, b)] 
  else:
    return [(a, b)] #If deepest element of recursion, just return [(a, b)]

setList = []
for i in range(5):
  setList += subset(0, i)

print(setList)

Upvotes: 1

Related Questions