Granny's Programming Pearls
"inside of every large program is a small program struggling to get out"
JavaRanch.com/granny.jsp
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Permutation and Combination in Java  RSS feed

 
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
HI,
Is there any utility class in java which helps in computing Permutation and Combination?
 
Sheriff
Posts: 22846
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The calculations themselves are very simple but you might require BigInteger if your numbers are going to become large.
 
Marshal
Posts: 56608
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Go to the API index (that was for P) and try ctrl-F permutation. And you will probably find the same as I did . . . nothing. You will have to try with C for combination, too.
 
Campbell Ritchie
Marshal
Posts: 56608
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Combination =
       n!       
r! × (n - r)!

Permutation =
   n!  
   r!

In all cases nr and if n = r both nCr = 1 and nPr = 1

You can probably count down from n and up from r; if you multiply downwards, you can reduce the maximum size of intermediate values. Don’t try to work out 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 ÷ 7 ÷ 6 ÷ 5 ÷ 4 ÷ 3 ÷ 2 ÷ 1.
Try 10 ÷ 1 × 9 ÷ 2 × 8 ÷ 3 × 7 ÷ 4 × 6 ÷ 5 × 5 ÷ 6 × 4 ÷ 7 × 3 × 2 × 1
You can speed the process, at the cost of more complicated code, if you can work out how to remove common factors and divisors.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!