[R] getting all circular arrangements without accounting for order
Jeff Newmiller
jdnewmil at dcn.davis.ca.us
Fri Mar 30 22:49:01 CEST 2018
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
More information about the R-help
mailing list