2
$\begingroup$

I would like MMA to only calculate some of the permutations of a set. I am currently doing something along the lines of

Permutations[Flatten[{Array[1 &, #], Array[0 &, # (# - 1)]}, 1]] &@3

and using Take and Drop before performing further calculation on smaller set.

For $n=3$ as above, this is fine, but since hte above calculation gives ${n^2}\choose{n}$ different permutations, asking MMA to calculate anything above $n=6$ results in SystemException["MemoryAllocationFailure"].

I don't know the algorithm used to calculate Permutations, but is there any way of calculating and returning only permutations between x and y?

$\endgroup$
12
  • 1
    $\begingroup$ the Combinatorica package has a function called NextPermutation $\endgroup$
    – vapor
    Commented Mar 18, 2017 at 7:10
  • $\begingroup$ @happyfish ...only problem is, I dont know what previous permutation was! - should work for x==1, but not for say, $1000$ permutations around x==n^2. $\endgroup$
    – martin
    Commented Mar 18, 2017 at 7:13
  • $\begingroup$ I thought you can iterate over x, but never mind, you can try UnrankPermutation, it looks more suitable here, $\endgroup$
    – vapor
    Commented Mar 18, 2017 at 7:15
  • 1
    $\begingroup$ I will try to write an algorithm $\endgroup$
    – vapor
    Commented Mar 18, 2017 at 7:30
  • 1
    $\begingroup$ martin, I missed the fact that this was specific to binary permutations. Thank you for editing the title. @happyfish No, nothing you need to do; thanks for asking. $\endgroup$
    – Mr.Wizard
    Commented Mar 19, 2017 at 8:00

1 Answer 1

3
$\begingroup$

This function will only work for binary permutations

permutationChunk[total_, select_, start_, end_] := 
 ReplacePart[ConstantArray[0, total], Thread[# -> 1]] & /@ 
  Subsets[Range[total], {select}, {start, end}]

total is the length of the list, select is the number of 1s. You will have to know the total number of permutations, and then input start and end to get specific range of permutations.

For example,

Sort@permutationChunk[9, 3, 1, Binomial[9, 3]] == 
   Sort@Permutations[
     Flatten[{Array[1 &, #], Array[0 &, # (# - 1)]}, 1]] &@3
(*True*)
$\endgroup$
2
  • $\begingroup$ this is great - just what I was after! many thnaks :) $\endgroup$
    – martin
    Commented Mar 18, 2017 at 7:44
  • 1
    $\begingroup$ you're welcome. $\endgroup$
    – vapor
    Commented Mar 18, 2017 at 7:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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