2

I have the following code written in python 2.7 to find n time Cartesian product of a set (AxAxA...xA)-

prod=[]
def cartesian_product(set1,set2,n):
    if n>=1:
        for x in set1:
            for y in set2:
                prod.append('%s,%s'%(x,y))
        #prod='[%s]' % ', '.join(map(str, prod)) 
        #print prod
        cartesian_product(set1,prod,n-1)
    else:
        print prod


n=raw_input("Number of times to roll: ")
events=["1","2","3","4","5","6"]
cartesian_product(events,events,1)

This works properly when n=1. But changing the parameter value from cartesian_product(events,events,1) to cartesian_product(events,events,2) doesn't work. Seems there's an infinite loop is running. I can't figure where exactly I'm making a mistake.

Improve this question
4
  • when it runs the second time, you are passing prod as set2. Since prod is defined outside the function, set2 and prod are now the same thing. so when you do for y in set2 and prod.append, you are appending to set2, which is causing the infinite iteration. Commented May 26, 2017 at 18:13
  • 2
    Hint: itertools.product does the job (unless this is homework of some sort) Commented May 26, 2017 at 18:15
  • But the loop should stop when n<1. This means it should exactly run 2 times when n=2 @algrebe Commented May 26, 2017 at 18:31
  • @AbdullahShahriar it is still stuck in the endless for y in set2 stage. only after it comes out of that can it call cartesian_product again which will print prod. Commented May 26, 2017 at 18:33

3 Answers 3

Reset to default
3

When you pass the reference to the global variable prod to the recursive call, you are modifying the list that set2 also references. This means that set2 is growing as you iterate over it, meaning the iterator never reaches the end.

You don't need a global variable here. Return the computed product instead.

def cartesian_product(set1, n):
    # Return a set of n-tuples
    rv = set()
    if n == 0:
        # Degenerate case: A^0 == the set containing the empty tuple
        rv.add(())
    else:
        rv = set()
        for x in set1: 
            for y in cartesian_product(set1, n-1):
                rv.add((x,) + y)
    return rv

If you want to perserve the order of the original argument, use rv = [] and rv.append instead.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

your code will always give [] value as it checks for cartesian_product(set1, n-1) and in recursion, it comes to n=0 and function will return [] always.
Always return []
OK, I was confused both about what A^0 should be and how to create a set containing just an empty tuple. Should be fixed now.
2 
def cartesian_product(*X):
    if len(X) == 1: #special case, only X1
        return [ (x0, ) for x0 in X[0] ]
    else:
        return [ (x0,)+t1 for x0 in X[0] for t1 in cartesian_product(*X[1:]) ]

n=int(raw_input("Number of times to roll: "))
events=[1,2,3,4,5,6]
prod=[]
for arg in range(n+1):
    prod.append(events)
print cartesian_product(*prod)

Output:

Number of times to roll:  1

[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)]

you can also pass string in your events list but it'll print string in tuple also.

Improve this answer

Comments

1

inside the recursive call cartesian_product(set1,prod,n-1) you are passing the list prod, and you are again appending values to it, so it just grows over time and the inner loop never terminates. Perhaps you might need to change your implementation.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.