let's consider vectors in space dim=3 and values {0,1,2,...,99} on each dimension I would like to create hash function but with special trait: collisions only for permutations on input

$\forall_{x, y \in N^3} (y = permutation(x) <=> hash(x) == hash(y))$

is it even possible but without sorting? if so please attach example :)

  • one idea is to sort these values and then just create a key like $x_1*10e4 + x_2*10e2 + x_3$, for higher dimensions sorting would slow down solving a bit, so is it possible without sorting?
  • $\begingroup$ I don't think the question is well-defined. How will you evaluate whether a solution meets the "without sorting" requirement? If I define some complicated algorithm, how will you be able to tell whether it is sorting or not? (Maybe it is using an obfuscated version of something that is effectively sorting...) $\endgroup$
    – D.W.
    Nov 8 '19 at 19:09
  • $\begingroup$ And I wonder why you would exclude sorting, anyway? It does not seem like a well-motivated requirement. It's like asking, how would I pound in a nail without a hammer? Well, the obvious answer is: use a hammer and be done without it. Without knowing why you can't use a hammer, it's hard to answer. I wonder if you have some efficiency requirement in mind. If so, you should state that requirement, rather than requiring "without sorting". $\endgroup$
    – D.W.
    Nov 8 '19 at 19:10
  • $\begingroup$ problem is that if these computations would be made many times it would speed up computations where sorting would be "heaviest" step, take a look into this question and program in answer math.stackexchange.com/questions/3368225/…, there sorting would be quite a burden $\endgroup$
    – quester
    Nov 8 '19 at 20:44
  • $\begingroup$ I suggest you ask a new question, and this time specify the problem you're actually trying to solve, and specify the actual requirements (e.g., what your performance or running time requirements are). It sounds like you're actually trying to solve a problem with more than 3 dimensions or more than 100 values. But I suggest you first implement sorting and measure how efficient it is, and check whether it is efficient enough. If it's not, then you'll be able to tell us about what you found and how much faster you need the solution to be, to be useful to you. $\endgroup$
    – D.W.
    Nov 8 '19 at 21:39

With your limitations, you put all values into about 166,000 or so buckets, so yes, easily. If x, y, z are arbitrarily large, of course not.

  • $\begingroup$ but is it possible without sorting (because I would like to know if I can generalize it for higher dimensions) $\endgroup$
    – quester
    Oct 10 '19 at 16:41
  • $\begingroup$ @quester, that sounds like a different question. Changing the question after you have received an answer is a bit discouraged. Instead, it would be better to ask a new question about how to do this for higher dimensions. $\endgroup$
    – D.W.
    Nov 8 '19 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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