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 linereturn None
.
References