fuzzy list of items - shuffled, but in strict order

I have a list of questions and I need to present each question in a different format.

(a list of N items with M possible permutations for each item).

e.g.

questions = [a, b, c]
permutations = [x, y]
permuted_questions = [(a,x), (b,x), (c,x), (a,y), (b,y), (c,y)]

Producing a simple list of permutations like above is straightforward. However, To make the list more "interesting", I'd like to shuffle it somehow.

The problem is that the list of permutations is strictly ordered. i.e. for given item a, permutation (a,x) should always appear before permutation (a,y).

e.g.

[(a,x), (b,x), (a,y), (c,x), (b,y), (c,y)] is a valid shuffle

[(a,x), (b,y), (a,y), (c,x), (b,x), (c,y)] is invalid, because (b,y) appears before (b,x)

Any suggestions?