Below is a brute-force for finding all tuples with prescribed ordering. For example there are 6 possible 5-tuples from set {1, 2, 3, 4} with ordering {3, 4, 2, 5, 1}.
Any idea how to do it without enumerating all possible tuples?
order = {3, 4, 2, 5, 1}; Grid[{#, Select[Tuples[Range[#], {Length[order]}], Ordering[#] == order &]} & /@ Range[6], Alignment -> Left] 
Using the ResourceFunction SelectTuples, we can get a method that is less memory intensive and does not generate all possible tuples first, but appears to be slower than the brute force case.
SelectTuples = ResourceFunction["SelectTuples"](*[list,n,crit]*) order = {3, 4, 2, 5, 1}; SelectTuples[Range[4], Length@order, Ordering[#] == order &]
{{3, 2, 1, 1, 2}, {4, 2, 1, 1, 2}, {4, 2, 1, 1, 3}, {4, 3, 1, 1, 3}, {4, 3, 1, 2, 3}, {4, 3, 2, 2, 3}}
According to the documentation of SelectTuples, it does not generate all tuples first:
ResourceFunction["SelectTuples"]is used in cases for which generating all tuples would be too memory intensive, especially when the elements of list are large and the number of tuples that satisfy crit is small.
ResourceFunction["SelectTuples"]is an alternative toSelect[Tuples[…],crit], which first generates all tuples.
Testing with a larger list, we see SelectTuples is slower than just using a selection on Tuples:
AbsoluteTiming[ SelectTuples[Range[16], Length@order, Ordering[#] == order &];] AbsoluteTiming[ Select[Tuples[Range[16], {Length[order]}], Ordering[#] == order &];]
1.4104
0.643293
But the MaxMemoryUsed is lower
MaxMemoryUsed[ SelectTuples[Range[16], Length@order, Ordering[#] == order &]] MaxMemoryUsed[ Select[Tuples[Range[16], {Length[order]}], Ordering[#] == order &]]
1385048
201556992
This does not need enumerating all tuples.
(order of tuples is different than in brute-force method)
Also the advantage is that we can replace Table with Do and produce each tuple one by one (in case the whole list of all tuples is very large).
Clear[fu] fu[order_, n_] := Block[{le = Length[order] - 1, or = order // Ordering, dif, itt, ta}, dif = Differences[order] // Negative // Boole; itt = Prepend[ Table[{x[i], x[i - 1] + dif[[i]], n}, {i, le}], {x[0], 1, n}]; ta = Table[x[i], {i, 0, le}][[or]]; Flatten[Table[ta, Evaluate[Sequence @@ itt]], le]] order = {3, 4, 2, 5, 1}; Grid[{#, fu[order, #]} & /@ Range[6], Alignment -> Left] 
Version with Do. Here we print each tuple, but instead of Print any computations can be done on each tuple one-by-one.
Clear[fu2] fu2[order_, n_] := Block[{le = Length[order] - 1, or = order // Ordering, dif, itt, ta}, dif = Differences[order] // Negative // Boole; itt = Prepend[ Table[{x[i], x[i - 1] + dif[[i]], n}, {i, le}], {x[0], 1, n}]; ta = Table[x[i], {i, 0, le}][[or]]; Do[Print[ta], Evaluate[Sequence @@ itt]]] order = {3, 4, 2, 5, 1}; fu2[order, 4] {3,2,1,1,2} {4,2,1,1,2} {4,2,1,1,3} {4,3,1,1,3} {4,3,1,2,3} {4,3,2,2,3} Verifying that each tuple ordering is equal to the prescribed order.
(Ordering /@ fu[order, 16] // Union) == {order} True