Executando o código

listoflists = []
list = []
for i in range(0,10):
    list.append(i)
    if len(list)>3:
        list.remove(list[0])
        listoflists.append((list, list[0]))
print listoflists

devolve

[([7, 8, 9], 0), ([7, 8, 9], 0), ([7, 8, 9], 0), ([7, 8, 9], 1), ([7, 8, 9], 2), ([7, 8, 9], 3), ([7, 8, 9], 4), ([7, 8, 9], 5), ([7, 8, 9], 6), ([7, 8, 9], 7)]

então, de alguma forma, o primeiro argumento de cada tupla (lista) está sendo atualizado a cada vez na lista de listas, mas a segunda lista de argumentos [0] não é. Alguém pode explicar o que está acontecendo aqui e sugerir uma maneira de corrigir isso? Eu gostaria de produzir

[([0],0), ([0,1],0), ...