Mindanao State University

General Santos City

Philippines

Introduction

In the area of Discrete Mathematics there is an elegant problem about having a random set with random number of elements.

The problem is about finding a sequence of consecutive elements in the random set that gives the maximum possible sum.

I was using the R language because I can easily share the result in the web. R is a excellent statistical programming language which is accessible to everybody.

I am developing this short but elegant solution for the purpose of training my students which are enrolled in basic programming course.

To other students, somewhere out there, this example will help you understand the challenge of building nested for loops which is essential for learning any programming language.

This is my algorithm for solving the problem.

password_creator = function(RandomSet,Size){
  
  # declare containers
  dat <- list()
  Sums <- list()
  txtdata <- NULL
  counter = 0
  
  
  # Gather all elements of the random set as a single value
  # that is values are gathered without a comma
  # 
  Reference_Set <- RandomSet[1]
  for (i in 2:length(RandomSet)){
    Reference_Set <- paste0(Reference_Set," ",RandomSet[i])
  }
  
  
  # start generating all possible subsets of
  # consecutive elements
  
  for (j in 2:Size){   
    for (i in 1:(Size-(j-1))){
      data <- RandomSet[i]
      txtdat <- RandomSet[i]
      for (k in 1:(j-1)){
        
        # accumulate data as a vector
        data <- c(data, RandomSet[i+k])
        
        # accumulate data as a single value
        txtdat <- paste0(txtdat," ",RandomSet[i+k])
      }
      
      # fill up the temporary containers
      counter = counter + 1
      
      # store the data into a list
      dat[[counter]] <- data
      
      # Compute the sum of terms
      Sums[[counter]] <- sum(data)
      
      # store the text data into a list
      txtdata[counter] <- txtdat
    }
  }
  
  # Sums is a list but I want the actual values 
  # so I have to convert to single array format
  # using the unlist command
  
  Sumseq <- unlist(Sums)
  
  # convert array to dataframe because I 
  # want to get the corresponding index number 
  Sumseq <- as.data.frame(Sumseq)
  head(Sumseq)
  
  
  # pull out the index numbers and put it inside the dataframe
  # the index numbers are actually the row names
  # 
  
  Sums <- cbind(row.names(Sumseq),Sumseq,txtdata,counter,Reference_Set)
  tail(Sums)
  
  # rename the column heading
  colnames(Sums) <- c("Index","Sumseq","Sequence","Num_Subsets","Random_Set")
  tail(Sums)
  
  # Be sure that the column index is a numeric
  Sums$Index <- as.numeric(Sums$Index)
  
  
  # arrange the dataset according to highest sum
  suppressPackageStartupMessages(library(dplyr))
  (max_sum <- arrange(Sums,Sumseq))
  
  
  # the highest sum occurs at the last row, so pick
  # all values in the last row
  (last_row_values <- max_sum[nrow(max_sum),])

  # send the result to the boss
  return(last_row_values)
}


# You must run first the entire function above so that the 
# codes below will run


# You are the boss and you want to create a dynamic password
# with the property that the sun is maximum out of the possible
# sequence of consecutive elements

# Process 100 passwords
(UniversalSet <- -100:100)
##   [1] -100  -99  -98  -97  -96  -95  -94  -93  -92  -91  -90  -89  -88  -87  -86
##  [16]  -85  -84  -83  -82  -81  -80  -79  -78  -77  -76  -75  -74  -73  -72  -71
##  [31]  -70  -69  -68  -67  -66  -65  -64  -63  -62  -61  -60  -59  -58  -57  -56
##  [46]  -55  -54  -53  -52  -51  -50  -49  -48  -47  -46  -45  -44  -43  -42  -41
##  [61]  -40  -39  -38  -37  -36  -35  -34  -33  -32  -31  -30  -29  -28  -27  -26
##  [76]  -25  -24  -23  -22  -21  -20  -19  -18  -17  -16  -15  -14  -13  -12  -11
##  [91]  -10   -9   -8   -7   -6   -5   -4   -3   -2   -1    0    1    2    3    4
## [106]    5    6    7    8    9   10   11   12   13   14   15   16   17   18   19
## [121]   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34
## [136]   35   36   37   38   39   40   41   42   43   44   45   46   47   48   49
## [151]   50   51   52   53   54   55   56   57   58   59   60   61   62   63   64
## [166]   65   66   67   68   69   70   71   72   73   74   75   76   77   78   79
## [181]   80   81   82   83   84   85   86   87   88   89   90   91   92   93   94
## [196]   95   96   97   98   99  100
Container = matrix("",nrow=100,ncol=4)



# define marker If you want to get the same result
# as you run the module for several times
set.seed(123)



# I want to process 100 RandomSets of length between 10 to 20
for (n in 1:100){
  
    # n=1
    # pick any number from 10 to 20 as maximum size of a subset
    Size <- sample(10:20,1)
    
    
    # Generate the elements of a random subset using sample command
    RandomSet <- sample(UniversalSet,Size,rep=FALSE)
    
    
    # Function call that will return the sequence with the highest
    # possible sum 
    result <- password_creator(RandomSet,Size)
    

    # Deposit result to container per random set generated 
    Container[n,1] <- paste0( "Number ", result$Index, " out of ", result$Num_Subsets," subsets") 
    Container[n,2] <- result$Sum
    Container[n,3] <- result$Sequence
    Container[n,4] <- result$Random_Set
 
}

Container <- as.data.frame(Container)
colnames(Container) <- c("Details","Max_Sum","Consecutive Elements","Random_Set")


# Present as a nice table
suppressPackageStartupMessages(library(flextable))
Container <- flextable(Container)
Container <- autofit(Container)
Container <- theme_box(Container)

Final result

This table contains the list of consecutive integers that gives the maximum sum for any random set of positive or negative integers.