Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Does anyone knows a way to compute a list of all (p,q)-shuffles in mathematica?

For a definition of the shuffle permutations see for example http://ncatlab.org/nlab/show/shuffle

I'm dreaming of a function with p and q as arguments that gives me:

1.) The number of all (p,q)-shuffles.

2.) A list of the actual "shuffle" (p+q)-permutations

3.) The sign of each such permutation

share|improve this question
    
Let's see if we can do better than this mathhelpforum.com/math-software/… –  belisarius May 4 '12 at 4:24
    
Ok. Since this was asked before, I guess there is no such thing. –  Mark Neuhaus May 4 '12 at 4:33
    
But it was not asked here :D –  belisarius May 4 '12 at 4:34
    
Is there a package to work with general permutations? Then maybe I can use it as a starting point to write that function by myself. –  Mark Neuhaus May 4 '12 at 4:47
    
Very painfully inefficient: With[{p = 4, q = 5}, Union[Join[Sort[Take[#, p]], Sort[Take[#, -q]]] & /@ Permutations[Range[p + q]]]] –  J. M. May 4 '12 at 4:50

1 Answer 1

up vote 7 down vote accepted

1) The number of all (p,q) shuffles is

Binomial[p+q,p]

since when you chose the first p elements, the whole thing (and its order) is given.

2)The actual shuffles are given by: (See JM's comment below*)

With[{x = Range@#1}, {#, Complement[x, #]} & /@ Subsets[x, {#2}]] &[p + q, p]

Example:

p = 3; q = 2;
With[{x = Range@#1}, {#, Complement[x, #]} & /@ Subsets[x, {#2}]] &[p + q, p]

(*
->
{{{1, 2, 3}, {4, 5}}, {{1, 2, 4}, {3, 5}}, {{1, 2, 5}, {3, 4}}, {{1, 3, 4}, {2, 5}}, 
 {{1, 3, 5}, {2, 4}}, {{1, 4, 5}, {2, 3}}, {{2, 3, 4}, {1, 5}}, {{2, 3, 5}, {1, 4}}, 
 {{2, 4, 5}, {1, 3}}, {{3, 4, 5}, {1, 2}}}

3) The sign of each permutation (for the above shuffles) is given by:

Signature/@ With[{x=Range@#1}, Join[#, Complement[x, #]] & /@ Subsets[x, {#2}]] &[p+q,p]

Example:

p = 3; q = 2;
Signature/@ With[{x=Range@#1}, Join[#, Complement[x, #]] & /@ Subsets[x, {#2}]] &[p+q,p]
(*
-> {1, -1, 1, 1, -1, 1, -1, 1, -1, 1}
*)
share|improve this answer
    
mmm looking again ... all those p+q looks nasty. Lets see if I can improve –  belisarius May 4 '12 at 5:00
    
Signature[] is built-in; no need for an auxiliary package... –  J. M. May 4 '12 at 5:01
1  
@J.M. Thanks. I keep using Combinatorica ... old vice. Editing. –  belisarius May 4 '12 at 5:02
    
On that note: it might be a bit better if you don't generate Range[p + q] more than once: With[{pq = Range[p + q]}, Join[#, Complement[pq, #]] & /@ Subsets[pq, {p}]]. –  J. M. May 4 '12 at 5:09
    
@J.M. yep. I'm trying to keep it as a one liner function of p,q –  belisarius May 4 '12 at 5:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.