magic_lobster_party , 1 month ago

By “certain distance function”, I mean a specific function that forces the problem to be O(n!^2).

But fear not! I have an idea of such function.

So the idea of such function is the hamming distance of a hash (like sha256). The hash is computed iterably by h[n] = hash(concat(h[n - 1], l[n])).

This ensures:

• We can save partial results of the hashing, so we don’t need to iterate through the entire lists for each permutation. Otherwise we would get another factor n in time complexity.
• The cost of computing the hamming distance is O(1).
• Order matters. We can’t cheat and come up with a way to exclude some permutations.

No idea of the practical use of such algorithm. Probably completely useless.