我编写了一个KargerMinCut函数，其中用Python编写了一个随机函数，但在同一运行中得到了相同的结果。如果我重新启动该功能，则会打印不同的结果。
这是代码
import random
with open('test.txt') as f:
#kargerMinCut
#a = [[int(x) for x in ln.split()] for ln in f]
data_set = []
for ln in f:
line = ln.split()
if line:
a = [int(x) for x in line]
data_set.append(a)
def choose_random_edge(data):
a = random.randint(0,len(data)-1)
b = random.randint(1,len(data[a])-1)
return a,b
def compute_nodes(data):
data_head = []
for i in xrange(len(data)):
data_head.append(data[i][0])
return data_head
def find_index(data_head,data,u,v):
index = data_head.index(data[u][v])
return index
def replace(data_head,data,index,u):
for i in data[index][1:]:
index_index = data_head.index(i)
for position,value in enumerate(data[index_index]):
if value == data[index][0]:
data[index_index][position] = data[u][0]
return data
def merge(data):
u,v = choose_random_edge(data)
print u,v
data_head = compute_nodes(data)
index = find_index(data_head,data,u,v)
data[u].extend(data[index][1:])
#print data
data = replace(data_head,data,index,u)
#print data
data[u][1:] = [x for x in data[u][1:] if x!=data[u][0]]
#print data
data.remove(data[index])
#print data
return data
def KargerMinCut(data):
while len(data) >2:
data = merge(data)
#print data
num = len(data[0][1:])
print num
#KargerMinCut(data_set)
这是test.txt
1 2 3 4 7
2 1 3 4
3 1 2 4
4 1 2 3 5
5 4 6 7 8
6 5 7 8
7 1 5 6 8
8 5 6 7
编辑12-28-2016
我通过添加输入数据的本地副本在合并和替换中修改了我的代码。我不知道我是否正确。
这是代码
def replace(data_head,data,index,u):
data1 = data
for i in data[index][1:]:
index_index = data_head.index(i)
for position,value in enumerate(data[index_index]):
if value == data[index][0]:
data1[index_index][position] = data[u][0]
return data1
def merge(data1):
data = data1
u,v = choose_random_edge(data)
#print u,v
data_head = compute_nodes(data)
index = find_index(data_head,data,u,v)
data[u].extend(data[index][1:])
#print data
data2 = replace(data_head,data,index,u)
#print data
data2[u][1:] = [x for x in data2[u][1:] if x!=data2[u][0]]
#print data
data2.remove(data2[index])
#print data
return data2
但是当我运行
merge(data_set)时，我发现我再次更改了输入。为什么以及我该怎么办？有人可以给我一些线索吗？Here is the output of merge and data_set
通过添加所需的输出图像进行编辑
这是图片：
wanted output
我想循环计算
KargerMinCut(data_set)并选择最小值作为输出。如您所见，当我循环计算
KargerMinCut(data_set)时，我应该得到不同的结果，而不是相同的结果，这是错误的。我知道我在调用KargerMinCut(data_set)时更改了输入数据，但是我不知道如何解决它。在1/7/2017解决的问题
我在顶部使用
import copy，在data = copy.deepcopy(data)的第一行中使用KargerMinCut()。添加calc_num()功能。这是输出：
calc_number(data_set,20)
17
calc_number(data_set,2)
17
calc_number(data_set,15)
20
calc_number(data_set,15)
17
这是代码：
随机导入
导入副本
with open('kargerMinCut.txt') as f:
#kargerMinCut
#a = [[int(x) for x in ln.split()] for ln in f]
data_set = []
for ln in f:
line = ln.split()
if line:
a = [int(x) for x in line]
data_set.append(a)
def choose_random_edge(data):
a = random.randint(0,len(data)-1)
b = random.randint(1,len(data[a])-1)
return a,b
def compute_nodes(data):
data_head = []
for i in xrange(len(data)):
data_head.append(data[i][0])
return data_head
def find_index(data_head,data,u,v):
index = data_head.index(data[u][v])
return index
def replace(data_head,data,index,u):
for i in data[index][1:]:
index_index = data_head.index(i)
for position,value in enumerate(data[index_index]):
if value == data[index][0]:
data[index_index][position] = data[u][0]
return data
def merge(data):
u,v = choose_random_edge(data)
#print u,v
data_head = compute_nodes(data)
index = find_index(data_head,data,u,v)
data[u].extend(data[index][1:])
#print data
data = replace(data_head,data,index,u)
#print data
data[u][1:] = [x for x in data[u][1:] if x!=data[u][0]]
#print data
data.remove(data[index])
#print data
return data
def KargerMinCut(data):
data = copy.deepcopy(data)
while len(data) >2:
data = merge(data)
#print data
num = len(data[0][1:])
return num
#KargerMinCut(data_set)
def calc_number(data,iteration):
list = []
for i in xrange(iteration):
list.append(KargerMinCut(data))
return min(list)
最佳答案
data_set是一个列表，列表是可变的。如果遵循函数调用：KargerMinCut调用merge，而merge调用replace。 merge和replace都对传递的列表进行突变。merge在行中对其进行变异
data[u].extend(data[index][1:])
replace在行中对其进行变异data[index_index][position] = data[u][0]
在单个会话中，第一次调用
KargerMinCut(data_set)时，它将更改data_set，将输入更改为第二个调用KargerMinCut(data_set)。这就是两个函数调用行为不同的原因。如果不希望这样做，则可以通过创建
merge的本地副本来启动每个功能replace和data。