एक पूर्णांक सरणी के लिए चेकसम?

Question

मेरे पास एक सरणी है जो आकार 4, 9, 16 या 25 (इनपुट के अनुसार) है और सरणी में संख्याएं समान हैं लेकिन एक से कम (यदि सरणी का आकार 9 है तो सरणी में सबसे बड़ा तत्व है 8) संख्या से शुरू होती है और मैं सरणी के लिए किसी प्रकार का चेकसम उत्पन्न करने के लिए कुछ एल्गोरिदम करना चाहता हूं ताकि मैं तुलना कर सकूं कि 2 सरणी पूरी सरणी के माध्यम से लूपिंग के बिना बराबर हैं और प्रत्येक तत्व की जांच कर रहे हैं एक एक करके।

मुझे इस तरह की जानकारी कहां मिल सकती है? मुझे ऐसा कुछ चाहिए जो जितना संभव हो सके उतना आसान हो। धन्यवाद।

संपादित करें: बस पर स्पष्ट जो मैं चाहता होने के लिए:

सरणी में संख्या -सभी अलग हैं, इसलिए [0,1,1,2] मान्य नहीं है एक दोहराया तत्व है, क्योंकि (1)

संख्या इस मामले की -इस स्थिति है, तो [0,1,2,3] इसे [3,2,1,0]

-इस सरणी संख्या 0 में शामिल होंगे ही नहीं है, इसलिए इसे भी ध्यान में रखा जाना चाहिए।

संपादित करें:

ठीक है मैं यहाँ फ्लेचर के एल्गोरिथ्म को लागू करने की कोशिश की: 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:

यहाँ ठीक एक और एक, एडलर चेकसम 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; 
} 

यह भी काम नहीं करता है। Arrays [2,0,3,1] और [1,3,0,2] समान चेकसम उत्पन्न करते हैं। मैं आशा खो रहा हूं, कोई विचार?

Answer 1

के के मामले लेते हैं अपने 25 पूर्णांक की सरणी। आप समझाते हैं कि इसमें अद्वितीय पूर्णांक 0 से 24 के किसी भी क्रमपरिवर्तन शामिल हो सकते हैं। this page के अनुसार, 25 है! (25 फैक्टोरियल) संभावित क्रमपरिवर्तन, जो 15511210043330985984000000 है। 32 बिट पूर्णांक से कहीं अधिक हो सकता है।

निष्कर्ष यह है कि आप टकराव करेंगे, इससे कोई फर्क नहीं पड़ता कि आप कितनी मेहनत करते हैं।

अब, यहाँ एक सरल एल्गोरिथ्म उस स्थिति के लिए खाते में है:

int checksum(int[] array, int size) { 
    int c = 0; 
    for(int i = 0; i < size; i++) { 
    c += array[i]; 
    c = c << 3 | c >> (32 - 3); // rotate a little 
    c ^= 0xFFFFFFFF; // invert just for fun 
    } 
    return c; 
} 

Answer 2

1 से एन के एन अद्वितीय पूर्णांक की एक सरणी के लिए, तत्वों को जोड़ना हमेशा एन * (एन + 1)/2 होगा। इसलिए आदेश में एकमात्र अंतर है। यदि "चेकसम" से आप संकेत देते हैं कि आप कुछ टकराव सहन करते हैं, तो एक ही तरीका लगातार संख्याओं के बीच मतभेदों को जोड़ना है। तो उदाहरण के लिए, {1,2,3,4} के लिए डेल्टा चेकसम 1 + 1 + 1 = 3 है, लेकिन {4,3,2,1} के लिए डेल्टा चेकसम -1 + -1 + -1 = -3।

कोई आवश्यकताओं टक्कर दरों या कम्प्यूटेशनल जटिलता के लिए दिए गए थे, लेकिन अगर इसके बाद के संस्करण के अनुरूप नहीं है, तो मेरा सुझाव है एक position dependent checksum

Answer 3

मुझे लगता है कि क्या आप चाहते हैं निम्नलिखित धागे के जवाब में है:

Fast permutation -> number -> permutation mapping algorithms

आप केवल अपने क्रमपरिवर्तन की संख्या लेते हैं और इसे आपके चेकसम के रूप में लेते हैं। चूंकि प्रति क्रमशः बिल्कुल एक चेकसम है, वहां एक छोटा चेकसम नहीं हो सकता है जो टकराव मुक्त है।

Answer 4

जो मैं समझता हूं उससे आपकी सरणी में 0 से N-1 की संख्याओं का क्रमपरिवर्तन होता है। एक चेक-योग जो उपयोगी होगा, उसके लेक्सिकोग्राफिक ऑर्डरिंग में सरणी का रैंक है। इसका क्या मतलब है ?यह देखते हुए 0, 1, 2 आप संभव क्रमपरिवर्तन

1: 0, 1, 2 
    2: 0, 2, 1 
    3: 1, 0, 2 
    4: 1, 2, 0 
    5: 2, 0, 1 
    6: 2, 1, 0 

चेक-राशि पहले नंबर होगा है, और गणना की है जब आप सरणी पैदा करते हैं। वहाँ

Find the index of a given permutation in the list of permutations in lexicographic order

जो सहायक हो सकता है में प्रस्तावित समाधान, रहे हैं, हालांकि ऐसा लगता है सबसे अच्छा एल्गोरिथ्म द्विघात जटिलता की थी। इसे रैखिक जटिलता में सुधारने के लिए आपको हाथ से पहले फैक्ट्रोरियल के मूल्यों को कैश करना चाहिए।

लाभ? शून्य टकराव।

संपादित करें: संगणना मूल्य एक बहुपद जहां भाज्य एकपद के बजाय सत्ता के लिए प्रयोग किया जाता है के मूल्यांकन की तरह है। तो समारोह

f(x0,....,xn-1) = X0 * (0!) + X1 * (1!) + X2 * (2!) +...+ Xn-1 * (n-1!) 

विचार क्रमपरिवर्तन की एक उप-श्रेणी प्राप्त करने के लिए प्रत्येक मूल्यों का उपयोग करने के लिए है, और काफी मूल्यों के साथ आप एक अद्वितीय क्रमचय इंगित है।

कार्यान्वयन (एक बहुपद में से एक की तरह) के लिए अब

:

1. पूर्व गणना 0 .... n-1 के लिए! कार्यक्रम
2. हर बार जब आप अपने चेकसम गणना करने के लिए
3. आप हे में तुलना (1) इस चेकसम का उपयोग कर एक सरणी आप च (तत्व) का उपयोग सेट की शुरुआत में

Answer 5

कैसे भारित योग की जांच योग के बारे में? आइए [0,1,2,3] के लिए एक उदाहरण लें। सबसे पहले एक बीज और सीमा लेने, के रूप में 10000007.

a[4] = {0, 1, 2, 3} 
limit = 10000007, seed = 7 
result = 0 
result = ((result + a[0]) * seed) % limit = ((0 + 0) * 7)) % 10000007 = 0 
result = ((result + a[1]) * seed) % limit = ((0 + 1) * 7)) % 10000007 = 7 
result = ((result + a[2]) * seed) % limit = ((7 + 2) * 7)) % 10000007 = 63 
result = ((result + a[3]) * seed) % limit = ((63 + 3) * 7)) % 10000007 = 462 

कि के लिए

आपका चेकसम है 462 7 के रूप में एक बीज और सीमा चुनने देती हैं [0, 1, 2, 3]। संदर्भ http://www.codeabbey.com/index/wiki/checksum