python - 为什么我在第二次运行中直接得到相同的结果而不在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)

这是测试.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

已编辑2016 年 12 月 28 日

我通过添加输入数据的本地副本修改了合并和替换中的代码。不知道我说的对不对。

这是代码

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) 时我已经更改了输入数据，但我不知道如何修复它。问题已于 2017 年 1 月 7 日解决我在顶部使用 import copy，在 KargerMinCut() 的第一行使用 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]

在单个 session 中，您第一次调用 KargerMinCut(data_set)它变异了data_set ，将输入更改为第二次调用 KargerMinCut(data_set) 。这就是两个函数调用的行为不同的原因。

如果这不合需要，您可以启动每个函数 merge和replace通过创建 data 的本地副本.