0

I am writing a little program to create a list of permutations. I read about the algorithm on wikipedia.

My algorithm basically takes an initially sorted list of numbers, and permutes it in place. It then appends this new permutation to a list. When all permutations are found, it returns the list of lists containing all the permutations. It is very good at printing out the expected results, but when I try to add those results to a list, things get a little funny.

I noticed that every time I find the next permutation and append it to, the previous list elements get updated to the new permutation. So, at the end of it all, what gets returned is a list containing a bunch of copies of the same permutation (exactly the last permutation).

I've read that Python is pass by value, pass by reference and I've also read that it's neither. I'm not smart enough to argue with any of those people, but I am wondering why my program is doing this, and how to remedy it:

def lexi_order(nums):

    permutations = []
    length = len(nums)


    while True:

        # find largest index i such that nums[i] < nums[i + 1]
        exists = False
        for j, elem in enumerate(nums):
            # check if last element
            if j == length - 1:
                break

            if elem < nums[j + 1]:
                i = j
                exists = True

        if not exists:
            break

        # find largest index k, such that i < k AND nums[i] < nums[k]
        for j in range(i + 1, length):
            if nums[j] > nums[i]:
                k = j

        # swap order of nums[i] and nums[k]
        nums[i], nums[k] = nums[k], nums[i]

        # reverse order of elements starting at position i+1
        to_reverse = nums[i+1:][::-1]
        nums[i+1::] = to_reverse

        permutations.append(nums)
        print(permutations)

    return permutations
rocksNwaves
  • 5,331
  • 4
  • 38
  • 77
  • You never copy ``nums`` -- there is only *a single* object that you repeatedly modify and append to ``permutations``. – MisterMiyagi Jan 20 '20 at 22:10
  • 2
    Python is always pass-by-reference. They way it helps users to *sometimes* avoid pass-by-reference related bugs is by making certain common types immutable (int, float, str, tuple). An immutable type helps because once your variable is referencing an instance of an immutable type, you can be certain that the value it is referencing will not change. You do need to be aware of which types are and are not immutable in order to write smart code in python however. – Hymns For Disco Jan 20 '20 at 22:18
  • @MisterMiyagi Yes, in a way. It goes well with one of the answers below which states that I need to make a copy for every new permutation. However, one piece is missing for me, which is in my comment to that answer: Let's say I say `temp_nums = nums`, then according to your link and also the article I read, I'm not making a copy. So, I have to learn how to copy something instead of giving it new names. – rocksNwaves Jan 20 '20 at 22:18
  • @HymnsForDisco Hmm, that makes sense. Must be why this is my first time running into this sort of issue. I was passing by reference all along, but the 'immutability' of the variables I was using made me think I was doing everything by value. Thanks! – rocksNwaves Jan 20 '20 at 22:20
  • 2
    calling `list(my_list)` is the standard way to make a shallow copy of a list. "copying" something is not as straight forward as you may think. Look up resources about shallow vs deep copy in python, and copying objects with the `copy` module – Hymns For Disco Jan 20 '20 at 22:21

3 Answers3

1

When you append nums to permutations, you are appending a reference to it, not copying all of the data over. When you modify nums, it gets modified everywhere. Python is pass by reference. If you make a change to a variable (not to be confused with reassigning it), that change will be reflected everywhere.

Michael Bianconi
  • 5,072
  • 1
  • 10
  • 25
  • You have to be really careful with terminology here, because reassigning an element of a list will actually *change* the list. – Mark Ransom Jan 20 '20 at 23:21
1

You're modifying the input (nums) in place each iteration through the loop, and then you keep adding a reference to the input to permutations. To fix it, make a copy of nums at the beginning of the loop and use it instead of the original everywhere inside it.

Joseph Sible-Reinstate Monica
  • 45,431
  • 5
  • 48
  • 98
  • So, I read that that if I do something like `temp_list = nums`, that I am actually just giving the same object two names. I read that if I do something to `temp_list`, it will be reflected in `nums` as well. An example is given here: https://jeffknupp.com/blog/2012/11/13/is-python-callbyvalue-or-callbyreference-neither/. I tested this out to see if it was true, and it worked. So how do i make a distinct "copy"? – rocksNwaves Jan 20 '20 at 22:12
1

You need to make a copy of the passed nums, otherwise you are working on the passed reference. E.g.

def lexi_order(nums):

    permutations = []

    nums = list(nums) # We are now working on a copy, and won't mutate the original whatsoever.
    length = len(nums)
    ...
Jordan Brière
  • 1,045
  • 6
  • 8