为什么我第二次在同一运行中直接获得相同的结果，而没有在python中运行随机函数

Question

我写了一个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

我通过添加输入数据的本地副本，在 Merge 和和中修改了代码。我不知道我是否对。

这是代码

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)时，我发现我再次更改了输入。为什么，我该怎么办？有人可以给我一些线索吗？

这是Merge和Data_set的输出

通过添加想要的输出图像编辑

这是图像：想要输出

我想循环计算KargerMinCut(data_set)并选择最小值作为输出。如您所见，当我循环计算KargerMinCut(data_set)时，我应该得到不同的结果，而不是错误的结果。我知道我在调用KargerMinCut(data_set)时会更改输入数据，但是我不知道如何修复它。在2017年1月7日解决的问题我在KargerMinCut()的第一行中使用import copy，在顶部使用data = copy.deepcopy(data)。添加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)

Answer 1

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)。这就是为什么两个函数调用行为不同的原因。

如果这不是可取的，则可以通过创建data的本地副本来启动每个功能merge和replace。

Answer 2

def KargerMinCut(data):
while len(data) > 2:  #here is the problem
    data = merge(data)
    # print data
num = len(data[0][1:])
print num

问题在第二行。

在第二次致电kargermincut len（数据）> 2中，它只会再次打印出相同的数字。