Skip to content
Advertisement

Finding elements unique to each rows in a 2D array

Given a 2D Array (Python List), I need to find a new 1D such that it contains elements unique in each column. For example:

[1, 1, -1, 1, 0]

[1, -1, -1, 3, 4]

[0, 0, 0, -2, -4]

should give me for example, [1,-1,0,3,4]. My trials so far: results is a 2D array of size 3 rows and n columns. last is the array which stores the end result, better said the unique values for each columns. From this array I need to find a 1D array of elements so that they are different.

last = []    
for i in range(len(results[0])):
    a = results[0][i]
    b = results[1][i]
    c = results[2][i]
    if (a not in last):
        last[i] = a
    elif (b not in last):
        last[i] = b
    elif (c not in last):
        last[i] = c

But it does not always give correct answer. This fails for input for example:

[1, 2, 3, 3]

[1, 0, -1, 1]

[0, 1, 2, 2]

The output should be for example [0,1,2,3] or [1,0,3,2] Any help and hints is appreciated.

Advertisement

Answer

The code in this answer returns a list made of one element from each column, such that this list contains no duplicates.

Bruteforce: Using itertools.product on the columns to iterate through every possible combination of elements from every column, and returning the first one which contains no duplicates.

Code

from itertools import product

def getCombinationWithoutDuplicates(table):
  columns = map(frozenset, zip(*table))
  for combination in product(*columns):
    if len(set(combination)) == len(combination):
      return combination
  return None

Output

>>> getCombinationWithoutDuplicates([[1, 1, -1, 1, 0],
                                     [1, -1, -1, 3, 4],
                                     [0, 0, 0, -2, -4]])
(0, 1, -1, 3, 4)

>>> getCombinationWithoutDuplicates([[1, 1, -1, 5, 0],
                                     [1, 3, 2, 4, 4],
                                     [0, 1, 2, 5, -4]])
(0, 1, 2, 4, -4)

Code explanation

  • zip(*table) transposes the list of lists (so it’s the list of columns rather than the list of rows);
  • map(frozenset, ...) remove duplicates from each columns, which has no impact on the final solution but makes the bruteforce faster;
  • for combination in product(*columns): iterates over every possible combination of one element from each column;
  • len(set(combination)) == len(combination) tests whether there are duplicates in the combination;
  • In the possible situation where there is no solution, the for-loop will be executed in its entirety and flow will reach the last line return None.

References

User contributions licensed under: CC BY-SA
1 People found this is helpful
Advertisement