Функция, которая удаляет определенные элементы из списка эффективным способом

Question

Я хочу создать функцию (без использования библиотек), которая принимает в качестве входных данных три целых числа (> 0) ( a , b , c ), например:

a = 6
b = 6
c = 3

и возвращает список, содержащий c элементов (поэтому в этом случае возвращаемый список должен содержать 3 элемента), взятый из списка a числа (поэтому в данном случае начальный список [1,2,3,4,5,6]).Элементы c возвращаемого списка должны быть теми, которые удалось сохранить в исходном списке после удаления номера каждые b позиций из списка a элементы до len (return_list) = c .

Так что для a = 6, b = 6 и c = 3 функция должна сделать что-то вроде этого:

1) initial_list = [1,2,3,4,5,6] 
2) first_change = [2,3,4,5,6] #the number after the 6th (**b**) is 1 because after the last element you keep counting returning to the first one, so 1 is canceled
3) second_change = [2,4,5,6] #you don't start to count positions from the start but from the first number after the eliminated one, so new number after the 6th is 3 and so 3 is canceled
4) third_change = [2,4,5] #now the number of elements in the list is equal to **c**

Обратите внимание, что если при подсчете вы заканчиваете заканчивать элементы из списка, вы продолжаете подсчет и возвращаетесь к первому элементу списка.

Я сделал эту функцию:

def findNumbers(a,b,c):  
count = 0
dictionary = {}
countdown = a
for x in range(1,a+1):
    dictionary[x] = True
while countdown > c:
    for key,value in dictionary.items():
        if value == True:
            count += 1
            if count == b+1:
                dictionary[key] = False
                count = 0
                countdown -= 1
return [key for key in dictionary.keys() if dictionary[key] == True]

В некоторых случаях это работает, как в приведенном выше примере.Но это не работает каждый раз.Например:

findNumbers(1000,1,5)

возвращает:

[209, 465, 721, 977]    #wrong result

вместо:

[209, 465, 721, 849, 977] #right result

и для больших чисел, например:

findNumbers(100000, 200000, 5)

даже для выполнения своей работы требуется слишком много времени, я не знаю, является ли проблема неэффективностью моего алгоритма или потому что в коде есть что-то, что создает проблемы для Python.Я хотел бы знать другой подход к этой ситуации, который мог бы быть более эффективным и способным работать в любой ситуации.Кто-нибудь может дать мне несколько советов / идей?Заранее спасибо за ваше время.И дайте мне знать, если вам нужны дополнительные объяснения и / или примеры.

Answer 1

Я думал, что могу быть рекурсивным в отношении проблемы, поэтому я написал это:

def func(a,b,c):
  d = [i+1 for i in range(a)]
  def sub(d,b,c):
    if c == 0: return d
    else:
      k = b % len(d)
      d.pop(k)
      d = d[k:] + d[:k]
      return sub(d,b,c-1)
  return sub(d,b,a-c)

, чтобы func(6,6,3) вернул: [2, 4, 5] успешно и func(1000,1,5) вернул: [209, 465, 721, 849, 977] к сожалению, сошибка.

Оказывается, что для значений a > 995 поднимается флаг ниже:

RecursionError: maximum recursion depth exceeded while calling a Python object

Не нужно было пытаться func(100000,200000,5) - урок усвоен.

Тем не менее, вместо того, чтобы избавляться от кода, я решил поделиться им.Это может послужить предосторожностью для рекурсивного мышления.

Answer 2

Вы можете отслеживать индекс последнего удаленного элемента списка следующим образом:

def findNumbers(a, b, c):
    l = list(range(1, a + 1))
    i = 0
    for n in range(a - c):
        i = (i + b) % (a - n)
        l.pop(i)
    return l

, так что findNumbers(6, 6, 3) возвращает:

[2, 4, 5]

и findNumbers(1000, 1, 5) возвращает:

[209, 465, 721, 849, 977]

и findNumbers(100000, 200000, 5) возвращает:

[10153, 38628, 65057, 66893, 89103]