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?

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.