python - 字符串置换。存储在数组中会返回相同的一组排列？

Question

更新:见下行除非我遗漏了什么？

from array import array

def string_permute(ar, lo, hi, result):
    if lo == hi:
        # print ar # this gives correct permutated output, howcome result isn't able to store that?
        result.append(ar)
    else:
        for index in xrange(lo, hi+1):
            ar[index], ar[lo] = ar[lo], ar[index]
            string_permute(ar, lo+1, hi, result)
            ar[index], ar[lo] = ar[lo], ar[index]
    return result

if __name__ == "__main__":
    f = array('c', '1234')
    result = []
    string_permute(f, 0, len(f)-1, result)
    print result

输出:

[array('c', '1234'), array('c', '1234'), array('c', '1234'), array('c', '1234'), array('c', '1234'), array('c', '1234'), array('c', '1234'), array('c', '1234'), array('c', '1234'), array('c', '1234'), array('c', '1234'), array('c', '1234'), array('c', '1234'), array('c', '1234'), array('c', '1234'), array('c', '1234'), array('c', '1234'), array('c', '1234'), array('c', '1234'), array('c', '1234'), array('c', '1234'), array('c', '1234'), array('c', '1234'), array('c', '1234')]

预期输出:

array('c', '1234') array('c', '1243') array('c', '1324') array('c', '1342') array('c', '1432') array('c', '1423') array('c', '2134') array('c', '2143') array('c', '2314') array('c', '2341') array('c', '2431') array('c', '2413') array('c', '3214') array('c', '3241') array('c', '3124') array('c', '3142') array('c', '3412') array('c', '3421') array('c', '4231') array('c', '4213') array('c', '4321') array('c', '4312') array('c', '4132') array('c', '4123')

我尝试传入 result = result or [] 然后做一个

result += string_permute(ar, lo+1, hi, result)
return result #at the end of loop

但这也会适得其反，并且输出相同。我不知道为什么。不是因为这个 array 我也单独用一个列表试过。

---

正如下面的一个答案中提到的，我使用了一个列表。

def string_permute(ar, lo, hi, result):
    if lo == hi:
        result.append(ar[:])  #why does this work and result.append(ar) doesn't?
        print ar
    else:
        for index in xrange(lo, hi+1):
            ar[index], ar[lo] = ar[lo], ar[index]
            string_permute(ar, lo+1, hi, result)
            ar[index], ar[lo] = ar[lo], ar[index]
    return result

if __name__ == "__main__":
    f = array('c', '1234').tolist()  #just made it into a list
    result = []
    string_permute(f, 0, len(f)-1, result)
    print result

问:为什么这行得通而 result.append(ar) 不行？

Answer 1

您没有为数组对象制作副本。因此，每次您尝试修改数组时，它都会随着每次函数调用而改变。

每次递归调用时，为数组对象复制一份。

import copy

string_permute(copy.copy(ar), lo+1, hi, result)