Shuffle with a constraint

I have a problem analog to:

We have 20 balls numbered from 1 to 20. The balls numbered from 1 to 5 are yellow, from 6 to 10 green, from 10 to 15 red and from 16 to 20 blue. Find a method to randomly shuffle the balls while respecting the constraint: "2 successive balls cannot have the same color".

Example:

I have considered two methods that I am not satisfied with, and I am looking for a better one

1. draw a ball at random, then draw a ball at random among all the others having a different color from the previous one, etc.

Problem: we can fall in cases where it is impossible to finish the drawing, if there are only remaining balls of the same color for example.

2. divide the balls into 4 sets of 5 balls (1 per color), form 5 other sets of 4 balls by randomly drawing a ball of each color. Reassemble these 5 sets in order to respect the criterion (the first balls of the last set are permuted until the criterion is respected).

Problem some combinations are never drawn, for example red, yellow, red, yellow ... green, blue, green, blue.