C      ALGORITHM 448, COLLECTED ALGORITHMS FROM ACM.
C      THIS WORK PUBLISHED IN COMMUNICATIONS OF THE ACM
C      VOL. 16, NO. 6, June, 1973, P.379.
#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create the files:
#	Fortran/
#	Fortran/Sp/
#	Fortran/Sp/Drivers/
#	Fortran/Sp/Drivers/Makefile
#	Fortran/Sp/Drivers/driver.f
#	Fortran/Sp/Drivers/res
#	Fortran/Sp/Src/
#	Fortran/Sp/Src/src.f
# This archive created: Thu Dec 15 13:28:15 2005
export PATH; PATH=/bin:$PATH
if test ! -d 'Fortran'
then
	mkdir 'Fortran'
fi
cd 'Fortran'
if test ! -d 'Sp'
then
	mkdir 'Sp'
fi
cd 'Sp'
if test ! -d 'Drivers'
then
	mkdir 'Drivers'
fi
cd 'Drivers'
if test -f 'Makefile'
then
	echo shar: will not over-write existing file "'Makefile'"
else
cat << "SHAR_EOF" > 'Makefile'
all: Res

src.o: src.f
	$(F77) $(F77OPTS) -c src.f

driver.o: driver.f
	$(F77) $(F77OPTS) -c driver.f

DRIVERS= driver
RESULTS= Res

Objs1= driver.o src.o
driver: $(Objs1)
	$(F77) $(F77OPTS) -o driver $(Objs1) $(SRCLIBS)
Res: driver 
	./driver >Res

diffres:Res res
	echo "Differences in results from driver"
	$(DIFF) Res res

clean: 
	rm -rf *.o $(DRIVERS) $(CLEANUP) $(RESULTS)
SHAR_EOF
fi # end of overwriting check
if test -f 'driver.f'
then
	echo shar: will not over-write existing file "'driver.f'"
else
cat << "SHAR_EOF" > 'driver.f'
      program main

c***********************************************************************
c
cc TOMS448_PRB tests COUNT.
c
      implicit none

      integer k_max
      integer n_max

      parameter ( k_max = 10 )
      parameter ( n_max = 100 )

      integer c(k_max)
      external count
      integer i
      integer k
      integer n
      integer p(n_max)

      write ( *, '(a)' ) ' '
      write ( *, '(a)' ) 'TOMS448_PRB'
      write ( *, '(a)' ) '  Test TOMS algorithm 448, number of'
      write ( *, '(a)' ) '  partitions of an integer '
      write ( *, '(a)' ) '  restricted to a set C.'

      write ( *, '(a)' ) ' '
      write ( *, '(a)' ) 'Test 1:'
      write ( *, '(a)' ) '  Let C = 1, 2, 3, ..., N'
      write ( *, '(a)' ) ' '

      n = 10
      k = 10

      do i = 1, k
        c(i) = i
      end do

      call count ( c, k, p, n )

      write ( *, '(a)' ) ' '
      write ( *, '(a)' ) '       I    P(I)'
      write ( *, '(a)' ) ' '
      do i = 1, n
        write ( *, '(2x,i6,2x,i6)' ) i, p(i)
      end do

      write ( *, '(a)' ) ' '
      write ( *, '(a)' ) 'Test 2:'
      write ( *, '(a)' ) '  Let C = 1, 3, 5, 7, ( N + 1 ) / 2'
      write ( *, '(a)' ) ' '

      n = 10
      k = ( n + 1 ) / 2

      do i = 1, k
        c(i) = 2 * i - 1
      end do

      call count ( c, k, p, n )

      write ( *, '(a)' ) ' '
      write ( *, '(a)' ) '       I    P(I)'
      write ( *, '(a)' ) ' '
      do i = 1, n
        write ( *, '(2x,i6,2x,i6)' ) i, p(i)
      end do

      write ( *, '(a)' ) ' '
      write ( *, '(a)' ) 'Test 3:'
      write ( *, '(a)' ) '  Let C = 1, 2, 2'
      write ( *, '(a)' ) ' '

      n = 10
      k = 3

      c(1) = 1
      c(2) = 2
      c(3) = 2

      call count ( c, k, p, n )

      write ( *, '(a)' ) ' '
      write ( *, '(a)' ) '       I    P(I)'
      write ( *, '(a)' ) ' '
      do i = 1, n
        write ( *, '(2x,i6,2x,i6)' ) i, p(i)
      end do

      write ( *, '(a)' ) ' '
      write ( *, '(a)' ) 'Test 4:'
      write ( *, '(a)' ) '  Let C = 1, 5, 10, 25, 50, 100'
      write ( *, '(a)' ) ' '

      n = 100
      k = 6

      c(1) = 1
      c(2) = 5
      c(3) = 10
      c(4) = 25
      c(5) = 50
      c(6) = 100

      call count ( c, k, p, n )

      write ( *, '(a)' ) ' '
      write ( *, '(a)' ) '       I    P(I)'
      write ( *, '(a)' ) ' '
      do i = 1, n
        write ( *, '(2x,i6,2x,i6)' ) i, p(i)
      end do

      write ( *, '(a)' ) ' '
      write ( *, '(a)' ) 'TOMS448_PRB'
      write ( *, '(a)' ) '  Normal end of execution.'

      stop
      end

SHAR_EOF
fi # end of overwriting check
if test -f 'res'
then
	echo shar: will not over-write existing file "'res'"
else
cat << "SHAR_EOF" > 'res'
 
TOMS448_PRB
  Test TOMS algorithm 448, number of
  partitions of an integer 
  restricted to a set C.
 
Test 1:
  Let C = 1, 2, 3, ..., N
 
 
       I    P(I)
 
       1       1
       2       2
       3       3
       4       5
       5       7
       6      11
       7      15
       8      22
       9      30
      10      42
 
Test 2:
  Let C = 1, 3, 5, 7, ( N + 1 ) / 2
 
 
       I    P(I)
 
       1       1
       2       1
       3       2
       4       2
       5       3
       6       4
       7       5
       8       6
       9       8
      10      10
 
Test 3:
  Let C = 1, 2, 2
 
 
       I    P(I)
 
       1       1
       2       3
       3       3
       4       6
       5       6
       6      10
       7      10
       8      15
       9      15
      10      21
 
Test 4:
  Let C = 1, 5, 10, 25, 50, 100
 
 
       I    P(I)
 
       1       1
       2       1
       3       1
       4       1
       5       2
       6       2
       7       2
       8       2
       9       2
      10       4
      11       4
      12       4
      13       4
      14       4
      15       6
      16       6
      17       6
      18       6
      19       6
      20       9
      21       9
      22       9
      23       9
      24       9
      25      13
      26      13
      27      13
      28      13
      29      13
      30      18
      31      18
      32      18
      33      18
      34      18
      35      24
      36      24
      37      24
      38      24
      39      24
      40      31
      41      31
      42      31
      43      31
      44      31
      45      39
      46      39
      47      39
      48      39
      49      39
      50      50
      51      50
      52      50
      53      50
      54      50
      55      62
      56      62
      57      62
      58      62
      59      62
      60      77
      61      77
      62      77
      63      77
      64      77
      65      93
      66      93
      67      93
      68      93
      69      93
      70     112
      71     112
      72     112
      73     112
      74     112
      75     134
      76     134
      77     134
      78     134
      79     134
      80     159
      81     159
      82     159
      83     159
      84     159
      85     187
      86     187
      87     187
      88     187
      89     187
      90     218
      91     218
      92     218
      93     218
      94     218
      95     252
      96     252
      97     252
      98     252
      99     252
     100     293
 
TOMS448_PRB
  Normal end of execution.
SHAR_EOF
fi # end of overwriting check
cd ..
if test ! -d 'Src'
then
	mkdir 'Src'
fi
cd 'Src'
if test -f 'src.f'
then
	echo shar: will not over-write existing file "'src.f'"
else
cat << "SHAR_EOF" > 'src.f'
      SUBROUTINE COUNT ( C, K, P, N )
      INTEGER C, P, K, N, I, J, JP1, M, MMJ
      DIMENSION C(K), P(N)
C  COUNT COMPUTES THE NUMBER OF PARTITIONS OF AN INTEGER
C  RESTRICTED TO C FOR INTEGERS IN THE RANGE 1 TO N.
C  INPUT:  K -- A POSITIVE INTEGER.
C          C -- AN ARRAY OF K POSITIVE INTEGERS.
C          N -- AN INTEGER LARGER THAN THE MAXIMUM VALUE IN C.
C  OUTPUT: P -- AN ARRAY OF N INTEGERS, WHERE P(M) IS THE
C               NUMBER OF PARTITIONS OF M RESTRICTED TO C.
C  INITIALIZE P
      DO 10 I = 1, N
        P(I) = 0
10    CONTINUE
C  EACH PASS THROUGH THE OUTER LOOP BELOW TRANSFORMS P FROM
C  PARTITIONS RESTRICTED TO C(1), ..., C(I-1) TO
C  PARTITIONS RESTRICTED TO C(1), ..., C(I).
      DO 30 I = 1, K
        J = C(I)
        JP1 = J + 1
        P(J) = P(J) + 1
        DO 20 M = JP1, N
          MMJ = M - J
          P(M) = P(M) + P(MMJ)
20      CONTINUE
30    CONTINUE
      RETURN
      END

SHAR_EOF
fi # end of overwriting check
cd ..
cd ..
cd ..
#       End of shell archive
exit 0