Setup: Consider integers say int8 (or int16, int32, int64).
Each integer is sequence of 8 binary digits e.g. 7 = 00000111.
There is simple natural action of the permutations of 8 letters on these digits.
The most simple example is cyclic shift - and cyclic shift is supported in most of the programming languages.
Question: Are there examples of other permutations which can be implemented via one or combination of instructions like multiplication by something, addition with something, xor with smth, or with smth , not, etc.. (i.e. those instructions which are supported in most programming languages and even in assembler level)?
To clarify: I am searching for one or combination of commands such that it will act as permutation on ALL binary sequence. I.e. when you apply it to ANY(!) int8 "x" - resulting sequence will be permutation of digits "x" - i.e. the number of "1" and "0" will be the same as in input "x".
Negative example Operation - multiply by say "3" (when overflow - take remainder) - acts as bijection on say int8, but NOT as permutation, because it does not preserve the number of "1" and "0", that means input "x" and output "3x" are not permutations of each other. (For example 3 * 1 = 3 = (00000111) - here are three "1", while input contained only one "1": (00000001).
Positive example Operation - cyclic shift. Input "x", output "shift-x" - is clearly permutation of digits binary digits.
Relaxed versions of the question: It would be interesting if there exists such examples which act as permutations on ONLY subset(s) of numbers containing say 4 - digits "1" (i.e. subsets - preserved by permutations). For examples there are 28 = C²₈ numbers with two digits equal to "1" - is there any instruction (instructions sequence) which acts on that subset of integers as permutation ?
Generalization of the question: combining 2-subsequent digits in one symbol int8 - will be a sequence of 4-symbols ABCD, where each symbol can be 00, 01, 10, 11. We can ask the same question on action realization of action of S₄ on such symbols. And so on.
Motivation: In research math sometimes we need to make computational experiments with permutations, but since n! grows fast we are limited. If there would be some quick way to works with at least S₈, S₁₆, S₃₂, S₆₄: int8, int16, int32, int64 - that might be helpful in some questions.
More context: https://www.kaggle.com/competitions/santa-2023/discussion/473074
At the very least you can express any permutation
(i8, i7, i6, i5, i4, i3, i2, i1)
by writing:
y = ((x & 1) << i1) | ((x & 2) << (i2-1))
| ((x & 4) << (i3-2))| ((x & 8) << (i4-3))
| ((x & 16) << (i5-4)) | ((x & 32) << (i6-5))
| ((x & 64) << (i7-6))| ((x & 128) << (i8-7));
The (x & poweroftwo) part selects a bit of x, and the << (i - j) part moves it from its old position j to its new position i.
The bitwise or | operators combine all the individual bits. In fact a simple + would do the same thing as | in this case.
I'm abusing notation a little bit: in the formula above, I wrote only left-shifts, but some of the numbers can be negative. In C that would be undefined behaviour, so you have to replace << (i5-4) with >> (4-i5), etc., where necessary.
If a particular permutation has a bit more "logic" to it then you can probably describe this permutation more succinctly than by moving each bit separately.
For instance if the permutation is the union of two disjoint cycles, then you can perform two cyclic shifts and recombine them and this will be shorter to write (and execute) than combining 8 bit shifts.
In fact, all permutations can be decomposed as a union of disjoint cycles, and in most cases this should lead to a slightly more expressive formula than the one above.
However there are 8! = 40320 possible permutations of 8 elements, and the average number of cycles in a random permutation of 8 elements is about 3. And when the cycles consist in adjacent bits, that's super helpful, but when the cycles are intermingled with one cycle of bits 1,2,7 and one cycle of bits 3,5,8 and one cycle of bits 4,6, it's still going to be hard to describe succinctly.
So for most permutations you shouldn't expect the formula to be too compact.
Note that "most" in the previous sentence kinda assumes that you are dealing with a random permutation, selected among all possible permutations. In practical applications it's possible that you deal with "simple/logical" permutations more often than with "complex" permutations, even though the total number of "complex" permutations is higher.
You might be interested in reading about Kolmogorov complexity, a concept invented precisely to describe "how logical / easy to describe" is a mathematical object.