0
$\begingroup$

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?
Improve this question
$\endgroup$
4
  • $\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. ♦
    Commented Nov 8, 2019 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. ♦
    Commented Nov 8, 2019 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
    Commented Nov 8, 2019 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. ♦
    Commented Nov 8, 2019 at 21:39

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ but is it possible without sorting (because I would like to know if I can generalize it for higher dimensions) $\endgroup$
    – quester
    Commented Oct 10, 2019 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. ♦
    Commented Nov 8, 2019 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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