Traversing a Python list and making in-place changes

Question

My task is to remove all instances of one particular element ('6' in this example) and move those to the end of the list. The requirement is to traverse a list making in-line changes (creating no supplemental lists).

Input example: [6,4,6,2,3,6,9,6,1,6,5] Output example: [4,2,3,9,1,5,6,6,6,6,6]

So far, I have been able to do this only by making supplemental lists (breaking the task's requirements), so this working code is not allowed:

def shift_sixes(nums):
    b = []
    c = 0
    d = []

   for i in nums:
    if i == 6:
        b.insert(len(nums),i)
    elif i != 6:
        c = c +1
        d.insert(c,i)

   ans = d + b
   return ans

I've also tried list.remove() and list.insert() but have gotten into trouble with the indexing (which moves when I insert() then move the element to the end): For example -

a = [6,4,6,2,3,6,9,6,1,6,5]
  def shift_sixes(nums):
    for i in nums:
        if i == 6:
            nums.remove(i)
            nums.insert(nums[len(nums)-1], 0)
        elif i != 0:
            i
 shift_sixes(a)

Additionally, I have tried to use the enumerate() function as follows, but run into problems on the right hand side of the b[idx] assigment line:

for idx, b in enumerate(a):
     a[idx] = ???

Have read other stackoverflow entries here, here and here, but they do not tackle the movment of the element to one end.

Would appreciate any help on this list traversal / inplace switching issue. Many thanks.

---

EDIT @eph - thank you. this is indeed an elegant response. I am sure it will pass my 'no new list' requirement? I surely intend to learn more about lambda and its uses @falsetru - thank you for the reminder of the append/pop combination (which I tried to do in my original query via list.remove() and list.insert() @tdelaney - thank you as well. somehow your response is closest to what I was attempting, but it seems not to pass the test for [0, 0, 5].

Answer 1

It is a bad idea to modify list while traverse. You can either make a copy to traverse, or generate a new list during traverse.

In fact, the question can be done in many ways, such as:

>>> a.sort(key = lambda i: i == 6)
>>> a
[4, 2, 3, 9, 1, 5, 6, 6, 6, 6, 6]

Answer 2

Iterating the list reverse way, pop the element if it's 6, then append it.

xs = [6,4,6,2,3,6,9,6,1,6,5] 

for i in range(len(xs)-1, -1, -1):  # 10 to 0
    if xs[i] == 6:
        xs.append(xs.pop(i))

Answer 3

Why not try something like this?

Basically, the approach is to first count the number of values. If 0, then returns (since Python produces a ValueError if the list.index method is called for an element not in the list).

We can then set the first acceptable index for the value to be the length of the list minus the number of occurrences it exists in the list.

We can then combine list.pop/list.append to then traverse the list until all the values desired occur at the end of the list.

def shift_value(lst, value):
    counts = lst.count(value)       # 5
    if not counts:
        return lst

    value_index = len(lst) - counts
    index = lst.index(value)
    while index != value_index:
        lst.append(lst.pop(index))
        index = lst.index(value)
    return lst

lst = [6,4,6,2,3,6,9,6,1,6,5]
print(shift_value(lst, 6))

EDIT: This is horribly inefficient, better answer suggested above. This requires O(n^2) time, rather than O(n) time.

Answer 4

The key term here is "In Line". The way you do that is move num[i] = num[i+1] for each i to the end of the list.

def shift_sixes(num):
    for i, val in enumerate(num):
        if val == 6:
            # shift remaining items down
            for j in range(i,len(num)-1):
                num[j] = num[j+1]
            # add 6 at the end
            num[-1] = 6
    return num

print(shift_sixes([1,9,4,6,2,7,8,6,2,2,6]))
print(shift_sixes([1,2,3]))
print(shift_sixes([6]))
print(shift_sixes([3]))

Answer 5

Use two runners. First from front to end checking for 6s, second from end to front pointing to last item that's not a 6. Keep swapping (a[i+1], a[i] = a[i], a[i+1]) until they meet.

Catch: this is not stable like in a stable sort. But I don't see that as a requirement.

Will try to write working code when in front of a python interpreter with a keyboard.

Answer 6

In case you need a stable sort (i.e. order of elements that are not 6 should remain the same), then the solution is:

def move_to_end(data, value):
    current = 0 # Instead of iterating with for, we iterate with index
    processed = 0 # How many elements we already found and moved to end of list
    length = len(data) # How many elements we must process
    while current + processed < length: # While there's still data to process
        if data[current] == value: # If current element matches condition
            data.append(data.pop(current)) # We remove it from list and append to end
            processed += 1 # Our index remains the same since list shifted, but we increase number of processed elements
        else: # If current element is not a match
            current += 1 # We increase our index and proceed to next element

if __name__ == '__main__':

    print
    print 'Some testing:'
    print

    for test_case in (
        [1, 9, 4, 6, 2, 7, 8, 6, 2, 2, 6], # Generic case
        [6, 6, 6, 6], # All items are 6
        [1, 7], # No items are 6
        [], # No items at all
    ):
        print 'Raw:', test_case
        move_to_end(test_case, 6)
        print 'Becomes:', test_case
        print

Note that this solution retains the order of not only non-matching elements, but of matching elements as well. So for example, if you change the check condition from "equal to 6" to "is an even number", all elements matching the condition will be moved to the end of list while retaining their order among themselves.

Answer 7

Why not keep it simple?

a = [6,4,6,2,3,6,9,6,1,6,5]
def shift_sixes(nums):
    for i in range(0,len(nums)):
        if nums[i] == 6:
            nums.append(nums.pop(i))

>>> shift_sixes(a)
>>> a
[3, 9, 1, 5, 2, 4, 6, 6, 6, 6]