Permutations

[Ed Neukirch]

I would like to determine nPr -- that is, the permutation of 'n' items
taken 'r' at a time preferably using the prev_permutation and
next_permutation functions of the STL. I 'googled' but could find nothing
useful.

I would appreciate any guidance or direction toward either algorithms or
source code.

Thanking you in advance.

Ed

 

[Jeffrey Schwab]

I would like to determine nPr -- that is, the permutation of 'n' items
taken 'r' at a time preferably using the prev_permutation and
next_permutation functions of the STL. I 'googled' but could find nothing
useful.

I would appreciate any guidance or direction toward either algorithms or
source code.

Thanking you in advance.

Ed

Do you just want the *number* of permutations? Here:

/* Return the number of permutations of n items, taken r at a time. The
* parameters are of type N; they should never be negative. To guard
* against overflow, underflow, etc., use a type N that performs
* validation.
*/
template< typename N /* An unsigned, integer type */ >
N num_permutations( N n, N r )
{
N result = 1;

while( r != 0 )
{
result *= n;
--n;
--r;
}

return result;
}

#include <iostream>

int main( )
{
std::cout << num_permutations( 7, 5 ) << '\n'; // 2520
}

 

[osmium]

I would like to determine nPr -- that is, the permutation of 'n' items
taken 'r' at a time preferably using the prev_permutation and
next_permutation functions of the STL. I 'googled' but could find nothing
useful.

I would appreciate any guidance or direction toward either algorithms or
source code.

That's an interesting problem and one that is more and more likely to come
up as time goes by. npr has been kidnapped by a very popular acronym,
National Public Radio and the noise overwhelms the signal. I too was
unsuccessful in finding what you want to know via google. One of the
problems is people posting "my favorite links" pages and these people know
what you want but they also have NPR on their links. As a matter of fact I
have npr in *my* list of links; but so far I have been too shy to think that
anyone else would find my set of links interesting or useful. I am
fascinated by the potential and problems in using Google, which accounts for
this rather long post.

My favorite alternative solution is to look at a book. Your text may have a
section on probabilities and such like. I would avoid using the STL in my
solution unless I had definite contrary advice, from someone with authority,
in my program.

It's kind of cheating google, since I already had, going in, a list of math
pages. But you might try starting here.

http://mathworld.wolfram.com/topics/ProbabilityandStatistics.html

 

[Mike Hewson]

I would like to determine nPr -- that is, the permutation of 'n' items
taken 'r' at a time preferably using the prev_permutation and
next_permutation functions of the STL. I 'googled' but could find nothing
useful.

I would appreciate any guidance or direction toward either algorithms or
source code.

Well, lets start with:

P(n,r) = n!/(n-r)!

( As distinct from combinations, which is without regard to the order of the
choice ie. C(n,r) = r!*P(n,r) = n!*r!/(n-r)! )

Considerations are:

- factorials get real big, real quick ( exceeding type and machine
limits )
- the order of evaluation can be important. ( truncation, overflow etc )
- you know the answer must be an integer ( use integral types )

Lets look at an example:

P(10,4) = 10!/6! = (10*9*8*7*6*5*4*3*2*1)/(6*5*4*3*2*1)
= 10*9*8*7

That should suggest a certain iterative method ( or recursive if you're
keen ).

I don't know a thing about the 'prev_permutation' and 'next_permutation'
functions of the STL. The next 'n', or the next 'r' ?

 

[Mike Hewson]

( As distinct from combinations, which is without regard to the order of the
choice ie. C(n,r) = r!*P(n,r) = n!*r!/(n-r)! )

Ahem...

C(n,r) = P(n,r)/r! = n!/r!(n-r)!

 

[Ed Neukirch]

Well, lets start with:

P(n,r) = n!/(n-r)!

( As distinct from combinations, which is without regard to the order of the
choice ie. C(n,r) = r!*P(n,r) = n!*r!/(n-r)! )

Considerations are:

- factorials get real big, real quick ( exceeding type and machine
limits )
- the order of evaluation can be important. ( truncation, overflow etc )
- you know the answer must be an integer ( use integral types )

Lets look at an example:

P(10,4) = 10!/6! = (10*9*8*7*6*5*4*3*2*1)/(6*5*4*3*2*1)
= 10*9*8*7

That should suggest a certain iterative method ( or recursive if you're
keen ).

I don't know a thing about the 'prev_permutation' and 'next_permutation'
functions of the STL. The next 'n', or the next 'r' ?

Thanks for your response, but to clarify my request for information, I am
not looking for the number of permutations, but for a method to determine
the permutations themselves; for example, nPr for n = 4, r = 2 four
items taken two at a time -- string = 'abcd' would produce 'ab', 'ac',
'ad', 'ba' .... etc.

Ed

 

[Jeff Schwab]

Thanks for your response, but to clarify my request for information, I am
not looking for the number of permutations, but for a method to determine
the permutations themselves; for example, nPr for n = 4, r = 2 four
items taken two at a time -- string = 'abcd' would produce 'ab', 'ac',
'ad', 'ba' .... etc.

Perhaps you could find a function to step through all possible
combinations (nCr), then step through each combination with
std::next_permutation. Do you think this approach would be valid?

 

[Mike Hewson]

Thanks for your response, but to clarify my request for information, I am
not looking for the number of permutations, but for a method to determine
the permutations themselves; for example, nPr for n = 4, r = 2 four
items taken two at a time -- string = 'abcd' would produce 'ab', 'ac',
'ad', 'ba' .... etc.

Hmmm...yes. Try the following approach ( pseuodcode ):

main_string is "abcd";

For letter_in_position_1 from start_of(main_string) thru end_of(main_string)
{
// letter_in_position_1 is 'a',b','c',d'.
sub_string1 is main_string minus letter_in_position_1
// First time thru sub_string1 is "bcd".
// Second time thru sub_string1 is "acd".
// Third time thru sub_string1 is "abd".
// Fourth time thru sub_string1 is "abc".
For letter_in_position_2 from start_of(sub_string1) thru
end_of(sub_string1)
{
sub_string2 is sub_string1 minus letter_in_position_2;
print letter_in_position_1 next to letter_in_position_2;
}
}

That's fine as it goes for the example quoted, but it doesn't readily
generalise. You need 'r' loops ( with nesting ), presumably not known at
compile time. I feel deja vu ( in other words recursion ) coming on.