How to remove circular list items until only one item is left using python?

Question

How do I iterate over a list of 1-100, where I delete every other item, starting from the first item, and repeat this step until there is only one item left in the list. Should I use a circular linked list, or can this only be done using loops and conditional statements?

Answer 1

If you accept the structure of the circular list when the last element of the list is deleted, the next element to be deleted is not the first in the rest of the list, but the second. Thus,

L = range(100)
st1=len(L)%2
st2=0
while len(L)>1:
    del L[st2::2]
    st2=(st1+st2)%2
    st1=len(L)%2
    print L

must be correct.

Result

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99]
[3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63, 67, 71, 75, 79, 83, 87, 91, 95, 99]
[7, 15, 23, 31, 39, 47, 55, 63, 71, 79, 87, 95]
[7, 23, 39, 55, 71, 87]
[7, 39, 71]
[7, 71] 
[71]

Answer 2

,

>>> L = range(100)       # for Python3, use L = list(range(100))
>>> while len(L) > 1:
...     del L[::2]
... 
>>> L
[63]

, " ", , ,

>>> L = range(100)
>>> while len(L) > 1:
...     del L[len(L)%2::2]
... 
>>> L
[99]

len(L)%2 del L[1::2], L

, , :

>>> L = range(100)
>>> while len(L) > 1:
...     del L[len(L)%2::2]
...     L
... 
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99]
[3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63, 67, 71, 75, 79, 83, 87, 91, 95, 99]
[3, 11, 19, 27, 35, 43, 51, 59, 67, 75, 83, 91, 99]
[3, 19, 35, 51, 67, 83, 99]
[3, 35, 67, 99]
[35, 99]
[99]

Answer 3

Python slice :

while len(best_list_ever) > 1:
    best_list_ever = best_list_ever[1::2]

best_list_ever[1::2] - .

: , ysakamoto, , , gnibbler.

Answer 4

,

>>> from itertools import islice
>>> L = range(100)
>>> for i in islice(L, 1, None, 2):
...     L.append(i)
... 
>>> i
71

islice

>>> L = range(100)
>>> i = 1
>>> while i < len(L):
...     L.append(L[i])
...     i += 2
... 
>>> L[-1]
71

deque

>>> from collections import deque
>>> L = deque(range(100))
>>> while len(L) > 1:
...     _ = L.popleft()
...     L.append(L.popleft())
... 
>>> L
deque([71])

71, @ysakamoto

Answer 5

pseudo code

    // if there is more than one element, lets keep working 
    while(list.size > 1) {
      // Know there is one element, thus safe to assume 0
      int i = 0;

      // retrieve list size, going to be mutating list 
      int l = list.size

      // iterate through list  
      while(i < l) {
        // delete element, we want to delete the next element but skip previous, thus floor / 2
        list.delete(floor(i / 2));

        // skip every other element, thus increment by 2
        i = i + 2;
      }
    }

. , , ( 10)

1 0,2,4,6,8

2 1,5,9

3 3

7

!

Answer 6

, , . Python , .

mylist = range(20)
print mylist
while len(mylist) > 1:
    for i in range(len(mylist) / 2):
        del mylist[i] 

    print  mylist

:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
[3, 7, 11, 15, 19]
[7, 15, 19]
[15, 19]
[19]

Answer 7

:

num=int(input())
list_num=[]
for j in range(num):
    list_num.append(j+1)
k=0   
while len(list_num)>1:
    new_list_sum=[]
    l=0
    while k+2*l<len(list_num):
        new_list_sum.append(list_num[k+2*l])
        l=l+1
    if (k+2*l)%(len(list_num)-1)==1:
        k=0
    else:
        k=1
    list_num=new_list_sum[:]
    print(list_num)
print(list_num[0])

:

num=int(input())
l=num-2**(len(bin(num)[2:])-1)
print (2*l+1)

: https://en.wikipedia.org/wiki/Josephus_problem