This smells like a dimension/support reduction problem where permutations lead to a minimal support vector/basis.
Turns out I actually need to solve a harder problem: Find the permutation so that the arithmetic difference between smallest and largest integer after permutation is minimal.https://twitter.com/oe1cxw/status/1119226244992774144 …
-
-
-
What is your linear algebra doing in my combinatorics problem? :) Can you elaborate?
- Show replies
New conversation -
-
-
Same permutation for all ints? And smallest maximum int after permutation?
-
Yes, or now smallest delta between max and min, and actually now there's also a XOR mask. And I think I've solved it already. (Or at least I have a heuristic that's good enough for my purpose.)
End of conversation
New conversation -
-
-
If it's only 32 bit, is it too slow to just do the O(32*n) algorithm?
-
If you mean a brute force search ... wouldn't there be 32! (factorial) permutations? What I ended up doing has approx O(N^2*M) complexity for N bits and M values, and tries to find a permutation and a XOR mask to minimize both the max value and the delta between min and max.
- Show replies
New conversation -
-
-
Ah dang, I was still having fun with the previous problem, which produces results like this. Still a few edge cases... but probably not the smallest *difference*. How did you end up doing it? Linked commit is too big for my 11pm brain. Good night :)pic.twitter.com/p1CfsCKi6s
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.