Hi! I have an array of indices (eg. {1,2,3,4,7,6...}) and I need 2 things. 1. Generate all possible permutations of this array 2. Create a random parmutation of this array What''s the most effective way to do this? I need it for my pattern matching algorithm in my CAS. ------- Dave

The number of permutations is the factorial of the number of elements in the array.

Death of one is a tragedy, death of a million is just a statistic.

There's a function in STL/C++ that's called 'std::next_permutation'.
That should be what you're looking for.

/John

[edited by - FunkyTune on January 8, 2003 4:45:24 PM]

Thanks Funky, it seems to be what I needed, in some way.
But I''d rather know the algorithm...

---------
Dave

Why don''t you check out the source code then?
If you''re running VC++, right click on the function name and choose ''Go To Definition of'', and all will be revealed to you. Well sort of, I find STL soruce code kind of hard to read, but I''m sure you''ll figure it out.

/John

some recursive pseudocode:

void permute(int *buf, int len)
{
if len>1
{
for(i=0;i {
exchange(buf[0],buf);<br> permute(&buf[1],len-1);<br> exchange(buf[0],buf);<br> }<br> }<br> else<br> {<br> output(whole_buffer);<br> }<br>}<br><br><SPAN CLASS=editedby>[edited by - ga &#111;n January 8, 2003 5:21:44 PM]</SPAN>

quote:

---

Original post by Dave007
2. Create a random parmutation of this array

---

Just go through the list tossing the elements around randomly.

Pseudocode:

for i = 0 to n
switch a a[rand(n)]

Stupid formatting!

for i = 0 to n  switch a a[rand(n)] 

3rd try...

std::random_shuffle will give a random permutation.