Sort list with binary values

Question

If I have a categorical list with only two values, how can I sort so that the values are placed on after another.

Example:

# input list
lst = ['foo', 'bar', 'bar', 'foo', 'bar', 'bar', 'foo', 'foo']

# expected output
['foo', 'bar', 'foo', 'bar', 'foo', 'bar', 'foo', 'bar']

I have a working solution, but I felt like this could be done smarter. I also looked into itertools but could not find anything useful for my problem:

my solution:

foo = [val for val in lst if val == 'foo']
bar = [val for val in lst if val == 'bar']

lst2 = [[x, y] for x, y in zip(foo, bar)]

final_list = [val for l in lst2 for val in l]

print(final_list)
['foo', 'bar', 'foo', 'bar', 'foo', 'bar', 'foo', 'bar']

---

Note, the lists always have a equal amount of both values

Answer 1

If you want the first value kept first, you can simply make a list of the first and the other, and multiply as necessary:

lst = ['foo', 'bar', 'bar', 'foo', 'bar', 'bar', 'foo', 'foo']

first = lst[0]
second = (set(lst) - {first}).pop()
out = [first, second] * (len(lst)//2) 
print(out)
# ['foo', 'bar', 'foo', 'bar', 'foo', 'bar', 'foo', 'bar']

---

A different, better way of getting the other value, without unnecessarily iterating the whole list to build the set of two values: we just take the next value that is different from the first one.

# input list
lst = ['foo', 'bar', 'bar', 'foo', 'bar', 'bar', 'foo', 'foo']
first = lst[0]
second = next(value for value in lst if value != first)
out = [first, second] * (len(lst)//2) 
print(out)
# ['foo', 'bar', 'foo', 'bar', 'foo', 'bar', 'foo', 'bar']