

 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



# -*- coding: utf-8 -*- #
 
COMMENT REQUIRED by "prelude_combinations_and_permutations.a68" CO
  MODE CPINT = #LONG# ~;
  MODE CPOUT = #LONG# ~; # the answer, can be REAL #
  MODE CPREAL = ~; # the answer, can be REAL #
  PROC cp fix value error = (#REF# CPARGS args)BOOL: ~;
#PROVIDES:#
# OP C = (CP~,CP~)CP~: ~ #
# OP P = (CP~,CP~)CP~: ~ #
END COMMENT
 
MODE CPARGS = STRUCT(CHAR name, #REF# CPINT n,k);
 
PRIO C = 8, P = 8; # should be 7.5, a priority between *,/ and **,SHL,SHR etc #
 
# I suspect there is a more reliable way of doing this using the Gamma Function approx #
 
OP P = (CPINT n, r)CPOUT: (
  IF n < r ORF r < 0 THEN IF NOT cp fix value error(CPARGS("P",n,r)) THEN stop FI FI;
  CPOUT out := 1;
# basically nPk = (n-r+1)(n-r+2)...(n-2)(n-1)n = n!/(n-r)! #
  FOR i FROM n-r+1 TO n DO out *:= i OD;
  out
);
 
OP P = (CPREAL n, r)CPREAL: # 'ln gamma' requires GSL library # 
  exp(ln gamma(n+1)-ln gamma(n-r+1));
 
# basically nPk = (n-r+1)(n-r+2)...(n-2)(n-1)n = n!/(n-r)! #
COMMENT # alternate slower version #
OP P = (CPREAL n, r)CPREAL: ( # alternate slower version #
  IF n < r ORF r < 0 THEN IF NOT cp fix value error(CPARGS("P",ENTIER n,ENTIER r)) THEN stop FI FI;
  CPREAL out := 1;
# basically nPk = (n-r+1)(n-r+2)...(n-2)(n-1)n = n!/(n-r)! #
  CPREAL i := n-r+1;
  WHILE i <= n DO
    out*:= i;
# a crude check for underflow #
    IF i = i + 1 THEN IF NOT cp fix value error(CPARGS("P",ENTIER n,ENTIER r)) THEN stop FI FI;
    i+:=1
  OD;
  out
);
END COMMENT
 
# basically C(n,r) = nCk = nPk/r! = n!/(n-r)!/r! #
OP C = (CPINT n, r)CPOUT: (
  IF n < r ORF r < 0 THEN IF NOT cp fix value error(("C",n,r)) THEN stop FI FI;
  CPINT largest = ( r > n - r | r | n - r );
  CPINT smallest = n - largest;
  CPOUT out := 1;
  INT smaller fact := 2;
  FOR larger fact FROM largest+1 TO n DO 
# try and prevent overflow, p.s. there must be a smarter way to do this #
#   Problems: loop stalls when 'smaller fact' is a largeish co prime #
    out *:= larger fact;
    WHILE smaller fact <= smallest ANDF out MOD smaller fact = 0 DO 
      out OVERAB smaller fact;
      smaller fact +:= 1
    OD
  OD;
  out # EXIT with: n P r OVER r P r #
);
 
OP C = (CPREAL n, CPREAL r)CPREAL: # 'ln gamma' requires GSL library # 
  exp(ln gamma(n+1)-ln gamma(n-r+1)-ln gamma(r+1));
 
# basically C(n,r) = nCk = nPk/r! = n!/(n-r)!/r! #
COMMENT # alternate slower version #
OP C = (CPREAL n, REAL r)CPREAL: (
  IF n < r ORF r < 0 THEN IF NOT cp fix value error(("C",ENTIER n,ENTIER r)) THEN stop FI FI;
  CPREAL largest = ( r > n - r | r | n - r );
  CPREAL smallest = n - largest;
  CPREAL out := 1;
  REAL smaller fact := 2;
  REAL larger fact := largest+1;
  WHILE larger fact <= n DO # todo: check underflow here #
# try and prevent overflow, p.s. there must be a smarter way to do this #
    out *:= larger fact;
    WHILE smaller fact <= smallest ANDF out > smaller fact DO 
      out /:= smaller fact;
      smaller fact +:= 1
    OD;
    larger fact +:= 1
  OD;
  out # EXIT with: n P r OVER r P r #
);
END COMMENT
 
SKIP