Boolsches Produkt
Code: Alles auswählen
# Author Joel Kessler
def boolean_product(A, B, n_r, m_r):
res = []
for row_i in range(0, n_r):
row = []
for col_i in range(0, m_r):
sel_row = A[row_i]
sel_col = [B_row[col_i] for B_row in B]
product_row_col = 0
# (....) or (....)
for sel_row_e_i in range(0, len(sel_row)):
sel_row_e = sel_row[sel_row_e_i]
sel_col_e = sel_col[sel_row_e_i]
if sel_row_e == 1 and sel_col_e == 1:
# (a1 and b1) or (....)
product_row_col = 1
break
row.append(product_row_col)
res.append(row)
return res
A = []
B = []
print("Dimension Linke A-Matrix (n x m):")
n_a = int(input("n:"))
m_a = int(input("m:"))
print("Dimension Rechte B-Matrix (n x m):")
n_b = int(input("n:"))
m_b = int(input("m:"))
# (n x m) (n x m)
if m_a != n_b:
print("Dimensionsfehler.")
else:
print("Resultierende Matrix: ({},{})".format(n_a, m_b))
print("Matrix A:")
for row_i in range(0, n_a):
row = []
for pos_i in range(0, m_a):
row.append(int(input("Position: ({}, {}): ".format(row_i+1, pos_i+1))))
A.append(row)
print("Matrix B:")
for row_i in range(0, n_b):
row = []
for pos_i in range(0, m_b):
row.append(int(input("Position: ({}, {}): ".format(row_i+1, pos_i+1))))
B.append(row)
print("Matrix A:")
for row in A:
print(row)
print("Matrix B:")
for row in B:
print(row)
res = boolean_product(A, B, n_a, m_b)
print("Boolsches Produkt:")
for row in res:
print(row)
Code: Alles auswählen
# Author Joel Kessler
def remove_from_dict(dict_data, l2):
for e in l2:
dict_data.pop(e, None)
def remove_from_list(l1, l2):
lr = list(l1)
for e in l2:
if e in lr:
lr.remove(e)
return lr
def dijkstra(edges_and_weight, start_node):
nodes = set()
for edge_and_weight in edges_and_weight:
nodes.add(edge_and_weight[0])
nodes.add(edge_and_weight[1])
nodes = sorted(list(nodes))
if not start_node in nodes:
print("Ungueltiger start Punk")
return
S = []
# Key: Node, Value: Laenge, Vorgaenger
columns = [dict.fromkeys(nodes, (None, None))]
columns[0][start_node] = (0, start_node)
while len(S) < len(nodes):
previous_column = columns[-1]
shortest_l_p = None
shortest_key = None
# Finde kleinsten in vorgaeniger liste
for key in remove_from_list(nodes, S):
l, p = previous_column[key]
if l == None:
continue
if shortest_l_p == None or l < shortest_l_p[0]:
shortest_l_p = (l, p)
shortest_key = key
# Knoten an S hinzufuegen
S.append(shortest_key)
print("Shortest: ", shortest_key, shortest_l_p)
# Finde verbundene knoten punkte
neighbours = [ew for ew in edges_and_weight if ew[0] == shortest_key or ew[1] == shortest_key]
# Entferne benachbarte welche y E (nodes - S)
neighbours_cleaned = []
for neighbour in neighbours:
detected_node = neighbour[0]
if detected_node == shortest_key:
detected_node = neighbour[1]
if detected_node in remove_from_list(nodes, S):
neighbours_cleaned.append(neighbour)
print("Neigbours:", neighbours_cleaned)
# Kopiere vorgaenige kolonne
new_column = previous_column.copy()
# Entferne abgeschlossene knoten
remove_from_dict(new_column, S)
columns.append(new_column)
print("neighbours_cleaned: " ,neighbours_cleaned)
# Fuer jeden nachbar
for v, w, weight in neighbours_cleaned:
y = v
s = w
if v == shortest_key:
y = w
s = v
y_column_data = previous_column[y]
if y_column_data[0] == None or y_column_data[0] > shortest_l_p[0] + weight:
# Setzte kuerzeren weg
new_column[y] = (shortest_l_p[0] + weight, shortest_key)
#print("Previous: ", previous_column)
#print("New: ", new_column)
print("S:", S)
print("------------------")
return columns, S
more_data = True
print("Abbruch mit allen Werten = 0")
start_point = input("Start knoten fuer Algorithmus:")
e_and_w = []
while more_data:
print("Daten für Punkt:", len(e_and_w))
a = input("Anfangsknoten:")
b = input("Endknoten:")
weight = int(input("Kantengewicht:"))
if a == "0" and b == "0" and weight == 0:
more_data = False
continue
e_and_w.append((a, b, weight))
cols, diS = dijkstra(e_and_w, start_point)
print("Knoten: (Distanz, Vorgaenger)")
for col in cols:
print(col)
print("S:", diS)
Code: Alles auswählen
# Author Joel Kessler V2
def e_randomvar(k_and_ps):
E_X, VAR_X, SD_X = 0, 0, 0
# Berechne E(X)
for k_and_p in k_and_ps:
k, p = k_and_p
E_X += k * p
# Berechne VAR(X)
for k_and_p in k_and_ps:
k, p = k_and_p
VAR_X += ((k - E_X) ** 2) * p
return E_X, VAR_X, VAR_X ** (1/2)
# Based on: https://www.johndcook.com/blog/2010/10/20/best-rational-approximation/
def farey(x, N):
# y = Ganzzahl faktor
y = 0
if x % 1 > 0:
y = x - (x % 1)
x = x % 1
if x == 0:
return y
a, b = 0, 1
c, d = 1, 1
while (b <= N and d <= N):
mediant = float(a+c)/(b+d)
if x == mediant:
if b + d <= N:
return "{}/{}".format(int(y * b+d) + a+c, b+d)
elif d > b:
return "{}/{}".format(int(y * d) + c, d)
else:
return "{}/{}".format(int(y * b) + a, b)
elif x > mediant:
a, b = a+c, b+d
else:
c, d = a+c, b+d
if (b > N):
return "{}/{}".format(int(y * d) + c, d)
else:
return "{}/{}".format(int(y * b) + a, b)
more_data = True
print("Abbruch mit allen Werten = esc, BRUECHE UNTERSTUETZT")
print("Ausgabe: E(X) / VAR(X) / SD(X):")
data = []
while more_data:
print("n-te Variable:", len(data))
k = input("k:")
p = input("P(X=k):")
if k == "esc" and p == "esc":
more_data = False
continue
data.append((float(eval(k)), float(eval(p))))
E_X, VAR_X, SD_X = e_randomvar(data)
print("------------")
print("E(X): ", farey(E_X, 1000), " -> ", round(E_X, 8))
EX_2 = VAR_X + (E_X ** 2)
print("E(X^2): ", farey(EX_2, 1000), " -> ", round(EX_2, 8))
print("VAR(X): ", farey(VAR_X, 1000), " -> ", round(VAR_X, 8))
print("SD(X): ", round(SD_X, 8))
Code: Alles auswählen
# Author Joel Kessler
def euclidean_extended(a, b):
x, y = a, b
if a < b:
print("a muss grösser als b sein. Vertausche diese.")
return [None, None, None, None]
top_rows = [[a, None, 1, 0], [b, a // b, 0, 1]]
print(top_rows[0])
print(top_rows[1])
breaker_step = 0
while breaker_step < 25:
step_row = [None, None, None, None]
breaker_step += 1
step_row[0] = top_rows[0][0] - top_rows[1][0] * top_rows[1][1]
if step_row[0] <= 0:
print(step_row)
break
step_row[1] = top_rows[1][0] // step_row[0]
step_row[2] = top_rows[0][2] - top_rows[1][2] * top_rows[1][1]
step_row[3] = top_rows[0][3] - top_rows[1][3] * top_rows[1][1]
print(step_row)
top_rows[0] = top_rows[1]
top_rows[1] = step_row
return top_rows[1]
in_a = int(input("a = "))
in_b = int(input("b = "))
ggt, _, x, y = euclidean_extended(in_a, in_b)
print("GGT:", ggt)
print("x:", x)
print("y:", y)
print("Diophantische Gleichung: " + str(in_a) + " * " + str(x) + " + " + str(in_b) + " * " + str(y) + " = 1")
print("Allgemein (k E N): " + str(in_a) + " * " + "(" + str(x) + " + " + str(in_b) + " * k) + " + str(in_b) + " * " + "(" + str(y) + " - " + str(in_a) + " * k) = 1")
Code: Alles auswählen
# Author Joel Kessler 2
def euclidean(a, b):
x, y = a, b
if a < b:
print("a muss grösser als b sein. Vertausche diese.")
return None
previous_row = [a, a // b, b, a - (a // b) * b]
breaker_step = 0
while breaker_step < 25:
print("{} = {} * {} + {}".format(previous_row[0],previous_row[1],previous_row[2],previous_row[3]))
breaker_step += 1
if previous_row[3] == 0:
return previous_row[2]
step_row = [previous_row[2], previous_row[2] // previous_row[3], previous_row[3], previous_row[2] - (previous_row[2] // previous_row[3]) * previous_row[3]]
if step_row[3] <= 0:
print("{} = {} * {} + {}".format(step_row[0],step_row[1],step_row[2],step_row[3]))
return step_row[2]
previous_row = step_row
return None
in_a = int(input("a = "))
in_b = int(input("b = "))
ggt = euclidean(in_a, in_b)
print("GGT:", ggt)
Code: Alles auswählen
# Author Ramon Stoffel
def euler_phi_numbers(n):
zn = [x for x in range(n)]
relatives_primes = []
for i in zn:
if ggt(n, zn[i])==1:
relatives_primes.append(zn[i])
else:
continue
return relatives_primes
def ggt(x , y):
if y == 0:
return x
return ggt(y, x % y)
def modular_invers(a, n):
v = 1
d = a
u = (a == 1)
t = 1-u
if (t == 1):
c = n % a
u = n // a
while c != 1 and t == 1:
q = d // c
d = d % c
v = v + q*u
t = (d != 1)
if (t == 1):
q = c // d
c = c % d
u = u + q*v
u = v*(1 - t) + t*(n - u)
return u
n = int(input("Geben Sie Z-n ein: "))
print("------------")
res = euler_phi_numbers(n)
print("EULERISCHE PHI FUNKTION: ",len(res))
print("------------")
print("TEILERFREMDE-ELEMENTE / Z-STERN: ",res)
mod_inv_list = []
for i in range(len(res)):
inv_mod = modular_invers(res[i],n)
if inv_mod == True:
mod_inv_list.append(1)
else:
mod_inv_list.append(inv_mod)
print("------------")
print("INVERSE VON TEILERFREMDEN_ELEMENTEN AUS Z-STERN: ",mod_inv_list)
Code: Alles auswählen
# Author Joel Kessler
def cross_product(A, B):
res = []
for b in B:
for a in A:
res.append((a, b))
return res
A = []
B = []
print("Abbruch mit allen Werten = esc")
print("Menge A:")
more_data = True
while more_data:
a = input("a{}:".format(len(A)))
if a == "esc":
more_data = False
continue
A.append(a)
print("Menge B:")
more_data = True
while more_data:
b = input("b{}:".format(len(B)))
if b == "esc":
more_data = False
continue
B.append(b)
A = sorted(set(A))
B = sorted(set(B))
print("--------")
print(sorted(cross_product(A, B)))Code: Alles auswählen
# Author Joel Kessler
def remove_from_list(l1, l2):
lr = list(l1)
for e in l2:
if e in lr:
lr.remove(e)
return lr
def kruskal_algorithm(edges_and_weights):
V = set()
edges_grouped = dict()
for edge_and_weight in edges_and_weights:
V.add(edge_and_weight[0])
V.add(edge_and_weight[1])
if edge_and_weight[2] not in edges_grouped:
edges_grouped[edge_and_weight[2]] = [(edge_and_weight[0], edge_and_weight[1]), ]
else:
edges_grouped[edge_and_weight[2]].append((edge_and_weight[0], edge_and_weight[1]))
edges_sorted_indecies = sorted(edges_grouped)
V = sorted(list(V))
R = [[node] for node in V]
T = []
w_T = 0
# Wiederhole bis alle Knoten besucht
while V != sorted(list(sum(T, ()))):
# Gewicht, x E R[a], y E R[b]
selected_edge = None
# Kante mit minimalem gewicht finden
for key in edges_sorted_indecies:
for i in range(0, len(edges_grouped[key])):
v, w = edges_grouped[key][i]
# Finde klassen von v und w
v_class = None
w_class = None
for R_class in R:
if v in R_class:
v_class = R_class
elif w in R_class:
w_class = R_class
if w_class == None or v_class == None:
continue
if v_class != w_class:
# Wenn klasse gefunden, fuege alle elemente aus klasse w zu klasse von v hinzu
for w_el_i in range(0, len(w_class)):
v_class.append(w_class[0])
w_class.remove(w_class[0])
# Entferne leere klasse
if len(w_class) == 0:
R.remove(w_class)
selected_edge = (key, v, w)
# Loesche selektierte kante
edges_grouped[key].remove(edges_grouped[key][i])
break
if selected_edge != None:
break
if selected_edge == None:
return R, T, w_T
w_T += selected_edge[0]
T.append((selected_edge[1], selected_edge[2]))
print("T added: ", (selected_edge[1], selected_edge[2]))
print("w(T) added: ", selected_edge[0])
print("R classes: ", R)
print("------------")
more_data = True
print("Abbruch mit allen Werten = 0")
e_and_w = []
while more_data:
print("Daten für Punkt:", len(e_and_w))
a = input("Anfangsknoten:")
b = input("Endknoten:")
weight = int(input("Kantengewicht:"))
if a == "0" and b == "0" and weight == 0:
more_data = False
continue
e_and_w.append((a, b, weight))
R, T, w_T = kruskal_algorithm(e_and_w)
print("------------")
print("R: ", R)
print("T: ", T)
print("w(T): ", w_T)
Code: Alles auswählen
# Author Joel Kessler
def set_values(A, B):
AANDB = set([a for a in A if a in B])
AORB = A.union(B)
ADIFFB = set([a for a in A if a not in B])
BDIFFA = set([b for b in B if b not in A])
return AANDB, AORB, ADIFFB, BDIFFA
print("Abbruch mit allen Werten = esc")
print("A:")
more_data = True
A = []
while more_data:
a = input("a{}:".format(len(A)))
if a == "esc":
more_data = False
continue
A.append(a)
more_data = True
B = []
while more_data:
b = input("b{}:".format(len(B)))
if b == "esc":
more_data = False
continue
B.append(b)
AANDB, AORB, ADIFFB, BDIFFA = set_values(set(A), set(B))
print("A ∩ B: ", sorted(AANDB))
print("A ∪ B: ", sorted(AORB))
print("A \ B:", sorted(ADIFFB))
print("B \ A:", sorted(BDIFFA))Code: Alles auswählen
# Author Joel Kessler
approx_decimal = 100000
def farey(x, N):
a, b = 0, 1
c, d = 1, 1
while (b <= N and d <= N):
mediant = float(a+c)/(b+d)
if x == mediant:
if b + d <= N:
return a+c, b+d
elif d > b:
return c, d
else:
return a, b
elif x > mediant:
a, b = a+c, b+d
else:
c, d = a+c, b+d
if (b > N):
return c, d
else:
return a, b
def gauss_jordan(a):
n = len(a)
x = [0 for _ in range(0, len(a))]
# Applying Gauss Elimination
for i in range(n):
if a[i][i] == 0.0:
print("Divide by zero detected!")
return
for j in range(i+1, n):
ratio = a[j][i]/a[i][i]
for k in range(n+1):
a[j][k] = a[j][k] - ratio * a[i][k]
# Back Substitution
x[n-1] = a[n-1][n]/a[n-1][n-1]
for i in range(n-2,-1,-1):
x[i] = a[i][n]
for j in range(i+1,n):
x[i] = x[i] - a[i][j]*x[j]
x[i] = x[i]/a[i][i]
return x
def pagerank_algorithm(edges, d):
V = sorted(set(sum(edges, ())))
N = len(V)
res = []
#print(["PR[{}]".format(i) for i in V])
rhs = []
for i in V:
sum_of_pr = []
res_row = [0 for _ in V]
res_row[V.index(i)] = 1
# Endknoten potential_j[1]
j_to_is = [potential_j for potential_j in edges if potential_j[1] == i]
#print(i, "->", j_to_is)
for j_to_i in j_to_is:
# j = j_to_i[0]
c_j = len([j_outgoing for j_outgoing in edges if j_outgoing[0] == j_to_i[0]])
res_row[V.index(j_to_i[0])] += d * (1 / c_j) * -1
if c_j == 1:
sum_of_pr.append("PR[{}]".format(j_to_i[0]))
else:
sum_of_pr.append("PR[{}] * (1/{})".format(j_to_i[0], c_j))
sum_of_pr = " + ".join(sum_of_pr)
if sum_of_pr == "":
sum_of_pr = "0"
sum_of_pr = "({})".format(sum_of_pr)
#d * sum_of_pr + (1 - d) * (1 / N)
d_approx = farey(d, approx_decimal)
one_sub_d_approx = farey((1 - d), approx_decimal)
pr_node = "PR[{}] = ({}/{}) * {} + ({}/{}) * (1/{})".format(i, d_approx[0], d_approx[1], sum_of_pr, one_sub_d_approx[0], one_sub_d_approx[1], N)
print(pr_node)
rhs.append((1 - d) * (1 / N))
res.append(res_row)
#for row in res:
# print(row, rhs[res.index(row)])
for rhs_index in range(0, len(rhs)):
res[rhs_index].append(rhs[rhs_index])
res_eval = gauss_jordan(res)
# Displaying solution
print("Loesung: ")
#sorted_res_eval = dict.fromkeys(res_eval)
for x_i in range(0, len(res_eval)):
x = res_eval[x_i]
approx_x = farey(x, approx_decimal)
#print("PR[{}] = ({}/{}) = {}".format(V[x_i], approx_x[0], approx_x[1], x))
#sorted_res_eval[res_eval[x_i]] = ["PR[{}]".format(V[x_i]), "({}/{})".format(approx_x[0], approx_x[1])]
print("PR[{}] = ({}/{}) = {}".format(str(V[x_i]), approx_x[0], approx_x[1], x))
"""print("Sortierte Loesung: ")
for key in sorted(sorted_res_eval.keys(), reverse=True):
print("{} = {} = {}".format(sorted_res_eval[key][0], sorted_res_eval[key][1], key))"""
return res_eval
more_data = True
edges = []
print("Abbruch mit allen Werten = esc")
d = float(eval(input("Daempfungsfaktor d: ")))
while more_data:
print("Daten für Punkt:", len(edges))
a = input("Von Knoten:")
b = input("Zu Knoten:")
if a == "esc" and b == "esc":
more_data = False
continue
edges.append((a, b))
R = pagerank_algorithm(edges, d)
#pagerank_algorithm([("1", "3"), ("3", "6"), ("3", "4"), ("3", "2"), ("5", "2"), ("2", "1"), ("4", "2")], 4/5)
Code: Alles auswählen
def powerset(fullset):
# See: https://www.delftstack.com/de/howto/python/powerset-python/
listsub = list(fullset)
subsets = []
for i in range(2**len(listsub)):
subset = []
for k in range(len(listsub)):
if i & 1<<k:
subset.append(listsub[k])
subsets.append(sorted(subset))
return subsets
print("Abbruch mit allen Werten = esc")
print("Menge:")
more_data = True
A = []
while more_data:
a = input("a{}:".format(len(A)))
if a == "esc":
more_data = False
continue
A.append(a)
subsets = powerset(set(A))
print(len(subsets), subsets)Code: Alles auswählen
# Author Joel Kessler 2
def remove_from_list(l1, l2):
lr = list(l1)
for e in l2:
if e in lr:
lr.remove(e)
return lr
def prim_algorithm(edges_and_weights, start_node):
V = set()
edges_grouped = dict()
for edge_and_weight in edges_and_weights:
V.add(edge_and_weight[0])
V.add(edge_and_weight[1])
if edge_and_weight[2] not in edges_grouped:
edges_grouped[edge_and_weight[2]] = [(edge_and_weight[0], edge_and_weight[1]), ]
else:
edges_grouped[edge_and_weight[2]].append((edge_and_weight[0], edge_and_weight[1]))
edges_sorted_indecies = sorted(edges_grouped)
V = sorted(list(V))
if not start_node in V:
print("Ungueltiger start Punkt")
return
S = [start_node]
V.remove(start_node)
T = []
w_T = 0
num_nodes = len(V) + 1
while len(S) < num_nodes:
# Gewicht, x E S, y E (V - S)
selected_edge = None
# Kante mit minimalem gewicht finden
for key in edges_sorted_indecies:
for i in range(0, len(edges_grouped[key])):
v, w = edges_grouped[key][i]
if (v in S and w in V) or (w in S and v in V):
x = v
y = w
if y in S:
x = w
y = v
selected_edge = (key, x, y)
edges_grouped[key].remove(edges_grouped[key][i])
break
if selected_edge != None:
break
# Menge S hinzuefuegen
S.append(selected_edge[2])
V.remove(selected_edge[2])
T.append((selected_edge[1], selected_edge[2]))
w_T += selected_edge[0]
print("S added: ", selected_edge[2])
print("T added: ", (selected_edge[1], selected_edge[2]))
print("w(T) added: ", selected_edge[0])
return S, T, w_T
more_data = True
print("Abbruch mit allen Werten = 0")
start_point = input("Start knoten fuer PRIM Algorithmus:")
e_and_w = []
while more_data:
print("Daten für Punkt:", len(e_and_w))
a = input("Anfangsknoten:")
b = input("Endknoten:")
weight = int(input("Kantengewicht:"))
if a == "0" and b == "0" and weight == 0:
more_data = False
continue
e_and_w.append((a, b, weight))
S, T, w_T = prim_algorithm(e_and_w, start_point)
print("------------")
print("S: ", S)
print("T: ", T)
print("w(T): ", w_T)
Code: Alles auswählen
# Author Joel Kessler und Ramon Stoffel
def euler_phi_numbers(n):
zn = [x for x in range(n)]
relatives_primes = []
for i in zn:
if ggt(n, zn[i])==1:
relatives_primes.append(zn[i])
else:
continue
return relatives_primes
def ggt(x , y):
if y == 0:
return x
return ggt(y, x % y)
def modular_invers(a, n):
v = 1
d = a
u = (a == 1)
t = 1-u
if (t == 1):
c = n % a
u = n // a
while c != 1 and t == 1:
q = d // c
d = d % c
v = v + q*u
t = (d != 1)
if (t == 1):
q = c // d
c = c % d
u = u + q*v
u = v*(1 - t) + t*(n - u)
return u
def quadratic_remainders(n):
remainders = []
Z_n = euler_phi_numbers(n)
for i in Z_n:
remainders.append(i ** 2 % n)
quadratic_remainders_dict = dict.fromkeys(sorted(Z_n))
# Leere listen erstellen
for key in quadratic_remainders_dict.keys():
quadratic_remainders_dict[key] = []
# Ordne x quadrate den Restklassen zu
for remainder_index in range(0, len(remainders)):
quadratic_remainders_dict[remainders[remainder_index]].append(Z_n[remainder_index])
# Entferne leere Restklassen
for key in list(quadratic_remainders_dict.keys()):
if quadratic_remainders_dict[key] == []:
quadratic_remainders_dict.pop(key)
return remainders, quadratic_remainders_dict, Z_n
n = int(input("n = "))
r, qrd, Z_n = quadratic_remainders(n)
print("Z({})*: {}".format(n, Z_n))
print("x-Quadrate:", r)
print("Restklassen:", qrd)
Code: Alles auswählen
#Author Joel Kessler
def square_and_multiply_algorithm(basis, exponent, modulo):
x = basis
ex_bin = str(bin(exponent))[2:].replace("1", "QM").replace("0", "Q")[2:]
y_step = x
print(str(y_step), end=" -> ")
for letter in ex_bin:
if y_step >= modulo:
print(str(y_step) + " mod " + str(modulo), end=" -> ")
y_step = y_step % modulo
if letter == "Q":
y_step = y_step ** 2
print(str(y_step) + " Q ", end=" -> ")
if letter == "M":
y_step = y_step * x
print(str(y_step) + " M ", end=" -> ")
print(str(y_step) + " mod " + str(modulo))
if y_step >= modulo:
y_step = y_step % modulo
return y_step
basis, exponent, modulo = int(input("basis = ")), int(input("exponent = ")), int(input("modulo = "))
mod_val = square_and_multiply_algorithm(basis, exponent, modulo)
print("{}^{} mod {} = {}".format(basis, exponent, modulo, mod_val))