KGS math club/solution 11 2: Difference between revisions
mNo edit summary |
added credit, C code |
||
| Line 2: | Line 2: | ||
Assign integers modulo n to the members of N, and cyclically order its members using them. Remove from N a member of K with a non-member of K that immediately follows it; and repeat until there are no members of K left. Append what we have left to K. | Assign integers modulo n to the members of N, and cyclically order its members using them. Remove from N a member of K with a non-member of K that immediately follows it; and repeat until there are no members of K left. Append what we have left to K. | ||
Solution by iceweasel. | |||
He also supplied this C code to compute it: | |||
main(int a, char **v) { | |||
int n=atoi(v[1]), | |||
ss=atoi(v[2]), | |||
x0=0, | |||
x1=0, | |||
m; | |||
for ( m=1<<n ; m>>=1 ; (m&ss?(x1|=m):x1?(x1&=(x1-1)):(x0|=m)) ); | |||
for ( m=1<<n ; m>>=1 ; m&x0&&x1&&(x1&=(x0^=m,x1-1)) ); | |||
printf("%d\n",ss^x0^x1); | |||
} | |||
Revision as of 10:44, 14 February 2011
Given n, k, and a k-member subset K of the n-member set N, we form the (n-k)-member subset it is paired with as follows.
Assign integers modulo n to the members of N, and cyclically order its members using them. Remove from N a member of K with a non-member of K that immediately follows it; and repeat until there are no members of K left. Append what we have left to K.
Solution by iceweasel.
He also supplied this C code to compute it:
main(int a, char **v) {
int n=atoi(v[1]), ss=atoi(v[2]), x0=0, x1=0, m;
for ( m=1<<n ; m>>=1 ; (m&ss?(x1|=m):x1?(x1&=(x1-1)):(x0|=m)) );
for ( m=1<<n ; m>>=1 ; m&x0&&x1&&(x1&=(x0^=m,x1-1)) );
printf("%d\n",ss^x0^x1);
}
