randomizing two lists and maintaining order in python

I’d combine the two lists together, shuffle that resulting list, then split them. This makes use of zip()

a = ["Spears", "Adele", "NDubz", "Nicole", "Cristina"]
b = [1, 2, 3, 4, 5]

combined = list(zip(a, b))
random.shuffle(combined)

a[:], b[:] = zip(*combined)