Random permutation

[hamidvosugh]

Hi
Would any one tell me how can I generate a random permutation of N numbers in c++?
Is there any algorithm in STL for this purpose?

Thanks in advance

[programmersbook]

i found this: http://www.codeguru.com/cpp/cpp/algorithms/article.php/c5123/

[hamidvosugh]

i found this: http://www.codeguru.com/cpp/cpp/algorithms/article.php/c5123/

That was a great help, but what I am looking for is to output N permutations out of total M permutations Randomly. (N < M)

[mrnutty]

What sort of premutation? On what set?

[hamidvosugh]

What sort of premutation? On what set?

int array[] ={1,2,3,4};
The output of next_permutation() on the above array result in
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
.....
.....
2 4 3 1
...
...
What I like to be output is permutation of those numbers, but in different orders each time the function is called.
E.X
2 4 3 1
1 4 3 2
2 1 3 4
1 2 4 3
3 4 2 1
4 2 1 3
...
...
1 2 3 4

[pecet]

You can store all permutations in 2D vector. Then You need to create another vector with M! elements (indexes). Random_shuffle vector with indexes and you have order in which You should read data from 2D vector (with all permutations).
But since (N < M) this algorithm is little overkill, because no matter how big N would be, you always have to generate all permutations.

[hamidvosugh]

I have reached to the following idea which works quite well for me. Although it won't generate all the permutations in the given range.

int array[] = {1,2,3,4,5};
srand (time(0));
do{
}while(next_permutation(array, array +(rand()%5)));