How to delete elements of a circular list until there is only one element left using python? [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 3 years ago.

Improve this question

How would I go about iterating through a list from 1-100, where I delete every other element starting with the first element, and repeat that step until there in only one element left in the list. Would I have to use a circular linked list, or can it be done just using loops and conditional statements?

Answer 1

If you assume the circular list structure, when the last element of the list is deleted, the next element to be deleted is not the first one in the remaining list any more but the second one. 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

should be correct.

The result is

[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

This deletes every other element over and over until just one is left

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

I'm not sure what the "circular list" means, but maybe this modification is needed

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

The len(L)%2 means to del L[1::2] if the length of L is odd

Or if you like to see what's going on:

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

How about using Python's handy slice syntax:

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

The expression best_list_ever[1::2] is a list of every other element in the original list.

Edit: I'm actually pretty confused about the circular constraint thing, but if it's accurately documented by ysakamoto then maybe look to gnibbler's answer.

Answer 4

This answer simply keeps appending the items you wish to keep

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

equivalently without using islice

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

memory efficient version using deque

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

These all give a value of 71, which doesn't agree with @ysakamoto's answer

Answer 5

You can do it with two nested while loops

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;
      }
    }

Same can be done with for loops or any iterative loop. Should you print elements while doing this, you should see elements deleted in order of (assume list size of 10)

Loop 1 0,2,4,6,8

Loop 2 1,5,9

Loop 3 3

Leaving you with element 7 from original list

Thanks!

Answer 6

Although not as compact as the other answers, here is my version. I'm new to Python and learning a lot by looking at others' answers.

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

    print  mylist

The result:

[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

long code:

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

short code:

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

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