About me | pbdR Tech | HPSC | Phyloclustering | R_note |

R_note -- The Exploration of Statistical Software R (統計軟體 R 深度歷險)
About R_note
Reference
MS Windows

Batch jobs
Function
Data/MySQL
Plot
String/Parse

Remark Lines
Classes/S3
S4 Methods
Batch more
Environment

Good Coding
Fast Loop
LAM/MPI/Rmpi
Recursion

PHP Call R
Basic C
R Call Fortran/C
R Call GSL
C Call R API
C Call R Objects
Standalone

Make Packages
C Pointer
Debug




Section: Recursion

  • Reference
    See "Modern Applied Statistics with S-PLUS", 2ed, by W.N. Venables and B.D. Ripley.
    ISBN 0-387-98214-0 Springer-Verlag.
    Chapter 4.7, page 149-150.

  • Author's suggestion
    It should be used cautiously as it can lead to slow and memory-intensive code. In a few cases it can provide a neat and effective solution to an intrinsically recursive problem.

  • Example
    Generating all possible subsets of size r from a set of elements of size n.

    1. subsets 1
      If the size of the result is not too large an efficient way to do this is to store the subsets as the rows of an array. Here, create a file "subsets_1.r" as follows,

          
      # File name: subsets_1.r
      
      subsets <- function(r, n, v = 1 : n){
        if(r <= 0) NULL else
        if(r >= n) v[1 : n] else
        rbind(cbind(v[1], subsets(r - 1, n - 1, v[-1])),
                          subsets(r,     n - 1, v[-1]))
      }
      

    2. subsets 2
      If we re-assign the function body to another name and use the name "subsets" for something else, or discard it, our function body will cease to work. It would be useful to have a function body that continued to work regardless of the name given it. Here, create a file "subsets_2.r" as follows,

          
      # File name: subsets_2.r
      
      subsets <- function(r, n, v = 1 : n){
        if(r <= 0) NULL else
        if(r >= n) v[1 : n] else
        rbind(cbind(v[1], Recall(r - 1, n - 1, v[-1])),
                          Recall(r,     n - 1, v[-1]))
      }
      


  • R commands to list all combinations and permutations
    For R version 2.4 or newer, there are some commands that you can use to list all combinations by given total elements and how many you want to choose, and all permutations by given total elements.

        
    choose(10,5)         # compute choose(10,5)
    factoral(5)          # compute numbers of permutations of 5 elements
    
    library(combinat)
    combn(10,5)          # list all combinations of choose(10,5)
    permn(5)             # list all permutations of 5 elements
    
    library(gtools)
    combinations(10,5)   # list all combinations of choose(10,5)
    permutations(5,5)    # list all permutations of 5 elements
    permutations(5,3)    # list all permutations of the elements from choose(5,3)
                         # i.e. total C(5,3) * 3! possible outcomes
    



[ Go to top ]

Maintained: Wei-Chen Chen
E-Mail: wccsnow @ gmail.com
Last Revised: Dec 12 2016, 09:44 (CST Taipei, Taiwan)
Created: Oct 06 2003
free counters Best Resolution
IE6.0
1280x1024
small font