Anonymous user
Combinations and permutations: Difference between revisions
→{{header|Go}}
Line 608:
=={{header|Go}}==
Go has arbitrary-length maths in the standard math/big library; no need for floating-point approximations at this level.
<lang go>
package main
import (
"fmt"
"math/big"
)
func main() {
var n, p int64
fmt.Printf("A sample of permutations from 1 to 12:\n")
for n = 1; n < 13; n++ {
p = n / 3
fmt.Printf("P(%d,%d) = %d\n", n, p, perm(big.NewInt(n), big.NewInt(p)))
}
fmt.Printf("\nA sample of combinations from 10 to 60:\n")
for n = 10; n < 61; n += 10 {
p = n / 3
fmt.Printf("C(%d,%d) = %d\n", n, p, comb(big.NewInt(n), big.NewInt(p)))
}
fmt.Printf("\nA sample of permutations from 5 to 15000:\n")
nArr := [...]int64{5, 50, 500, 1000, 5000, 15000}
for _, n = range nArr {
p = n / 3
fmt.Printf("P(%d,%d) = %d\n", n, p, perm(big.NewInt(n), big.NewInt(p)))
}
fmt.Printf("\nA sample of combinations from 100 to 1000:\n")
for n = 100; n < 1001; n += 100 {
p = n / 3
fmt.Printf("C(%d,%d) = %d\n", n, p, comb(big.NewInt(n), big.NewInt(p)))
}
}
func fact(n *big.Int) *big.Int {
if n.Sign() < 1 {
return big.NewInt(0)
}
r := big.NewInt(1)
i := big.NewInt(2)
for i.Cmp(n) < 1 {
r.Mul(r, i)
i.Add(i, big.NewInt(1))
}
return r
}
func perm(n, k *big.Int) *big.Int {
r := fact(n)
r.Div(r, fact(n.Sub(n, k)))
return r
}
func comb(n, r *big.Int) *big.Int {
if r.Cmp(n) == 1 {
return big.NewInt(0)
}
if r.Cmp(n) == 0 {
return big.NewInt(1)
}
c := fact(n)
den := fact(n.Sub(n, r))
den.Mul(den, fact(r))
c.Div(c, den)
return c
}
</lang>
Output:
<pre>A sample of permutations from 1 to 12:
P(1,0) = 1
P(2,0) = 1
P(3,1) = 3
P(4,1) = 4
P(5,1) = 5
P(6,2) = 30
P(7,2) = 42
P(8,2) = 56
P(9,3) = 504
P(10,3) = 720
P(11,3) = 990
P(12,4) = 11880
A sample of combinations from 10 to 60:
C(10,3) = 120
C(20,6) = 38760
C(30,10) = 30045015
C(40,13) = 12033222880
C(50,16) = 4923689695575
C(60,20) = 4191844505805495
A sample of permutations from 5 to 15000:
P(5,1) = 5
P(50,16) = 103017324974226408345600000
P(500,166) = 353487492174294278760936182660176230684400287910609032932176169251145051223056590013516735448538086130105926216996155913554025250125337170813019594283712354977999534430770809915541863294344717641926832713607917635838943102385935821177067602075180371673503765613359169210620516084434587852075431010684540863423686685437846488590916158047347611875355166780660833377163468853354607169353747005440000000000000000000000000000000000000000000
P(1000,333) = 596932628850341508903970176590078428099818947656708993181003187015748137551596090897395098770177006143741943000028735297176540996715216223470117008188290845824893667956971794591724165149886070514986743432208287422668258597883938335639789463537748828480742878588232053442156529356123644254034620250998013239063050800571901268462622323786888857845397534124006543754044331948142416200311556601875197681493636464229808874876131434533721937546154413110195799580966669097512255452752067457629468146295647406985227990184437533735467426422585063839734564755495294687791091277426861971582062496498138090957027659529000216472781766770467939751274131497380920782541878343751496719223481266229644276166815775979972070711062842180838624567600323874889368489920534418201154996144776696986749038638993937273035934558675329887334851616951614782042039326589303359315137179445599073086196250614391361241088000000000000000000000000000000000000000000000000000000000000000000000000000000000000
P(5000,1666) = 685674575725567427548453694024889606223415671024481949274389525763165050940278456955930987049278913288741555958551429473866794447094151777406284837935079289013939976368320856320075398810321021264609367677596630017492662476653457696667818345302032079158497998678962485919859205035598026552321633034034950067207086196635562039504231368320682342175536748176816241129369211418155064764285518551122913802314264757797230065345837585112169021234001053819461909997341171332285483908469793127022101882927191957584158820572953454348525922376264896938701700503579[cut for brevity]
P(15000,5000) = 964985398872749392201485880593129598079228168868086089709069882934904327326041434448685068557423519588782990996839148935743422697293448340149394869739166392123184483900811562453898657822593544251663672426442538772790754374376708208571908721887559582227891355612508675254239851818491849618848602192999811776790423150460291684931309968390568370095954400889615967984376006072547506893620140168365357740946620575769516153753735678390720704316317251046076250691800213698137901479234159657387339301806781869228964210268691780310799227446113809960921205463002689680686581917548426454723087176124161728203856922785131850458595700123281745279678944233081992533251647291980003523846698046974475328766195265764029672828687155439288711515137638802309221117722696141292043413736618293499869841412502567093112620576877254953509763190120514494690844850900732795773648193199871673637389424514221019995024902360799221264651063770768194819355718580618775786102220736660007307021195929713637615667876228769039112504881578385857681786265840651390718446642041061982261630233585694136722143048873223923363402206453540375800805584706454386378553117095912890292078608807203370350094921116703330118357576158786202069866488676813049328910886961677198798213135372964228023956951408480830806905842004749290253667472325116488994202675719755525469268037451046892994419861436389890344224919839492952550142350743[cut for brevity]
A sample of combinations from 100 to 1000:
C(100,33) = 294692427022540894366527900
C(200,66) = 726975254516927834152706665119273897675502691419359300
C(300,100) = 4158251463258564744783383526326405580280466005743648708663033657304756328324008620
C(400,133) = 12579486841821087021333484756519650044917494358375678689903944407062661887691782714561293494166382210572895600
C(500,166) = 39260283861944227552204083450723314281973490135301528555644859907093815055309467400410307687655531369748267877388321068535356654999949000
C(600,200) = 250601778322140280500561677051322883520255102508793389473094343332441398315528846878026090182866148274621477126087990864486283260622128340138769443055475567389095596
C(700,233) = 810320356333959990474045364403113823294492031194214481466666874664632951279413378341573227990559808332117096088495529108312831240206642074673862825014526456696556162909686658807978793453220000
C(800,266) = 2645623362683627034288829299556124255091524045015061559880110850588357798837813526621954238671844949835878984342140544523564918954064307529607727040078866833961879433579846596361407958192581870170248962672479120257018000
C(900,300) = 17433563732964466429607307650857183476303419689548896834573896609295907147982188408607179689430757813632301567003238290404591375673438892792913992016448098783043956457942357838233534288303678577768883350818012950587783262800434058273110416350965200
C(1000,333) = 57761345531476516697774863235496017223394580195002114171799054793660405129610824218694609475292335509897216233568933163108481350037180876217607177657236327948642711456536116349650593787069554795812874358426845137087373717847050642650744775784499136594696491030795647099932000
</pre>
=={{header|Haskell}}==
| |||