给定一本英语单词词典，请找出所有的变位词集。所谓的变位词是指，组成各个单词的字母完全相同，只是字母排列的顺序不同。
例如，“pots”,”stop”和“tops”互为变位词，因为每个单词都可以通过改变其他单词中字母的顺序来得到。
编程珠玑的变位词程序要按照三个步骤来执行，其中前一个步骤程序的输出作为下一个步骤程序的输入：
单词的字典的处理过程：
由以上可看出需要三个程序的处理。
假设输入单词的长度不超过100，对每个输入的单词依照字母进行排序，将结果输入这个单词所对应的“签名”。
程序排序后的输出的“签名”，对其输出的结果排序，如上图。
将同一个变位词类中的各个单词放到同一行中。
一个最多包含n个正整数的文件，每个数都小于n，其中n=107。如果在输入文件中有任何正数重复出现就是致命错误。没有其他数据与该正数相关联。
按升序排列的输入正数的列表。
最多有1MB的内存空间可用，有充足的磁盘存储空间可用。运行时间最多几分钟，运行时间为10秒就不需要进一步优化。
应用位图或位向量表示集合。可用一个32位长的字符串来表示一个简单的非负整数，例如，可以用如下字符串表示集合{1,2,4,5,8}。1
01101100100
32位字符串位表示：0 1 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
32位字符串位下标：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
数值的位都置为1，其他所有的位置为0。编程珠玑当中建议一个具有1000万个位的字符串来表示这个文件，那么这个文件的所占容量为10000000 bit= $10^7$bit，不到1MB的大小。
分三个阶段来编写程序。
int数组的存储位置：位置=数据/32(采用位运算即右移5位)int数组元素的位位置：位位置=数据%32(采用位运算即跟0X1F进行与操作)int数组如下所示，int大小：32位，从0开始。数组中每一个元素就是一个int，所以有长度是32位。
请将一个具有n个元素的一维向量向左旋转i个位置。例如，假设n=8,i=3，那么向量abcdefgh旋转之后得到向量defghabc。简单编码使用一个具有n个元素的中间向量分n步即可完成此作业。你可以仅使用几十字节的微小内存，花费与n成比例的时间来旋转该向量吗？
将向量x中的前i个元素复制到一个临时数组中，接着将余下的n-i个元素左移i个位置，然后再将前i个元素从临时数组中复制回x中的后面位置。
该方案使用i个额外的位置，如i足够大，过于浪费空间。
将这个问题看作是把数组ab转换成数组ba吧，但同时也假定我们具有在数组中转置指定部分元素的函数。我们先从ab开始，转置a得到$a^rb$，再转置b得到$a^rb^r$，然后再转置整个$a^rb^r$得到$(a^rb^r)^r$，实际上就是ba。
该转置代码在时间和空间上都很有效，并且是这么简短和简单，想出错都很难。
Update your browser to view this website correctly. Update my browser now