check whether an element is in list or not

Question

I have a matrix or list of lists:

x = [[1,2,3], 
     [2,3,1], 
     [3,1,2]]

My goal is to check whether

1) Each column of the matrix contains, each of the whole numbers from 1 to n exactly once.

2) Each row of the matrix contains each of the whole numbers from 1 to n exactly once.

This is the problem exercise that I encountered when I was solving Udacity's intro to programming course. This is my solution to the problem. I know that this is long and inefficient. So what is the short and efficient way to do this problem??

def check(p):
    j = 0
    for e in p:
        i = 1 + j
    s = str(p)

    if s.find('.')!= -1:
        return False

    while i < len(p):
        if p[i] == e:
            return False
        if p[i] > len(p) or p[i] < 1:
            return False
        i += 1
        j += 1
    return True

def check_sudoku(p):
    i = 0
    z = []
    a = []
    x = 0
    for e in p:
        r = check(e)
        if r == False:
            return r

    #Below here is to transpose the list
    while x < len(p):
        z.append(1)
        x += 1
    while i < len(p):
        for e in p:
            a.append(e.pop())
        z[i] = a
        i +=  1
        a = []

    #Below here is to check the transpose
    for g in z:
        r = check(g)
        if r == False:
            return r
    return True

Answer 1

You can simplify your check program like this:

def check_valid(matrix):
    n = len(matrix[0])
    valid_num = range(1, n+1)     # make a list of valid number from 1 to n

    # sort rows and column of matrix in ascending order and compare with valid_num 
    for line in matrix:
        if sorted(line) != valid_num:
            return False
    for column in zip(*matrix):
        if sorted(column) != valid_num:
            return False

    # If all rows and column is valid, then 
    return True 

EDIT: follow @vocalno KISS rule but faster and work for both numbers and characters

def check_valid2(matrix):
    n = len(matrix)

    for line in matrix+zip(*matrix):
        if len(set(line)) != n:
            return False

    return True

In[9]: %timeit for m in (x, y): check_valid_mine(m)
100000 loops, best of 3: 8.55 µs per loop

In[10]: %timeit for m in [x,y]: check_valid2(m)
100000 loops, best of 3: 5.77 µs per loop

EDIT 2: all about the speed

def check_valid3(matrix):
    n = len(matrix)

    for line in matrix+zip(*matrix):
        if not len(set(line)) - n:
            return False

    return True

In[19]: %timeit for m in [x,y]: check_valid3(m)
100000 loops, best of 3: 2.29 µs per loop

Answer 2

Here's my solution

I cycle over rows and columns, using zip to flips matrix and chain - to combine 2 lists. if either row or column contain values not in valid_set,

set(row) - valid_set

expression will yield non-empty set - turned to False by not- and all cycle will end

from itertools import chain
def check_valid(matrix, n):
   valid_set = set(range(1, n+1))
   return all(not(set(row) - valid_set) for row in chain(matrix, zip(*matrix)))

EDIT:
Sorry, misread the question; here's correct answer - all exits on first False

from itertools import chain
def check_valid(matrix):
   valid_set = set(range(1, len(matrix)+1))
   return all(set(row) == valid_set for row in chain(matrix, zip(*matrix)))

EDIT 2:

Out of curiosity - I timed sort vs set approach

In [74]: x = [[1,2,3], 
   ....:      [2,3,1], 
   ....:      [3,1,2]]

In [79]: %timeit for row in x: sorted(row)
1000000 loops, best of 3: 1.38 us per loop

In [80]: %timeit for row in x: set(row)
1000000 loops, best of 3: 836 ns per loop

set is about 30% faster

EDIT 3: I fixed dangerous solution and updated mine

In [132]: def check_valid(matrix):
    valid_num = np.unique(np.array(matrix)).tolist() # selects unique elements
    for line in matrix:
        if sorted(line) != valid_num:
            return False
    for column in zip(*matrix):
        if sorted(column) != valid_num:
            return False
    return True
In [136]: %timeit for m in (z, d): check_valid(m)
10000 loops, best of 3: 57.8 us per loop

In [115]: def check_valid_mine(matrix):                                                  
       valid_set = set(chain(*matrix))
       return all(set(row) == valid_set for row in chain(matrix, zip(*matrix)))

In [137]: %timeit for m in (z, d): check_valid_mine(m)
100000 loops, best of 3: 8.96 us per loop

Bottom line? KISS - keep it simple stupid

Explaining the matrix transposition by zip()

• operator before iterable argument in a function call expands this argument list of positional arguments, essentially

  zip(*matrix)

means

zip(matrix[0], matrix[1], matrix[2], ...)

thus rearranging columns into rows Check out this answer for detailed explanation of * and ** operators

Answer 3

I was searching for a solution that perfectly matches both characters and numbers and I came with a solution using numpy library. I slightly modified dragon2fly solution. Please correct me if I am wrong. I checked the solution for both z and d values and it gave correct results.

 import numpy as np

z = [[8,9,10],  # example case with numbers
     [9,10,8], 
     [10,8,9]]


d =  [['a','b','c'], # example case with characters
      ['b','c','a'],
      ['c','a','b']]

def check_valid(matrix):
    valid_num = list(np.unique(matrix)) # selects unique elements


    # sort rows and column of matrix in ascend order and compare with valid_num 
    for line in matrix:
        if sorted(line) != valid_num:
            return False
    for column in zip(*matrix):
        if sorted(column) != valid_num:
            return False

    # If all rows and column is valid, then 
    return True