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

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.

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

Thanks! 

It is not clear to me that the weeding step is straightforward to do
efficiently. Comparing using rev appears to me to be an operation on the order
of O(n^3).

I guess one way would be to include everything with all 1's in the first
slot (taking them out of consideration for future operations) and eliminate
everything with 1's in the last slot. Then go for the 2's and so on,
perhaps ending until nothing left. This looks like an O(n) operation, however I
do not know if I will be missing something.

Many thanks again and 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.

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.