Changes between Version 1 and Version 20 of Ticket #10950


Ignore:
Timestamp:
10/24/17 15:34:40 (2 years ago)
Author:
jdemeyer
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #10950

    • Property Authors changed from to Jeroen Demeyer
    • Property Summary changed from The Hash function for matrices suffers from many collisions with permutation matrices to The hash function for matrices suffers from many collisions with permutation matrices
    • Property Owner changed from jason, was to nthiery
    • Property Dependencies changed from to #24090
    • Property Branch changed from to u/jdemeyer/the_hash_function_for_matrices_suffers_from_many_collisions_with_permutation_matrices
    • Property Milestone changed from to sage-8.1
    • Property Keywords permutation matrices hash added
    • Property Commit changed from to f67a8839d7dfb843a8ed8652a2734b644be579f1
  • Ticket #10950 – Description

    v1 v20  
    77}}}
    88
    9 In general, we would hope to get n! below:
    10 
     9After applying this branch:
    1110{{{
    12     sage: len(set([ hash(mat(p)) for p in Permutations(1) ]))
    13     1
    14     sage: len(set([ hash(mat(p)) for p in Permutations(2) ]))
    15     1
    16     sage: len(set([ hash(mat(p)) for p in Permutations(3) ]))
    17     5
    18     sage: len(set([ hash(mat(p)) for p in Permutations(4) ]))
    19     1
    20     sage: len(set([ hash(mat(p)) for p in Permutations(5) ]))
    21     16
    22     sage: len(set([ hash(mat(p)) for p in Permutations(6) ]))
    23     16
    24     sage: len(set([ hash(mat(p)) for p in Permutations(7) ]))
    25     32
    26     sage: len(set([ hash(mat(p)) for p in Permutations(8) ]))
    27     1
     11sage: def hashmat(p): m = p.to_matrix(); m.set_immutable(); return hash(m)
     12sage: len(set(hashmat(p) for p in Permutations(1)))
     131
     14sage: len(set(hashmat(p) for p in Permutations(2)))
     152
     16sage: len(set(hashmat(p) for p in Permutations(3)))
     176
     18sage: len(set(hashmat(p) for p in Permutations(4)))
     1924
     20sage: len(set(hashmat(p) for p in Permutations(5)))
     21120
     22sage: len(set(hashmat(p) for p in Permutations(6)))
     23720
     24sage: len(set(hashmat(p) for p in Permutations(7)))
     255040
     26sage: len(set(hashmat(p) for p in Permutations(8)))
     2740320
    2828}}}
    2929