I've noticed that Signature can have an undocumented second argument. What does it do?
Signature[{1,2,3,4}, ?] $\begingroup$ $\endgroup$
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
7 It should be a comparison function. One can simulate the standard behavior by
Signature[{1, 2, 3}, If[#1 < #2, True, 0] &] Signature[{2, 1, 3}, If[#1 < #2, True, 0] &] Signature[{1, 1, 3}, If[#1 < #2, True, 0] &] (* 1 *) (* -1 *) (* 0 *) If the first argument is less than the second we return True (or False, it doesn't matter!), otherwise we can return everything except True and False.
Update:
Sometimes it returns 0 instead of 1 or -1. For example,
a = {52579, 13723}; Signature[a] (* -1 *) Signature[a, If[#1 < #2, True, 0] &] (* 0 *) I've found that Signature has 2 phases:
Check up for duplicates. If duplicates are found then return
0.If there is no duplicates then calculate the signature.
At the first phase Signature compares hashes instead of the direct values of elements (I think it is an optimization for non-numerical lists). Hashes of 52579 and 13723 are the same:
Hash[52579] Hash[13723] (* 8900173879719767389 *) (* 8900173879719767389 *) So I should return something instead of 0
If[#1 < #2, True, ?] & Any ideas?
P.S. V8 and earlier have another Hash function so the "magic" numbers are different. For example, {34064, 32232}.
- $\begingroup$ Very interesting. How did you discover this? (+1 of course.) $\endgroup$Mr.Wizard– Mr.Wizard2014-01-26 03:23:11 +00:00Commented Jan 26, 2014 at 3:23
- $\begingroup$ I'm finding cases where your code doesn't match the output of
Signature. I haven't isolated it yet but here's an example:SeedRandom[13]; a = RandomInteger[1*^10, 1*^5];nowSignature[a]gives-1whileSignature[a, If[#1 < #2, True, 0] &]gives0. Ideas? Signature[a, If[#1 < #2, True, 0] &] $\endgroup$Mr.Wizard– Mr.Wizard2014-01-26 03:36:23 +00:00Commented Jan 26, 2014 at 3:36 - $\begingroup$ @Mr.Wizard I've discovered this when I debug my code at codegolf.SE. I accidentally wrote
MapIndexed[Signature,A,{2}]instead ofMap[Signature,A,{2}]. It doesn't return any error, but it returns a wrong signature. Then I was surprised to find that theSignature[list, something]returns2 Boole[Mod[Length[list], 4] < 2] - 1iflisthas no duplicates and0otherwise! $\endgroup$ybeltukov– ybeltukov2014-01-26 03:44:11 +00:00Commented Jan 26, 2014 at 3:44 - $\begingroup$ Here is a shorter example where your code does not match the default:
a = {49914, 54968, 11840, 69457, 40872}-- can you confirm this problem on your system? $\endgroup$Mr.Wizard– Mr.Wizard2014-01-26 03:48:04 +00:00Commented Jan 26, 2014 at 3:48 - 2$\begingroup$ I really hope this gets an answer, has been bugging me for the better part of a year (when I made a similar typo mistake but still saw results). I
Sowedthe second argument and observed it appears to be pair lists, tried various ordering functions, etc. to no avail. I thought it might have something to do with counting inversions, left it at that. Are the MM staff that are here "allowed" to post such information? Surely a peek by one of them at the source could put this to bed. $\endgroup$ciao– ciao2014-02-03 04:01:14 +00:00Commented Feb 3, 2014 at 4:01