Perfect Hash Families (PHFs) are a widely studied combinatorial object. Essentially, they are 4-tuples
(N; t, k, v), where the PHF is an
k array of
v symbols. For any
t columns chosen, there is at least one row of those chosen columns that has no symbol duplicated in that row.
I want to be able to count how many "non-distinct"
t-column choices there are in a given PHF. My code is below, with some sample inputs that I made up:
from itertools import combinations def get_column(phf, c): return [x[c] for x in phf] # returns the PHF as if we restrict to the "cs" columns (a list) def combine_columns_into_array(phf, cs): r =  for c in cs: r.append(get_column(phf, c)) return list(map(list, zip(*r))) # returns the number of t-column choices that have no distinct rows def count_non_distinct_combinations(phf, t): k = len(phf) true_count = 0 # get all combinations for c in combinations([i for i in range(k)], t): b = False choices = combine_columns_into_array(phf, list(c)) for row in choices: # if the row is completely distinct if len(row) == len(set(row)): b = True # if all rows are non-distinct: if not b: true_count += 1 return true_count phf = [ [4, 2, 3], [2, 1, 3], [1, 1, 4]] # first 2 columns have no distinct rows phf2 = [ [4, 4, 3], [2, 2, 3], [1, 1, 4]] print(count_non_distinct_combinations(phf, 2)) # 0 print(count_non_distinct_combinations(phf2, 2)) # 1
I plan to use this code as a metric for how "good" the array is - what I mean by this is that I want, given the number of rows
N, try to reduce this metric as much as possible. Therefore, speed/efficiency is the most important part of any review of this code.