A function called rand receives a positive integer M and returns a positive integer between 1 to M, randomly.
Write a function that given a sorted array of all integers from 1 to N, it returns an array of length N which comprises a permutation of these 1 to N numbers, so that the probability of receiving each permutation is 1/N!.
Required time complexity is O(N).
I'm not sure how you can prove that your solution returns permutations that are received in 1/N! probability.
Any help is appreciated
Write a function that given a sorted array of all integers from 1 to N, it returns an array of length N which comprises a permutation of these 1 to N numbers, so that the probability of receiving each permutation is 1/N!.
Required time complexity is O(N).
I'm not sure how you can prove that your solution returns permutations that are received in 1/N! probability.
Any help is appreciated