Chris - 8 months ago 65

Python Question

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]`

`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

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.

Source (Stackoverflow)