Ja die Frage steht im Titel, nachdem was ich so im Netz gefunden habe würde ich sagen ja, aber ich bin noch nicht über die Vorgaben des Standards zu dieser funktion gefunden.
Mir scheint, ja, es ist deterministisch. Lies mal hier: www.sgi.com/tech/stl/next_permutation.html, besonders dieser Satz: "Next_permutation transforms the range of elements [first, last) into the lexicographically next greater permutation of the elements."