

 This page uses content from Wikipedia. The original article was at Combination. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)



 This page uses content from Wikipedia. The original article was at Permutation. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

Task

Implement the combination    (nCk)    and permutation    (nPk)    operators in the target language:

 






n



C

k


=



(


n
k


)



=



n
(
n
−
1
)
…
(
n
−
k
+
1
)


k
(
k
−
1
)
…
1





{\displaystyle ^{n}\operatorname {C} _{k}={\binom {n}{k}}={\frac {n(n-1)\ldots (n-k+1)}{k(k-1)\dots 1}}}


 






n



P

k


=
n
⋅
(
n
−
1
)
⋅
(
n
−
2
)
⋯
(
n
−
k
+
1
)


{\displaystyle ^{n}\operatorname {P} _{k}=n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)}




See the Wikipedia articles for a more detailed description.

To test, generate and print examples of:

   A sample of permutations from 1 to 12 and Combinations from 10 to 60 using exact Integer arithmetic.
   A sample of permutations from 5 to 15000 and Combinations from 100 to 1000 using approximate Floating point arithmetic.
 This 'floating point' code could be implemented using an approximation, e.g., by calling the Gamma function.


Related task

   Evaluate binomial coefficients



 The number of samples of size k from n objects.


With   combinations and permutations   generation tasks. 






 Order Unimportant

 Order Important


 Without replacement








(


n
k


)




=

n



C

k


=



n
(
n
−
1
)
…
(
n
−
k
+
1
)


k
(
k
−
1
)
…
1





{\displaystyle {\binom {n}{k}}=^{n}\operatorname {C} _{k}={\frac {n(n-1)\ldots (n-k+1)}{k(k-1)\dots 1}}}










n



P

k


=
n
⋅
(
n
−
1
)
⋅
(
n
−
2
)
⋯
(
n
−
k
+
1
)


{\displaystyle ^{n}\operatorname {P} _{k}=n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)}




Task: Combinations

Task: Permutations


 With replacement








(



n
+
k
−
1

k


)




=

n
+
k
−
1



C

k


=



(
n
+
k
−
1
)
!


(
n
−
1
)
!
k
!





{\displaystyle {\binom {n+k-1}{k}}=^{n+k-1}\operatorname {C} _{k}={(n+k-1)! \over (n-1)!k!}}








n

k




{\displaystyle n^{k}}




Task: Combinations with repetitions

Task: Permutations with repetitions



Function PermBig(x As Long, y As Long) As ULongint
    Dim As Long i
    Dim As Longint z = 1
    For i = x - y + 1 To x
        z = z * i
    Next i
    Return (z)
End Function
 
Function FactBig(x As Long) As ULongint
    Dim As Long i
    Dim As Longint z = 1
    For i = 2 To x
        z = z * i
    Next i
    Return (z)
End Function
 
Function CombBig(Byval x As Long, Byval y As Long) As Double
    If y > x Then
        Return (0)
    Elseif x = y Then
        Return (1)
    Else
        If x - y < y Then y = x - y
        Return (PermBig(x, y) / FactBig(y))
    End If
End Function
 
Dim As Long i, j
Print "-- Long Integer - Permutations - from 1 to 12"
For i = 1 To 12
    For j = 1 To i
        Print "P(" & i & "," & j & ")=" & Str(PermBig(i, j)) & "  ";
    Next j
    Print ""
Next i
 
Print Chr(10) & "-- Float integer - Combinations from 10 to 60"
For i = 10 To 60 Step 10
    For j = 1 To i Step i \ 5
        Print "C(" & i & "," & j & ")=" & Str(CombBig(i, j)) & "  ";
    Next j
    Print ""
Next i
 
Print Chr(10) & "-- Float integer - Permutations from 5000 to 15000"
For i = 5000 To 15000 Step 5000
    For j = 10 To 50 Step 20
        Print "P(" & i & "," & j & ")=" & Str(PermBig(i, j)) & "  ";
    Next j
    Print ""
Next i
 
Print Chr(10) & "-- Float integer - Combinations from 200 to 1000"
For i = 200 To 1000 Step 200
    For j = 20 To 100 Step 20
        Print "C(" & i & "," & j & ")=" & Str(CombBig(i, j)) & "  ";
    Next j
    Print ""
Next i
Sleep