Discussion:
Product and sum of integer array as test for repeats
Bruce Varley
2011-05-21 13:17:16 UTC
This is an outcome of an industrial problem that's been solved with some
brute force computer work, this posting is just a result of my curiosity.

We had the task of checking an array of integers for duplicates, due to the
hardware involved the traditional approaches weren't suitable. One of our
people came up with an algo that works for the cases that we encounter in
the field, I'm wondering whether the result holds for all n.

There is an array of n integers between 1 and n, with no repeated members,
in any order. Let P be the product of all the entries, and S be the sum.

The postulate is that no other set of n integers, all between 1 and n
(obviously containing repeats) will have the same values for both P and S.
k***@kymhorsell.com
2011-05-21 14:24:48 UTC
Post by Bruce Varley
This is an outcome of an industrial problem that's been solved with some
brute force computer work, this posting is just a result of my curiosity.
We had the task of checking an array of integers for duplicates, due to the
hardware involved the traditional approaches weren't suitable. One of our
people came up with an algo that works for the cases that we encounter in
the field, I'm wondering whether the result holds for all n.
There is an array of n integers between 1 and n, with no repeated members,
in any order. Let P be the product of all the entries, and S be the sum.
The postulate is that no other set of n integers, all between 1 and n
(obviously containing repeats) will have the same values for both P and S.
1 54 55 sum 110 product 2970

5 6 99

---
You whackos [i.e. "scientists"] just keep changing your "predictions" to suit reality!
-- ***@27-32-240-172 [86 nyms and counting], 16 Feb 2011 15:57 +1100
Bruce Varley
2011-05-22 10:25:27 UTC
Post by Bruce Varley
This is an outcome of an industrial problem that's been solved with some
brute force computer work, this posting is just a result of my curiosity.
We had the task of checking an array of integers for duplicates, due to the
hardware involved the traditional approaches weren't suitable. One of our
people came up with an algo that works for the cases that we encounter in
the field, I'm wondering whether the result holds for all n.
There is an array of n integers between 1 and n, with no repeated members,
in any order. Let P be the product of all the entries, and S be the sum.
The postulate is that no other set of n integers, all between 1 and n
(obviously containing repeats) will have the same values for both P and S.
1 54 55 sum 110 product 2970
5 6 99
---
You whackos [i.e. "scientists"] just keep changing your "predictions" to suit reality!
Yep, the conjecture breaks for n=9 also.
k***@kymhorsell.com
2011-05-22 10:40:54 UTC
Bruce Varley <***@nospam.com> wrote:
[...]

What you may be looking for is a "perfect hashing" scheme.
While Don Knuth wrote in his book such schemes might be very dificult
to find, quite a few are now known.

There is also a UNIX/Linux/GNU tool called "gperf" that creates perfect
hash tables for strings (normally used for reserved word or keyword lookup)
that might either do what you want or be adapted.
--
"Denialism"? Is that a word?
-- Mickey Langan, Sun 2 Jan 2011 4:50 pm
Bruce Varley
2011-05-22 13:03:18 UTC
Post by k***@kymhorsell.com
[...]
What you may be looking for is a "perfect hashing" scheme.
While Don Knuth wrote in his book such schemes might be very dificult
to find, quite a few are now known.
There is also a UNIX/Linux/GNU tool called "gperf" that creates perfect
hash tables for strings (normally used for reserved word or keyword lookup)
that might either do what you want or be adapted.
--
"Denialism"? Is that a word?
-- Mickey Langan, Sun 2 Jan 2011 4:50 pm
Thanks, I'll follow that up. This function has to run on a specialised
industrial platform with minimal capabilities (yes, amazingly they do still
exist), classical algos such as hashing are likely to be OTT. I have a
couple of workarounds up my sleeve. Cheers
k***@kymhorsell.com
2011-05-22 13:33:27 UTC
Bruce Varley <***@nospam.com> wrote:
...
Post by Bruce Varley
Thanks, I'll follow that up. This function has to run on a specialised
industrial platform with minimal capabilities (yes, amazingly they do still
exist), classical algos such as hashing are likely to be OTT. I have a
couple of workarounds up my sleeve. Cheers
Generalisations of Pearson hashing only require XOR and indexing
into a table.

---
Why have you posted binaries to a text-only newsgroup, fuck wit?
Would you like to see how it appears in a compliant newsreader, which
all of the usenet with IQs beyond single digits use? It appears as
above in the quoted text - NO IMAGES AT ALL! ROTFL
[Seems like "fuckwit" has never seen HTML before].
-- Gillard Lies <***@gmail.com>, 18 Feb 2011 22:57 -0800 (PST)