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

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

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.

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.

> On Mar 29, 2018, at 6: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? 
> 
Well half of these arrangements will be of the form 

	`k, ... , j, n' 

and half will be of the form 

	`j, ...,  k, n'

So fix n in position n, select (k,j), and require that the first position is
min(k,j) and position n-1 is max(k,j).

There are choose(n-1,2) choices for {(k,j):k<j!=n}. Then you have (n-3)! ways
to fill the rest.

That gives (n-1)!/((n-3)! * 2!) * (n-3)! = (n-1)!/2 arrangements.

HTH,

Chuck