Chris Chris - 1 month ago 12
Python Question

python - checking if an array consisting of N integers is a permutation

I am analyzing the routine which checks if an array of N integers is a permutation (sequence containing each element from 1 to N).




I am new to python. I can't grasp how this routine gets the correct answer. Could anybody explain the logic behind the loop? especially the use of the

counter[element-1]
.




Is the counter a built-in function working on every element of A? does the
counter[element-1]
reference position/value of elements of A by default because the loop is defined on an array?



A=[4,1,3,2]

def solution(A):
counter = [0]*len(A)
limit = len(A)
for element in A:
if not 1 <= element <= limit:
return 0
else:
if counter[element-1] != 0:
return 0
else:
counter[element-1] = 1

return 1


Update:
I modified the code to see the values used within the loop, for example

def solution(A):
counter = [0]*len(A)
limit = len(A)
for element in A:
if not 1 <= element <= limit:
print element
print 'outside'
return 0
else:
if counter[element-1] != 0:
print 'element %d' % element
print [element-1]
print counter[element-1]
return 0
else:
counter[element-1] = 1
print 'element %d' % element
print [element-1]
print counter[element-1]

return 1


gives me

element 4
[3]
1
element 1
[0]
1
element 3
[2]
1
element 2
[1]
1
1


I still don't get the logic. For example fot the first element, why [3] gives 1?

Answer

The idea behind the code is twofold. A permutation of the list [1, 2, ..., N] has two properties. It has only elements between 1 and N and each element just appear one time in the list. I will try explain it to you part by part this idea in the code.

def solution(A):
    counter = [0]*len(A)
    limit = len(A)

Assume as an example, a list [1, 3, 2]. counter is initialized as a list of zeros of size len(A) = 3. Each 0 correspond to one of the elements of the list

for element in A:
        if not 1 <= element <= limit:
            return 0

This part condition is the most easy one. If the element is not in this range, the list cannot be a permutation of [1, 2,...N]. For instance, [1, 3, 2] is a permutation of [1, 2, 3] but [1, 6, 2] is not.

 else:
            if counter[element-1] != 0:
                return 0
            else:
                counter[element-1] = 1

This next part is related with the uniqueness of each term. The if checks if a number = element has already passed through this loop. The second else make sure that this number is marked, so if a repeated number is found in the next iterations, the if will be true and return 0.
For instance, for the list [1, 2, 2]. The first 2 would not trigger the if, while the second 2 would trigger it, returning 0. On the other hand, [1, 3, 2], would never trigger the if. If all the number pass this conditions, the two properties were true and the list is a permutation.

Comments