w****o
发帖数: 2260 | 1 数组大小为N, 要shift by k positions
有关的讨论在：
http://www.mitbbs.com/article_t/JobHunting/32080185.html
这个juggling algorithm,其实就是把数组分成了gcd(N, k)个set,在每个set里的数可
以通过k跳，互相到达，所以他们之间就可以交换。
我的问题是，如何从数学上证明这gcd(N, k)个set之间是没有任何的交集？同时这gcd(
N, k)个set的并集正好就是整个数组？
是不是要从 k modulus N方面来着手？
谢谢！ | w****o
发帖数: 2260 | 2 这个链接解释了。
http://eli.thegreenplace.net/2008/08/29/space-efficient-list-ro
gcd(
【在 w****o 的大作中提到】
: 数组大小为N, 要shift by k positions
: 有关的讨论在：
: http://www.mitbbs.com/article_t/JobHunting/32080185.html
: 这个juggling algorithm,其实就是把数组分成了gcd(N, k)个set,在每个set里的数可
: 以通过k跳，互相到达，所以他们之间就可以交换。
: 我的问题是，如何从数学上证明这gcd(N, k)个set之间是没有任何的交集？同时这gcd(
: N, k)个set的并集正好就是整个数组？
: 是不是要从 k modulus N方面来着手？
: 谢谢！
|
|
