CODEWITHSUNDEEP
pythonrecursioncombinationspermutation
matrix42
matrix42

Reputation: 289

non-recursive version Permutations

I have two functions, prod and perm. They are very similar.Both of them using the recursive.Now I wan't replace recursion with for loop. prod2 worked correct, but perm2 doesn't, How can I fix it?

#Recursive version:

def prod(A,k):
    return [[]] if k==0 else [[a]+b for a in A for b in prod(A,k-1)]

def perm(A,k):
    return [[]] if k==0 else [[a]+b for a in A for b in perm([i for i in A if i!=a],k-1)]


#NonRecursive version:

def prod2(A,k):
    r=[[]]
    for i in range(k):
        r=[[a]+b for a in A for b in r]
    return r

def perm2(A,k):
    r=[[]]
    for i in range(k):
        r=[[a]+b for a in A for b in [i for i in r if i!=a ] ]
    return r

print prod([1,2,3],2)
print prod2([1,2,3],2)

print perm([1,2,3],2)
print perm2([1,2,3],2)

Upvotes: 1

Views: 1535

Answers (2)

Anatoly Alekseev
Anatoly Alekseev

Reputation: 2410

Beautiful solution guys, here's a rewrite which works with Numba:

@numba.njit()
def permutations(A, k):
    r = [[i for i in range(0)]]
    for i in range(k):
        r = [[a] + b for a in A for b in r if (a in b)==False]
    return r
permutations([1,2,3],3)

Upvotes: 1

Igonato
Igonato

Reputation: 10787

Since the r variable in your code contains lists, i != a will always be True. Here is how to fix it:

def perm2(A, k):
    r = [[]]
    for i in range(k):
        r = [[a] + b for a in A for b in [i for i in r if a not in i]]
    return r

Or simply:

def perm2(A, k):
    r = [[]]
    for i in range(k):
        r = [[a] + b for a in A for b in r if a not in b]
    return r

Upvotes: 3

Related Questions