Message Boards Message Boards

0
|
392 Views
|
11 Replies
|
3 Total Likes
View groups...
Share
Share this post:

Obtaining permutations in a circle

Posted 20 days ago

Permutations in a row or permutations in a line of n = 4 objects taking r = 3 at a time which is Length-3 permutations of {a,b,c,d} is obtained in Mathematica using Permutations[{a, b, c, d}, {3}].I do not know if Permutations[{a, b, c, d}, {3}] can be tweaked in Mathematica to obtain permutations in a circle of n=4 objects taking r=3 at a time. Regardless, how can permutations in a circle of n=4 objects taking r=3 at a time too be obtained in Mathematica?

POSTED BY: Yaw Antoa Onyina
11 Replies
Posted 18 days ago

I misunderstood. Deleted.

POSTED BY: Hans Milton

Put element 1 first. Permute 2,3,…,n. If first exceeds last, reverse them. Then list 1 followed by that (possibly reversed) permutation.

This assumes I understand the problem correctly.

POSTED BY: Daniel Lichtblau
Posted 19 days ago

You've described an approach when $r=n$. But I think the OP is also interested in $r<n$. (Although I'm not yet convinced that any reversing is necessary in the case you describe. I'll think about that a bit more.)

POSTED BY: Jim Baldwin

I do not know what it means to permute 3 of 4 elements. Keep one fixed?

As for reversals, (1,4,3,2) is the same on a circle as (1,2,3,4)— just travel ccw from 1 instead of cw.

POSTED BY: Daniel Lichtblau
Posted 19 days ago

Maybe I'm misunderstanding the OP's question. I interpret it that there are 4 persons showing up for dinner but you only have 3 chairs to seat them at a round table. I think the question is to generate all possible seating arrangements (with just 3 being seated at a time).

That means one would first find all of the ways 3 out of 4 dinner guests could be chosen. For each of those sets of 3, all possible circular arrangements would be generated. For this example that would be (3-1)! = 2 ways for each set of 3.

So I see the question being general for $n \geq r \geq 2$. For $n=r \geq 2$, one just has to fix 1 dinner guest and then permute the rest as usual resulting in $(n-1)!$ arrangements. No need for reversing.

But the OP will need to clarify.

POSTED BY: Jim Baldwin

Me, I don’t care if Fred is to my left and Sheila to my right, or vice versa. Both are gonna get cocktail sauce on them either way.

POSTED BY: Daniel Lichtblau
Posted 18 days ago

Lol. I'd love to be invited to your next party!

POSTED BY: Eric Rimbey

Yes BIG MAN DANIEL, to permute 3 of 4 elements and Keep one fixed as is required for permutations in a circle which uses the formula n combination r times (r-1) as opossed to permutations in a line or row which uses the formula n combination r times r

POSTED BY: Yaw Antoa Onyina

Per the question I was interested in r<n but then I want to believe that once it works for r<n it should work for r=n

POSTED BY: Yaw Antoa Onyina
Posted 19 days ago

Here's an alternative approach:

circlePermutations[object_, r_?IntegerQ] := Module[{t},
  If[r <= Length[object],
   t = {#[[1]], Permutations[#[[2 ;;]]]} & /@ Subsets[object, {r}];
   Flatten[MapThread[Join, {ConstantArray[{#[[1]]}, Length[#[[2]]]], #[[2]]}] & /@ t, 1],
   Print[ToString[r] <> " is greater than the length of " <> ToString[object] <> "."]]]

circlePermutations[{a, b, c, d}, 3]
(* {{a, b, c}, {a, c, b}, {a, b, d}, {a, d, b}, {a, c, d}, {a, d, c}, {b, c, d}, {b, d, c}} *)
POSTED BY: Jim Baldwin
Posted 20 days ago

I couldn't find any built in functions or options that would produce circle permutations. Here is a way to do it.

First, define a function that puts a permutation into some canonical order. I chose to rotate the permutation until its "minimal" element (by sort order) is first.

CanonicalizePermutation[perm_List] := 
  NestWhile[RotateLeft, perm, Not@*MatchQ[{1, ___}]@*Ordering]

If we take a list of permutations and put them all in this canonical form, we can then use Union or DeleteDuplicates or just DeleteDuplicatesBy.

DeleteDuplicatesBy[Permutations[{a, b, c, d}, {3}], CanonicalizePermutation]
(* {{a, b, c}, {a, b, d}, {a, c, b}, {a, c, d}, {a, d, b}, {a, d, c}, {b, c, d}, {b, d, c}} *)

DeleteDuplicates[CanonicalizePermutation /@ Permutations[{a, b, c, d}, {3}]]
(* {{a, b, c}, {a, b, d}, {a, c, b}, {a, c, d}, {a, d, b}, {a, d, c}, {b, c, d}, {b, d, c}} *)

Union[CanonicalizePermutation /@ Permutations[{a, b, c, d}, {3}]]
(* {{a, b, c}, {a, b, d}, {a, c, b}, {a, c, d}, {a, d, b}, {a, d, c}, {b, c, d}, {b, d, c}} *)
POSTED BY: Eric Rimbey
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract