HHU AlDat Blatt 11 Aufgabe 1 a)

hashing.py

#!/usr/bin/env python3

import itertools
import math

goallist = [8, 31, 44, 55, 3, 47, 64]

combination = []

def quersumme(x):
    x = str(x)
    return sum([int(i) for i in x])

def h(x):
    return (quersumme(x) % 7) - 1

def hashfunc(lista):
    # Create an empty hashing table
    hashtable = [0 for i in range(0, len(lista))]

    sondierungCounter = 0
    
    # iterate over all the items in the given list
    for item in lista:

        # calculate the first hash index
        index = h(item)

        # if there is place in the hashingtable, insert the item there
        if hashtable[index] == 0:
            hashtable[index] = item
        # else, "quadratisches sondieren"
        else:
            #print("!")

            # quadratic list
            quadraticlist = []
            for i in range(1, 10):
                quadraticlist.append((i ** 2))
                quadraticlist.append(-(i ** 2))

            print(quadraticlist)

            for i in quadraticlist:
                index = (index + i) % 7

                if hashtable[index] == 0:
                    hashtable[index] = item
                    sondierungCounter = i
                    break

    return hashtable, sondierungCounter
        
# generating all possible permutations
for item in itertools.permutations(goallist):
    combination.append(item)

print("Original list: ", end="")
print(goallist)
print("Length of the original list: ", end="")
print(len(goallist))
print("Number of combinations: ", end="")
print(math.factorial(len(goallist)))
print(60 * "-")

for item in combination:
    item = list(item)

    sondierungsCounter = 0
    hashedlist, sondierungsCounter = hashfunc(item)

    if hashedlist == item:
        print(f"{item} {sondierungsCounter}")