/usr/share/ncarg/nclscripts/contrib/nchoosek.ncl is in libncarg-data 6.3.0-6build1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 | ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; nchoosek function
; Gabriel Abrahao: gabriel.abrahao@ufv.br
; Adapted from the original Martin Broadhurst's C code, that can be found at:
; http://www.martinbroadhurst.com/
;
; Prototype:
; function nchoosek (
; n :integer
; k :integer
; )
;
; return_val [n!/(k!(n-k)!),k]
;
; Returns all the k-combinations taken from the n-set {0:n-1}
;
; Uses: nextcombination (below)
;
; The algorithm is explained at : http://www.martinbroadhurst.com/combinatorial-algorithms.html#combinations
; In short:
; Begin with the combination containing the the numbers from 0 to k - 1, and at each step:
; -Find the rightmost element ar(i) that is less than the maximum value it can have (which is (n - 1) - (k - 1) - i)
; -Increment it
; -Turn the elements after it into a linear sequence continuing from ar(i)
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; nextcombination function
; Gabriel Abrahao: gabriel.abrahao@ufv.br
; Adapted from the original Martin Broadhurst's C code, that can be found at:
; http://www.martinbroadhurst.com/source/combination.c.html
;
; Takes a strictly increasing vector of k integers and finds the next k-combination in the lexicographical order,
; from the set {0:n-1}
;
; The algorithm is explained at : http://www.martinbroadhurst.com/combinatorial-algorithms.html#combinations
; In short, it does the step in the algorithm to find all combinations:
; Begin with the combination containing the the numbers from 0 to k - 1, and at each step:
; -Find the rightmost element ar(i) that is less than the maximum value it can have (which is (n - 1) - (k - 1) - i)
; -Increment it
; -Turn the elements after it into a linear sequence continuing from ar(i)
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
undef("nextcombination")
function nextcombination(n,k,ar)
begin
;n=5
;k=3
;ar=(/2,3,4/)
;ar=(/0,2,3/)
finished=0
changed=0
;do i=k-1,0,-1
i=k-1
do while(i .ge. 0)
if (finished .ne. 1 .and. changed .ne. 1) then
if ( ar(i) .lt. (n-1)-(k-1)+i ) then
;Increment ar(i)
ar(i)=ar(i)+1
if ( i .lt. k-1 ) then
;Turn elements after it into a linear sequence
do j=i+1,k-1,1
ar(j) = ar(j-1) + 1
end do
end if
changed=1
end if
else
break
end if
i=i-1
end do
return(ar)
end
undef("nchoosek")
function nchoosek(n,k)
begin
;Initializes from 0 to k-1
ini=ispan(0,k-1,1)
;Computes the total number of combinations using the gamma function for computing factorials (gamma(x)=(x-1)!)
ncomb = gamma(n+1)/(gamma(k+1)*gamma(n-k+1))
;Preallocates the matrix
combmat=new((/round(ncomb,3),k/),integer)
;Fills the matrix using nextcombination
combmat(0,:) = ini
do i=1,round(ncomb,3)-1
; The obvious line here would be:
; combmat(i,:) = nextcombination(n,k,combmat(i-1,:))
; but it doesn't work for some reason, so a dummy was used
dummy=combmat(i-1,:)
combmat(i,:) = nextcombination(n,k,dummy)
end do
return(combmat)
end
|