質問編集履歴

追加

2020/11/12 22:26

投稿

apeirogon0813

スコア117

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -183,3 +183,361 @@
 ご教示願います。
+```python
+import random
+import networkx as nx
+import matplotlib.pyplot as plt
+import copy
+#要素が重複しているか
+def has_duplicates(seq):
+    return len(seq) == len(set(seq))
+def create_volumes(n):
+    #重複しないレコードの作成
+    V = random.sample(range(5,260), k=n)
+    #観測されるボリューム集合の生成
+    W = copy.copy(V)
+    for i in range(N-1):
+        W.append(V[i]+V[i+1])
+    return V, W
+#候補解から生成されるボリュームを観測したボリュームと比較
+def compare_volumes(S, W):
+    T = set()
+    #観測されるボリューム集合の生成
+    for s in S:
+        w = copy.copy(s)
+        for i in range(N-1):
+            w.append(s[i]+s[i+1])
+        if set(w) == set(W):
+            #print(tuple(s))
+            T.add(tuple(s))
+    return T
+#１つ以上重複しているボリュームを作成(レコードは重複していない)
+def create_duplicates(n):
+    data = create_volumes(n)
+    if has_duplicates(data[1]): #重複していないならば
+        return create_duplicates(n)
+    else:
+        return data
+def create_no_duplicates(n):
+    data = create_volumes(n)
+    #print(data[1])
+    if has_duplicates(data[1]):
+        return data
+    else:
+        return create_duplicates(n)
+Ans = []
+N = 26 #攻撃者は既知
+result = create_duplicates(N)
+#result = create_no_duplicates(N)
+V = result[0] #復元したいレコード
+print("V = " + str(V))
+print("W = " + str(result[1]))
+W = list(set(result[1])) #攻撃者が観測するボリュームの集合
+#要素を昇順に
+W.sort()
+print("昇順W = " + str(W) + " ( |W| = " + str(len(W)) +" )")
+G = nx.Graph()
+#step1 ２頂点の和がボリュームに含まれているのならエッジを追加
+#連結しているて頂点のみをエッジごと抽出
+n = len(W)
+for i in range(n-2):
+    for j in range(i+1,n-1):
+        if W[i] + W[j] in W:
+            G.add_edge(W[i], W[j])
+print("存在する枝 = " + str(G.edges))
+print("抽出されたボリューム(" + str(len(G.nodes)) +"/" + str(len(W)) +") = " + str(G.nodes))
+print(list(G.neighbors(W[0])))
+#step2 確定レコード選別する
+RNodes = [W[0], W[1]] #レコードは重複しない仮定より1,2番目に小さいボリュームはレコードである
+for i in range(2, N):
+    for j in range(i):
+        #print("W[i] - W[j] = " + str(W[i]) + " - " + str(W[j]))
+        if W[i] - W[j] in W and W[i] != 2 * W[j] : #あるボリュームが確定レコード同士の和である時(その要素が隣同士orレコードであるor両方)
+            break
+        #else: 和でない場合は次に進める
+    #最終的にそのボリュームを生成する確定レコードの２要素の和が存在しない場合、そのボリューム確定レコード
+    if j == i-1:
+        RNodes.append(W[i])
+print("確定レコード = " + str(RNodes))
+#step3　確定レコードである頂点を通る経路長＝N-1である経路
+S = []
+#//集合の中にリストの集合
+l = list(G.neighbors(W[0]))
+for i in l: #一次元配列だとループが回せないため、二次元配列にしておく
+    S.append([W[0],i])
+def right_shift(S,G):
+    #print("S = " + str(S))
+    for i in range(N-2): #解の長さがNになるまで
+        T = []
+        for s in S: #解の数
+            if len(s) != N:
+                right_num = len(s) - 1
+                l = list(G.neighbors(s[right_num]))#一番右の要素と隣合うノードを取得
+                for node in l:
+                    if node not in s: #同じレコードは存在しないかの判定
+                        C = copy.copy(s)
+                        C.append(node)
+                        if C not in T:
+                            T.append(C)
+            T.append(s)#右に拡張できるがそのノードが終点である可能性があるため
+        #print(T)
+        S = copy.copy(T)
+        #print("S = " + str(S))
+    return S
+#S = right_shift(S)
+#左に拡張
+def left_shift(S,G):
+    for i in range(N-2):
+        T = []
+        for s in S:
+            #print("s = " + str(s))
+            if len(s) != N:
+                l = list(G.neighbors(s[0]))
+                for node in l:
+                    if node not in s: #同じレコードは存在しないかの判定
+                        C = copy.copy(s)
+                        C.insert(0,node) #先頭に要素を追加
+                        if C not in T:
+                            T.append(C)
+            T.append(s)
+        S = copy.copy(T)
+        #print("s = " + str(S))
+    return S
+#step4　確定コードが解に含まれているか 現段階では確定レコードを通る効率的なアルゴリズムが考えられていないため
+def confirm(S):
+    T = []
+    for s in S:
+        if len(s) == N:
+            for i in range(len(RNodes)):
+                if RNodes[i] not in s:
+                    break
+            if i == len(RNodes)-1:
+                T.append(s)
+    return T
+T = copy.copy(S)
+T = right_shift(T,G)
+T = left_shift(T,G)
+S = left_shift(S,G)
+S = right_shift(S,G)
+#print("解候補 = " + str(T))
+print("解の数1 = " + str(len(T)))
+T = confirm(T)
+S = confirm(S)
+#print("解候補選別T = " + str(T))
+#print("解候補選別S = " + str(S))
+print("解の数2 = " + str(len(T)))
+#step5 解からボリュームを計算し比較
+G1 = compare_volumes(T, W)
+#print("G1 = " + str(G1))
+G2 = compare_volumes(S, W)
+#print("G2 = " + str(G2))
+G3 = G1|G2
+print("候補解(" + str(len(G3)) + "個) = " + str(G3))
+print("真の解 = " + str(V))
+```