user2290820 user2290820 - 6 months ago 9
Python Question

string permutation. storing in an array returns same set of permutations?

UPDATED:see below line
Unless I am missing something?

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


outputs:

[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')]


expected output:

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')


I tried passing in
result = result or []
and then doing a

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


but that too is counter productive and outputs the same. I don't know why.
it is not because of this
array
I also tried it solely with a list.




As mentioned in one of the answers below, I used a list instead.

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


Q: why does this work and
result.append(ar)
doesn't?

Answer

You are modifying ar inplace, so you end up with result containing multiple copies of same object. Changing result.append(ar) to result.append(ar[:]) in string_permute solves the problem.