from itertools import combinations def verify(los, num): target = max(map(max, los)) + 1 for subset in combinations(los, num): if len(reduce(lambda x, y: x | y, subset)) != target: return False for subset in combinations(los, num - 1): if len(reduce(lambda x, y: x | y, subset)) == target: return False return True def num2bin(s, size): result = [0] * size for n in s: result[n] = 1 return result def bin2num(s): result = set([]) for i in range(len(s)): if s[i]: result.add(i) return result def answer(x, n): # test = [[1, 1, 1, 1, 1, 1, 0, 0, 0, 0], # [1, 1, 1, 0, 0, 0, 1, 1, 1, 0], # [1, 0, 0, 1, 1, 0, 1, 1, 0, 1], # [0, 1, 0, 1, 0, 1, 1, 0, 1, 1], # [0, 0, 1, 0, 1, 1, 0, 1, 1, 1]] # numeric = map(bin2num, test) # print verify(numeric, 3) test = """@@@@@@@@@@.............. @@@@......@@@@@@....@@@@ @...@@@...@@@...@@@.@@@. .@..@..@@.@..@@.@@.@@@.@ ..@..@.@.@.@.@.@@.@@@.@@ ...@..@.@@..@.@@.@@@.@@@ """.strip().split('\n') test = map(lambda l: bin2num([1 if i is '@' else 0 for i in l]), test) print verify(test, 4) answer(5, 3)