Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I've noticed that Signature can have an undocumented second argument. What does it do?

Signature[{1,2,3,4}, ?]
share|improve this question
add comment

1 Answer 1

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:

  1. Check up for duplicates. If duplicates are found then return 0.

  2. 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}.

share|improve this answer
    
Very interesting. How did you discover this? (+1 of course.) –  Mr.Wizard Jan 26 at 3:23
    
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]; now Signature[a] gives -1 while Signature[a, If[#1 < #2, True, 0] &] gives 0. Ideas? Signature[a, If[#1 < #2, True, 0] &] –  Mr.Wizard Jan 26 at 3:36
    
@Mr.Wizard I've discovered this when I debug my code at codegolf.SE. I accidentally wrote MapIndexed[Signature,A,{2}] instead of Map[Signature,A,{2}]. It doesn't return any error, but it returns a wrong signature. Then I was surprised to find that the Signature[list, something] returns 2 Boole[Mod[Length[list], 4] < 2] - 1 if list has no duplicates and 0 otherwise! –  ybeltukov Jan 26 at 3:44
    
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? –  Mr.Wizard Jan 26 at 3:48
2  
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 Sowed the 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. –  rasher Feb 3 at 4:01
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.