相关疑难解决方法(0)

我们给了一个字符串和字符串的排列.

例如,输入字符串sandeep和排列psdenae.

在原始字符串的排列的排序列表中查找给定排列的位置.

我有一个大小为4,9,16或25的数组(根据输入)并且数组中的数字相同但少一个(如果数组大小为9则数组中的最大元素将是8)数字从0开始, 我想做一些算法来为数组生成某种校验和,这样我就可以比较2个数组是否相等,而不是遍历整个数组并逐个检查每个元素.

我在哪里可以获得这类信息？我需要一些尽可能简单的东西.谢谢.

编辑:只是为了清楚我想要的东西:

- 数组中的所有数字都是不同的,因此[0,1,1,2]无效,因为存在重复的元素(1)

- 数字的位置很重要,所以[0,1,2,3]与[3,2,1,0]不一样

- 数组将包含数字0,因此这也应该被考虑在内.

编辑:

好吧,我试着在这里实现Fletcher的算法:http: //en.wikipedia.org/wiki/Fletcher%27s_checksum#Straightforward

int fletcher(int array[], int size){
  int i;
  int sum1=0;
  int sum2=0;
  for(i=0;i<size;i++){
    sum1=(sum1+array[i])%255;
    sum2=(sum2+sum1)%255;
  }
  return (sum2 << 8) | sum1;
}

说实话,我不知道返回线做了什么但不幸的是,算法不起作用.对于数组[2,1,3,0]和[1,3,2,0],我得到相同的校验和.

EDIT2:

好的,这是另一个,Adler校验和 http://en.wikipedia.org/wiki/Adler-32#Example_implementation

#define MOD 65521;

unsigned long adler(int array[], int size){
  int i;
  unsigned long a=1;
  unsigned long b=0;
  for(i=0;i<size;i++){
    a=(a+array[i])%MOD;
    b=(b+a)%MOD;
  }
  return (b <<16) | a;
}

这也行不通.数组[2,0,3,1]和[1,3,0,2]生成相同的校验和.我在这里失去了希望,任何想法？

我正在0, 1, ..., (N - 1)按顺序逐个阅读这些数字.我的目标是只使用O(1)空格来找到这个给定排列的词典编纂索引.

之前曾问过这个问题,但我能找到的所有算法都使用了O(N)空间.我开始认为这是不可能的.但是,通过减少分配数量,这对我帮助很大.