R help - Sep 2007 - programming question

Dear list,

I have a vector of numbers, let's say:

myvec <- c(2, 8, 24, 26, 51, 57, 58, 78, 219)

My task is to reduce this vector to non-reducible numbers; small numbers can 
cross-out some of the larger ones, based on a function let's say called 
reduce()

If I apply the function to the first element 2, my vector gets shorted
to:
> (myvec <- reduce(myvec[1]))
 [1]   2   24   51   57   58   78  219

The next element that can further reduce the vector is the second (24) and a 
next iteration further reduces it and so on, until nothing can be reduced.

The question is, what is the best programming technique to achieve this?

My crude solution is:
####
position <- 1 # start with the first position in the vector (smallest number)
while(position < length(myvec)) {
    myvec <- reduce(myvec[position])
    position <- position + 1
    }
####

Is there a better programming approach?
Some vectors have lengths of millions, so this one takes a very long time.

Thanks in advance,
Adrian



PS: below is a self-contained example:
The initial vector corresponds to the following lines in a base 3 matrix:
      [,1] [,2] [,3] [,4] [,5]
   2     0    0    0    0    2
   8     0    0    0    2    2
  24     0    0    2    2    0
  26     0    0    2    2    2
  51     0    1    2    2    0
  57     0    2    0    1    0
  58     0    2    0    1    1
  78     0    2    2    2    0
 219     2    2    0    1    0

In the first iteration, the first element 2 eliminates 8 and 26 because both 
contain number 2 in the last position (first line being shorter).
The element 24 eliminates 51 and 78, and so on.

`findSubsets2` <-
function(element) {
    require(QCA)
    base3row <- getRow(rep(3,5), element, zerobased=TRUE)
    increment <- function(x, y) {
        a <- x
        for (i in 1:2) {
            a <- as.vector(outer(y, a, "+"))
            x <- c(x, a)
            }
        return(x)
        }
    indices <- which(base3row == 0)
    mbase <- c(81, 27, 9, 3, 1)
    for (i in indices) {
        element <- increment(element, mbase[i])
        }
    return(element[-1])
    }

position <- 1
while(position < length(myvec)) {
    falsevector <- findSubsets2(myvec[position])
    myvec <- setdiff(myvec, falsevector)
    position <- position + 1
    }




-- 
Adrian Dusa
Romanian Social Data Archive
1, Schitu Magureanu Bd
050025 Bucharest sector 5
Romania
Tel./Fax: +40 21 3126618 \
          +40 21 3120210 / int.101

R 2.6.0 has Reduce;

myvec <- c(2, 8, 24, 26, 51, 57, 58, 78, 219)
Reduce(function(myvec, p) setdiff(myvec, findSubsets2(p)), myvec, myvec)


On 9/16/07, Adrian Dusa <dusa.adrian at gmail.com>
wrote:
>
> Dear list,
>
> I have a vector of numbers, let's say:
>
> myvec <- c(2, 8, 24, 26, 51, 57, 58, 78, 219)
>
> My task is to reduce this vector to non-reducible numbers; small numbers
can
> cross-out some of the larger ones, based on a function let's say called
> reduce()
>
> If I apply the function to the first element 2, my vector gets shorted to:
> > (myvec <- reduce(myvec[1]))
>  [1]   2   24   51   57   58   78  219
>
> The next element that can further reduce the vector is the second (24) and
a
> next iteration further reduces it and so on, until nothing can be reduced.
>
> The question is, what is the best programming technique to achieve this?
>
> My crude solution is:
> ####
> position <- 1 # start with the first position in the vector (smallest
number)
> while(position < length(myvec)) {
>    myvec <- reduce(myvec[position])
>    position <- position + 1
>    }
> ####
>
> Is there a better programming approach?
> Some vectors have lengths of millions, so this one takes a very long time.
>
> Thanks in advance,
> Adrian
>
>
>
> PS: below is a self-contained example:
> The initial vector corresponds to the following lines in a base 3 matrix:
>      [,1] [,2] [,3] [,4] [,5]
>   2     0    0    0    0    2
>   8     0    0    0    2    2
>  24     0    0    2    2    0
>  26     0    0    2    2    2
>  51     0    1    2    2    0
>  57     0    2    0    1    0
>  58     0    2    0    1    1
>  78     0    2    2    2    0
>  219     2    2    0    1    0
>
> In the first iteration, the first element 2 eliminates 8 and 26 because
both
> contain number 2 in the last position (first line being shorter).
> The element 24 eliminates 51 and 78, and so on.
>
> `findSubsets2` <-
> function(element) {
>    require(QCA)
>    base3row <- getRow(rep(3,5), element, zerobased=TRUE)
>    increment <- function(x, y) {
>        a <- x
>        for (i in 1:2) {
>            a <- as.vector(outer(y, a, "+"))
>            x <- c(x, a)
>            }
>        return(x)
>        }
>    indices <- which(base3row == 0)
>    mbase <- c(81, 27, 9, 3, 1)
>    for (i in indices) {
>        element <- increment(element, mbase[i])
>        }
>    return(element[-1])
>    }
>
> position <- 1
> while(position < length(myvec)) {
>    falsevector <- findSubsets2(myvec[position])
>    myvec <- setdiff(myvec, falsevector)
>    position <- position + 1
>    }
>
>
>
>
> --
> Adrian Dusa
> Romanian Social Data Archive
> 1, Schitu Magureanu Bd
> 050025 Bucharest sector 5
> Romania
> Tel./Fax: +40 21 3126618 \
>          +40 21 3120210 / int.101
>
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
>