I published this question on mathoverflow two years ago, but I did not get an answer:

Leave $ w = a_0 cdot a_1 cdots a_ {n-1} $ be a word of $ {0,1 } ^ n $, $ | w | = n $

Leave $ m = sum_ {i = 0} ^ {n-1} {a_i cdot 2 ^ {n-1-i}} $ be the corresponding binary number built

of the word.

Leave $ k = left lfloor frac {n!} {2 ^ n} right rfloor cdot (m + 1) $ , so $ 1 le k le n! $.

Calculate the permutation of Lehmer $ pi_k $ since $ k $ in $ n $ numbers.

(

https://en.wikipedia.org/wiki/Lehmer_code

)

Set $ x: = pi_k cdot w = a _ { pi_k (0)} cdot a _ { pi_k (1)} cdots a _ { pi_k (n-1)} $

So $ f (w): = x $.

So the function permutes the digits in the word $ w $ and the permutation is determined by $ w $.

Suppose you randomly choose a word from $ {0,1 } ^ {1000} $ and then the function is applied. Is it practically possible to reverse the word constructed?

I mean, does anyone have an idea about how to reverse the word?

More details can be found at:

http://orgesleka.blogspot.de/2015/09/candidate-one-way-function.html

This image shows all the words of length 7 when f is applied to those words: