Random permutations generation with non-repeating values at each index

There was one problem:

Given a natural number sequence S of size n, [1,2,3,4....n], the task is to generate n random permutations but the catch is that the values shouldn't repeat at any index among all permutations.

For example, given n=3, S=[1,2,3], the possible result can be

1.[3,1,2]

2.[2,3,1]

3.[1,2,3]

Output like below is not acceptable as permutation 1 and 3 have same second value as 1

1.[3,1,2]

2.[2,3,1]

3.[2,1,3]

Another restriction was this needs to be solved with O(n) space complexity.