CODEWITHSUNDEEP
python
Chris
Chris

Reputation: 767

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?

Upvotes: 1

Views: 1309

Answers (2)

Arthur
Arthur

Reputation: 573

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.

Upvotes: 2

ivan_pozdeev
ivan_pozdeev

Reputation: 36026

Quite a cunning algorithm actually.

The input is a sequence of length N.

Each element of input is presumed to be an integer (if not, either comparison or indexing will throw an exception).

counter is an array of flags - of length N, too.

  • No integers outside of [1,N] range are allowed
  • No duplicates are allowed (see how it's done)

Can you now prove that the only way for both conditions to stay true is for the sequence to be a permutation?

Upvotes: 2

Related Questions