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]
> -------------------------------------
>
>