[prev in list] [next in list] [prev in thread] [next in thread]
List: r-help
Subject: Re: [R] getting all circular arrangements without accounting for order
From: Ranjan Maitra <maitra () email ! com>
Date: 2018-03-30 21:13:40
Message-ID: 20180330161340.a785696373854234086b4b3a () email ! com
[Download RAW message or body]
Jeff,
Thanks! This one is much faster, no doubt!
system.time(directionless_circular_permutations2(12))
user system elapsed
5.331 0.745 6.089
system.time(directionless_circular_permutations(12))
user system elapsed
173.659 0.890 174.946
However, from n = 13, things start becoming slow.
system.time(directionless_circular_permutations2(13))
user system elapsed
60.588 14.933 75.864
Perhaps the loop can be parallelized using doMC or doSNOW, etc. but most likely it is \
best to do a .Call or .C or Rcpp as you suggested earlier. This may be a consequence \
of the permutations function itself being slow.
Thanks again!
Ranjan
On Fri, 30 Mar 2018 13:49:01 -0700 Jeff Newmiller <jdnewmil@dcn.davis.ca.us> wrote:
> New function below is a bit faster due to more efficent memory handling.
>
> for-loop FTW!
>
> directionless_circular_permutations2 <- function( n ) {
> n1 <- n - 1L
> v <- seq.int( n1 )
> ix <- combinations( n1, 2L )
> jx <- permutations( n-3L, n-3L )
> jxrows <- nrow( jx )
> jxoffsets <- seq.int( jxrows )
> result <- matrix( n, nrow = factorial( n1 )/2L, ncol = n )
> k <- seq( 2L, n - 2L )
> for ( i in seq.int( nrow( ix ) ) ) {
> result[ ( i - 1L ) * jxrows + jxoffsets, k ] <-
> matrix( v[ -ix[ i, ] ][ jx ], nrow = jxrows )
> }
> result[ , 1L ] <- rep( ix[ , 1L ], each = jxrows )
> result[ , n1 ] <- rep( ix[ , 2L ], each = jxrows )
> result
> }
>
>
> On Fri, 30 Mar 2018, Ranjan Maitra wrote:
>
> > Jeff,
> >
> > I wanted to let you know that your function is faster than generating
> > the directional circular permutations and weeding.
> >
> > Here is the time for n = 10. I compared with just doing the
> > permutations, there is no point in proceeding further with the weeding
> > since it is slower at the start itself.
> >
> >
> > system.time(directionless_circular_permutations(10))
> > user system elapsed
> > 1.576 0.000 1.579
> >
> > system.time(permutations(9,9))
> > user system elapsed
> > 3.030 0.000 3.037
> >
> > Repeats keep the values similar. All computations on a 10-core processor
> > @3.1GHz with 20 threads (using only one thread) and running the Fedora
> > 27 with 4.15.9 kernel.
> >
> > I have to say that I was surprised to see the difference at n = 10 itself.
> >
> > Thanks again!
> >
> > Best wishes,
> > Ranjan
> >
> > On Thu, 29 Mar 2018 23:26:12 -0700 Jeff Newmiller <jdnewmil@dcn.davis.ca.us> \
> > wrote:
> > > I don't know if this is more efficient than enumerating with distinct
> > > directions and weeding... it seems kind of heavyweight to me:
> > >
> > > #######
> > > library(gtools)
> > > directionless_circular_permutations <- function( n ) {
> > > v <- seq.int( n-1 )
> > > ix <- combinations( n-1, 2 )
> > > jx <- permutations( n-3, n-3 )
> > > x <- lapply( seq.int( nrow( ix ) )
> > > , function( i ) {
> > > cbind( ix[ i, 1 ]
> > > , permutations( n-3
> > > , n-3
> > > , v[ -ix[ i, ] ]
> > > )
> > > , ix[ i, 2 ]
> > > )
> > > }
> > > )
> > > cbind( do.call( rbind, x ), n )
> > > }
> > > #######
> > >
> > > For more speed, perhaps use Rcpp with [1]?
> > >
> > > [1] http://howardhinnant.github.io/combinations.html
> > >
> > > On Thu, 29 Mar 2018, Ranjan Maitra wrote:
> > >
> > > > Thanks!
> > > >
> > > > Yes, however, this seems a bit wasteful. Just wondering if there are
> > > > other, more efficient options possible.
> > > >
> > > > Best wishes,
> > > > Ranjan
> > > >
> > > >
> > > > On Thu, 29 Mar 2018 22:20:19 -0400 Boris Steipe <boris.steipe@utoronto.ca> \
> > > > wrote:
> > > > > If one is equal to the reverse of another, keep only one of the pair.
> > > > >
> > > > > B.
> > > > >
> > > > >
> > > > >
> > > > > > On Mar 29, 2018, at 9:48 PM, Ranjan Maitra <maitra@email.com> wrote:
> > > > > >
> > > > > > Dear friends,
> > > > > >
> > > > > > I would like to get all possible arrangements of n objects listed 1:n on \
> > > > > > a circle.
> > > > > > Now this is easy to do in R. Keep the last spot fixed at n and fill in \
> > > > > > the rest using permuations(n-1, n-1) from the gtools package.
> > > > > > However, what if clockwise or counterclockwise arrangements are the same? \
> > > > > > I know that half of the above (n - 1)! arrangements are redundant.
> > > > > > Is there an easy way to list these (n-1)!/2 arrangements?
> > > > > >
> > > > > > I thought of only listing the first half from a call to permuations(n - \
> > > > > > 1, n - 1), but while this holds for n = 4, it does not for n = 5. So, I \
> > > > > > am wondering if there is another function or tweak which would easily do \
> > > > > > this.
> > > > > > Many thanks in advance for any help. and best wishes,
> > > > > > Ranjan
> > > > > >
> > > > > > ______________________________________________
> > > > > > R-help@r-project.org mailing list -- To UNSUBSCRIBE and more, see
> > > > > > 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.
> > > > >
> > > > > ______________________________________________
> > > > > R-help@r-project.org mailing list -- To UNSUBSCRIBE and more, see
> > > > > 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.
> > > >
> > > >
> > > > --
> > > > Important Notice: This mailbox is ignored: e-mails are set to be deleted on \
> > > > receipt. Please respond to the mailing list if appropriate. For those needing \
> > > > to send personal or professional e-mail, please use appropriate addresses.
> > > > ______________________________________________
> > > > R-help@r-project.org mailing list -- To UNSUBSCRIBE and more, see
> > > > 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.
> > > >
> > >
> > > ---------------------------------------------------------------------------
> > > Jeff Newmiller The ..... ..... Go Live...
> > > DCN:<jdnewmil@dcn.davis.ca.us> Basics: ##.#. ##.#. Live Go...
> > > Live: OO#.. Dead: OO#.. Playing
> > > Research Engineer (Solar/Batteries O.O#. #.O#. with
> > > /Software/Embedded Controllers) .OO#. .OO#. rocks...1k
> > >
> > > ______________________________________________
> > > R-help@r-project.org mailing list -- To UNSUBSCRIBE and more, see
> > > 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.
> > >
> >
> >
> > --
> > Important Notice: This mailbox is ignored: e-mails are set to be deleted on \
> > receipt. Please respond to the mailing list if appropriate. For those needing to \
> > send personal or professional e-mail, please use appropriate addresses.
> > ______________________________________________
> > R-help@r-project.org mailing list -- To UNSUBSCRIBE and more, see
> > 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.
> >
>
> ---------------------------------------------------------------------------
> Jeff Newmiller The ..... ..... Go Live...
> DCN:<jdnewmil@dcn.davis.ca.us> Basics: ##.#. ##.#. Live Go...
> Live: OO#.. Dead: OO#.. Playing
> Research Engineer (Solar/Batteries O.O#. #.O#. with
> /Software/Embedded Controllers) .OO#. .OO#. rocks...1k
>
> ______________________________________________
> R-help@r-project.org mailing list -- To UNSUBSCRIBE and more, see
> 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.
>
--
Important Notice: This mailbox is ignored: e-mails are set to be deleted on receipt. \
Please respond to the mailing list if appropriate. For those needing to send personal \
or professional e-mail, please use appropriate addresses.
______________________________________________
R-help@r-project.org mailing list -- To UNSUBSCRIBE and more, see
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.
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic