from math import sqrt, ceil, log2 from sys import exit data = [] ddata = dict() def fill(r1, r2, r3, rest): if len(r1) > 3: return if not rest: k = (list(sorted(r1)),list(sorted(r2)),list(sorted(r3))) ddata[str(k)] = k return t = [rest[0]] fill(t+r1, r2, r3, rest[1:]) fill(r1, t+r2, r3, rest[1:]) fill(r1, r2, t+r3, rest[1:]) fill([],[],[],[0,1,2,3,4]) def to_bin(r): c = 0 for i in r: c |= 1<<i return c for _, v in ddata.items(): r1, r2, r3 = v data.append((to_bin(r1)<<10) | (to_bin(r2)<<5) | to_bin(r3)) def hash_func(data, pow2=True): class DoesNotFit(Exception): pass #controlla che elementi nella stessa posizione non siano settati def check(l, r): for a, b in zip(l, r): if (a&b)==1: return False return True #calcolo dimensione minima size = max(ceil(sqrt(max(data))), len(data)) if pow2: size = 1<<ceil(log2(size)) #procedo per tentativi while True: try: square = [[0]*size for i in range(size)] rowcounts = [0] * size #tabella da comprimere for c in data: square[c//size][c%size] = 1 rowcounts[c//size]+=1 most_frequent_row_order = reversed(sorted(zip(rowcounts, range(size)))) #shift relativo ad ogni riga shifts = [0]*size #tabella compressa in una riga C = [0]*size #cerco di ruotare ogni riga in modo che non ci siano duplicati sulle colonne for _, r in most_frequent_row_order: tmp = square[r] #ruoto finché non trovo una rotazione che vada bene o abbia fatto un giro completo while not check(C, tmp) and shifts[r] < size: shifts[r] += 1 tmp = tmp[-1:]+tmp[:-1] #Se ho compiuto un giro completo non posso sistemare le righe if shifts[r] == size: raise DoesNotFit #marko le posizioni occupate dalla riga corrente ruotata C = list(map(sum, zip(C, tmp))) return size, shifts except DoesNotFit: pass #ritento con una dimensione più grande if pow2: size = size << 1 else: size += 1 def output_c_hash_func(data, prefix="", pow2=True): size, shifts = hash_func(data, pow2) tsize = prefix+"SIZE" def tshifts(n): return prefix+"SHIFTS["+str(n)+"]" def ttable(n): return prefix+"TABLE["+str(n)+"]" print("#define", tsize, size) print("int", tshifts(size), "= {", end="") it = iter(shifts) print(next(it), end="") for c in it: print(",", c, end="") print("};") print("int", ttable(size), ";") print("#define", prefix+"lookup(i)", ttable("((i)+"+tshifts("(i)/"+tsize)+")%"+tsize)) output_c_hash_func(data, "HT_", False)
Standard input is empty
#define HT_SIZE 232 int HT_SHIFTS[232] = {0, 0, 0, 0, 1, 0, 12, 6, 10, 4, 3, 0, 0, 15, 1, 51, 62, 34, 4, 4, 0, 4, 78, 11, 37, 6, 13, 12, 22, 0, 0, 135, 118, 71, 54, 0, 10, 1, 0, 10, 7, 7, 2, 0, 2, 0, 3, 63, 6, 9, 18, 5, 0, 0, 0, 0, 0, 1, 0, 1, 0, 6, 6, 0, 3, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 1, 0, 0, 0, 4, 0, 1, 0, 8, 19, 10, 0, 0, 0, 0, 0, 0, 25, 7, 9, 0, 0, 0, 17, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 1, 5, 0, 0, 2, 10, 0, 0, 0, 0, 0, 0, 0, 4, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; int HT_TABLE[232] ; #define HT_lookup(i) HT_TABLE[((i)+HT_SHIFTS[(i)/HT_SIZE])%HT_SIZE]