Какова формула для подсчета количества проходов элементов списка, если циклически повторяется x раз?

Question

Учитывая

    list =['a','b','c']

Как узнать, сколько раз к элементу обращались при циклическом просмотре списка х раз.Например:

    # if we cycled list 4 times, output would be
    output = [('a',2), ('b',1), ('c',1)]

    # if we cycled list 7 times, output would be
    output = [('a',3), ('b',2), ('c',2)]

Есть ли для этого формула или необходим цикл?

Answer 1

Дано

import itertools as it
import collections as ct


lst = list("abc")
n = 7

Код

iterable = (it.islice(it.cycle(lst),  n)
[(k, v) for k, v in ct.Counter(iterable).items()]
# [('a', 3), ('b', 2), ('c', 2)]

Answer 2

Количество раз, которое мы посещаем k -й элемент в списке с n элементами, а v посещений составляет ⌈ (vk) / n⌉, что эквивалентно ⌊ (v-k + n-1) / n⌋.В конце концов, мы совершаем v посещений, что означает, что каждый элемент посещает не менее ⌊v / n-1⌋.Последний «раунд» распределяет оставшиеся v - ⌊v / n-1⌋ , а первые v - ⌊v / n-1⌋ элементов «возвращают» посещение.

Мы можем сгенерировать такой список за линейное время с помощью:

def visit_count(data, v):
    n = len(data)
    return [(x, (v-i+n-1)//n) for i, x in enumerate(data)]

Например:

>>> visit_count('abc', 7)
[('a', 3), ('b', 2), ('c', 2)]
>>> visit_count('abc', 8)
[('a', 3), ('b', 3), ('c', 2)]
>>> visit_count('abc', 9)
[('a', 3), ('b', 3), ('c', 3)]
>>> visit_count('abc', 10)
[('a', 4), ('b', 3), ('c', 3)]

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

>>> visit_count('abcde', 1_234_567_890_123_456)
[('a', 246913578024692), ('b', 246913578024691), ('c', 246913578024691), ('d', 246913578024691), ('e', 246913578024691)]

Ведение учета для 1'234'567'890'123'456 посещений по отдельности приведет к тому, что функция получит возраст для получения результата.Но так как количество элементов (здесь 5) ограничено, это займет всего несколько микросекунд.

Answer 3

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

def nb_accesses(sequence, loops):
    length = len(sequence)
    out = [(value, loops // length + (index < loops % length))
            for index, value in enumerate(sequence)]
    return out

sequence = ['a', 'b', 'c']

print(nb_accesses(sequence, loops=0))
# [('a', 0), ('b', 0), ('c', 0)]

print(nb_accesses(sequence, loops=3))
# [('a', 1), ('b', 1), ('c', 1)]

print(nb_accesses(sequence, loops=5))
# [('a', 2), ('b', 2), ('c', 1)]

index < loops % length оценивается как 0 (False)или 1 (True).

Answer 4

Вы можете рассчитать это частично, но в какой-то момент для этого подхода необходим цикл.Используйте деление по полу, чтобы узнать, сколько выполнено полных проходов, затем увеличьте остаток на 1 (начиная слева) для оставшихся - неполных проходов:

data = ['a', 'b', 'c']
cycles = 7
complete_passes, remainder = divmod(cycles, len(data))
passes = {i: complete_passes for i in data}
for key in data[:remainder]:
    passes[key] += 1

Примечание к divmod:

divmod(x, y)

... возвращает ...

(x//y, x%y)
# floor division, modulus

Answer 5

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

from collections import Counter

n = 7
listt = ['a','b','c']

a = n%len(listt) 
b = int(n/len(listt))

listt = listt*b + listt[0:a]
result = [(i, j) for i,j in Counter(listt).items()]
print (result)
# [('a', 3), ('b', 2), ('c', 2)]