user2290820 - 2 years ago 68
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?

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.