Find permutation list

Question

I have a task. I know this task is really easy but..

A non-empty zero-indexed array A consisting of N integers is given. A permutation is a sequence containing each element from 1 to N once, and only once. For example, array A such that:

• A[0] = 4
• A[1] = 1
• A[2] = 3
• A[3] = 2

is a permutation, but array A such that:

• A[0] = 4
• A[1] = 1
• A[2] = 3

is not a permutation. The goal is to check whether array A is a permutation.

I implemented this solution, but I think this isn't the best solution.

def solution(A):
    # write your code in Python 2.6
    maxN = max(A)
    B = list(xrange(1,maxN+1))
    if sorted(A) == sorted(B):
        return 1
    else:
        return 0

Do you have any ideas how I should solve this problem?

Answer 1

def solution(A):
    N = len(A)
    return min(A) == 1 and max(A) == N and len(set(A)) == N

That takes (expected) time linear in N, so is expected to be faster than sorting. But it does rely on the stated assumption that all list entries are in fact integers. If they're not, then, for example,

>>> solution([1, 2, 4, 3.14159])
True

Answer 2

What about this?:

>>> def is_permutation(a, n):
        if len(a) != n: return False
        h = {}
        for i in a:
            if not 1 <= i <= n: return False
            if h.setdefault(i, False): return False
            h[i] = True
        return True

>>> is_permutation([1,4,2,3], 4)
True
>>> is_permutation([1,4,2,0], 4)
False
>>> is_permutation([1,4,2],4)
False

Answer 3

If both arrays should have all numbers from 1 to N you shouldn't sort them, all you need to do is make sure they actually have all the numbers.

so this is your algorithm (working solution soon):

1. make sure the list is of size N, otherwise return false.
2. generate list of N zeros (We will refer to it as zero-list)
3. for each member (say it's value is m) of the list (both) increase the zero-list[m-1] by 1
4. make sure all members of zero-list is 1

This is O(n) as opposed to O(nlogn) that you have right now.

What you are doing verifies that each member from 1 to N exists in the list you're given

#!/usr/bin/env python

def is_perm(l, n):
    # make sure initial criterias are met
    if len(l) != max(l) or len(l) != n:
        return False
    # make room for a list that verifies existence from 1 to N
    zero_list = [0 for i in l]
    # "mark" using the new list each member of the input list
    for i in l:
        try:
            zero_list[i-1] += 1
        except:
            return False

    # make sure all members have been "marked"
    for i in zero_list:
        if zero_list[i] != 1:
            return False

    # if all is good, the earth is saved
    return True

if "__main__" == __name__:
    print is_perm([1, 2, 3, 3], 4) # false
    print is_perm([1, 2, 4, 3], 4) # true
    print is_perm([1, 2, 4, 300000000000000], 4) # false

Answer 4

def is_perm(lst):
    n = len(lst)
    if min(lst) != 1 or max(lst) != n:
        return False
    cnt = [1] * n
    for e in lst:
        cnt[e - 1] -= 1
    return not any(cnt)

It has a worst case complexity O(n) which is of course optimal.

Answer 5

Just check if all elements are present ...

In [36]: all(map(lambda p: p in [1,4,3,2], range(1,5)))
Out[36]: True
In [37]: all(map(lambda p: p in [1,4,3,2444], range(1,5)))
Out[37]: False
In [38]: all(map(lambda p: p in [1,4,3], range(1,5)))
Out[38]: False

Answer 6

So I found solution which works great:

def solution(A):
  A.sort(reverse=True)
  return 1 if A[0] == len(A) and len(set(A)) == len(A) else 0

Answer 7

Here is fastest way:

def solution(A):
    '''
    >>> solution([4,1,3,2])
    1
    >>> solution([2,3])
    0
    '''
    suma = sum(A)
    N = len(A)
    if (N*(N+1)/2)!=suma:
        return 0

    return 1