Combinatorics

Use this forum to post questions about syntax problems or general programming issues. Questions on implementing a particular aspect of econometrics should go in "Econometrics Issues" below.
jonasdovern
Posts: 97
Joined: Sat Apr 11, 2009 10:30 am

Combinatorics

Unread post by jonasdovern »

Dear RATS-user,

does anybody have a nice piece of code to "run through" the possible combinations of a "n choose k" problem? Say I have an index of dimension N pointing to a set of regressors. Now, I would like to estimate all equations that have possible combinations of k of those regressors as explanatory variables. I guess I have to do multiple loops over n=1,N. Any hint on how to program this efficiently? Best, Jonas.

Code: Select all

*My guess for structure of the code:
decl vec[int] reglist
decl vec[equ] eqn(%factorial(N)/(%factorial(k)*%factorial(N-k))

comp counter = 1
* Some part of the loop-structure
   comp reglist = %rlempty()
   * Some part of the loop-structure
       * Fill reglist with new combination of regressors
       linreg(define=eqn(counter)) depvar
       # constant reglist
       compute counter=counter+1
* Close all loops


TomDoan
Posts: 7814
Joined: Wed Nov 01, 2006 4:36 pm

Re: Combinatorics

Unread post by TomDoan »

The code below is something relatively close. If all you really need out of the regressions is the sum of squared residuals, you can do that with:

LINREG Y
# list of all X's
CMOM(LASTREG)
loop from below generating combinations
COMPUTE SXX=%SWEEPLIST(%CMOM,PICK)
COMPUTE RSS=SXX(%NCMOM,%NCMOM)
do something with RSS
finish loop
end loop

Code: Select all

* This code sample demonstates a method for selecting a valid set of 
* instruments for a GMM where some of the moment conditions are suspected 
* of being incorrect.
*
* It is based on a recent paper by Donald Andrews, entitled "Consistent 
* Moment Selection Procedures for Generalized Method of Moments Estimation." 
* Econometrica, Vol. 67, No. 3, pp 543-564. To do this precisely as 
* described by Andrews requires running GMM with all subsets of a given 
* size out of the instrument set. The following code provides a systematic
* method for generating such subsets.
*
* Most of the code is written to be as general as possible. In this 
* particular example, we demonstrate the use of the "pos" index to set 
* up MASK arrays for a GMM estimated using the NLSYSTEM command.
*
* Note that this is not a complete program--you need to add instructions 
* to read in your data, do any transformations, etc. For the NLSYSTEM case, 
* as shown here, you will also need to define your non-linear parameters, 
* and define the formula to be estimated (we refer to it as "mygmmfrml" 
* in the NLSYSTEM command included below):
*
* The sections of code specific to this application (i.e. the sections 
* which need to be changed for other applications) are bracketed 
* by "*******************" lines.
*
* Written by Estima
*  August, 1999
*

declare vect[int] pos
*
* pop is the population size (10 in this example)
* pick is the number of items to be picked
*
compute pop =10
compute pick=5
dim pos(pick)

*****************************************************************
* Variable definitions specific to this example:
*
  * Set up the MASK array to be used for this particular application:
   dec rect mask(pop,1)
 * Initialize bookkeepping variable:
    compute bestuzwzu=-1.0
*
* End of application-specific variable definitions
*****************************************************************

*
* start with 1,2,...,pick. The vector of integers "pos" is always filled with an increasing
* sequence of values between 1 and pop.
*
ewise pos(i)=i
*
compute fixpos=pick
begin {
   loop {
*****************************************************************
* Insert code here to do what you want with the indexes in pos. In this example, we
*  specify the masking arraying and estimate using NLSYTEM:
      compute mask=%const(0.0)
      do j=1,pick
         compute mask(pos(j),1)=1.0
      end do j
      nlsystem(mask=mask,zudep,instruments,noprint) / mygmmfrml
     if bestuzwzu<0.or.%uzwzu<bestuzwzu
        compute bestuzwzu=%uzwzu,bestset=pos
*   End of inserted code section
*****************************************************************

*
*        When we hit the end of the range for a slot,
*        back up to the nearest preceding slot which still
*        can be incremented.
*
      while (fixpos>=1.and.pos(fixpos)==pop+fixpos-pick)
         compute fixpos=fixpos-1
*
*        If all slots are at their limit, we're done.
*
      if fixpos==0
         break
*
*        Increment the selected slot by one, and set all
*        following slots to their preceding slot plus one.
*
      compute pos(fixpos)=pos(fixpos)+1
      do j=1,pick-fixpos
         compute pos(fixpos+j)=pos(fixpos)+j
      end do j
      compute fixpos=pick
   }
}
jonasdovern
Posts: 97
Joined: Sat Apr 11, 2009 10:30 am

Re: Combinatorics

Unread post by jonasdovern »

Thanks for the example code. I could adjust it to my problem. I think, however, your code is missing one combination, namely the initial

Code: Select all

ewise pos(i)=i
specification. You end up with only pop!/(pick!(pop-pick)!)-1 combinations! I adjusted that by including a counter and added the statement

Code: Select all

if counter<>0
just before the

Code: Select all

compute pos(fixpos)=pos(fixpos)+1
statement. Best, Jonas
Post Reply