R help - Mar 2018 - getting all circular arrangements without accounting for order

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 at
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 at
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 at
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 at 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 at 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 at 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 at 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 at 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.

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 at
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 at
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 at
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 at 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 at 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 at 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 at 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 at 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 at 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 at 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

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 at
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 at
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 at 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
at 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 at 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 at 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 at 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 at 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 at 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 at 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 at 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 at 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.