Joseph Wetherell on Sun, 26 Jun 2016 22:47:50 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Need permutation help for n!/(n-r)!


Is it OK if the numbering is off by one?  The numbering used in permtonum takes the identity permuation to 0, and I would be inclined to follow that convention.  Note permtonum actually returns a number between 0 and n!-1, even though the documentation says it returns a number between 1 and n!.  I've decided to also follow the convention in the permtonum implementation.

With those choices, the following two functions will convert between integers and permutations of subsets of r out of n:

\\ numtopermsubset(n,r,k): permutation number k (mod n!/(n-r)!) of subsets of r out of n letters.
numtopermsubset(n,r,k) = vecextract(numtoperm(n,k*((n-r)!)),vector(r,i,i))

\\ permsubsettonum(n,x): ordinal (between 0 and n!/(n-r)!-1) of subset permutation x
\\     where x is a subset of length(x) out of n letters.
permsubsettonum(n,x) = permtonum(concat(x,setminus(vector(n,i,i),Set(x))))\(n-length(x))!

Here is a test:

{
  for(k=0,23,
    x = numtopermsubset(4,3,k);
    printf("%2d -> %o -> %2d\n", k, x, permsubsettonum(4,x));
  );
}

 0 -> [1,2,3] ->  0
 1 -> [1,2,4] ->  1
 2 -> [1,3,2] ->  2
 3 -> [1,3,4] ->  3
 4 -> [1,4,2] ->  4
 5 -> [1,4,3] ->  5
 6 -> [2,1,3] ->  6
 7 -> [2,1,4] ->  7
 8 -> [2,3,1] ->  8
 9 -> [2,3,4] ->  9
10 -> [2,4,1] -> 10
11 -> [2,4,3] -> 11
12 -> [3,1,2] -> 12
13 -> [3,1,4] -> 13
14 -> [3,2,1] -> 14
15 -> [3,2,4] -> 15
16 -> [3,4,1] -> 16
17 -> [3,4,2] -> 17
18 -> [4,1,2] -> 18
19 -> [4,1,3] -> 19
20 -> [4,2,1] -> 20
21 -> [4,2,3] -> 21
22 -> [4,3,1] -> 22
23 -> [4,3,2] -> 23


Cheers,
Joe



On Sat, Jun 25, 2016 at 11:19 PM, chandra sekaran <sekar.bc@gmail.com> wrote:
>
>
> Hi Joe,
>
> It is working. Thanks.
>
> I want to find out index to number and number to index
>
> with out loop. For small number we can loop through and compare to get the number.
>
> If n and r big number(n=600,r=25) it will take long time to find.
>
> (11:39) gp > 600!/(600-25)!
> %59 = 1712444741995872743767068314898968290507882039321992936466415616000000
>
> Is there any efficient algorithm for solving above problem or not.
>
> Thanks,
>
> Chandrasekarn B
>
>
> ---------------------------------------------------
>
> For example if i give the vector [1,4,2] i want to get index number
>
> 5 and given the number 5 i want to get the pattern [1,4,2] with out
>
> loop.
>
>
> n(11:27) gp > n=4
> %52 = 4
> (11:28) gp > r=3
> %53 = 3
> (11:28) gp > forvec(v=vector(r,i,[1,n]), if(length(Set(v))==r, print(v)))
>
> Result
>
> 1   [1, 2, 3]
> 2   [1, 2, 4]
> 3   [1, 3, 2]
> 4   [1, 3, 4]
> 5   [1, 4, 2]
> 6   [1, 4, 3]
> 7   [2, 1, 3]
> 8   [2, 1, 4]
> 9   [2, 3, 1]
> 10  [2, 3, 4]
> 11  [2, 4, 1]
> 12  [2, 4, 3]
> 13  [3, 1, 2]
> 14  [3, 1, 4]
> 15  [3, 2, 1]
> 16  [3, 2, 4]
> 17  [3, 4, 1]
> 18  [3, 4, 2]
> 19  [4, 1, 2]
> 20  [4, 1, 3]
> 21  [4, 2, 1]
> 22  [4, 2, 3]
> 23  [4, 3, 1]
> 24  [4, 3, 2]
> -------------------------------------
>
>