Relation between permutations and fourier transform?

534 Views Asked by At

i dont know if this is already addressed somewhere (searching around did not find sth).

The motivation is to find a way to generate or produce permutations using concepts from continuous mathematics (instead of discrete).

How can one generate permutations of the $n$ items using for example rotations?

This reminds how clocks work. A clock has a number of gearwheels inter-connected with various (multiples of same number) sizes (or radii).

enter image description here

A small gearwheel will rotate by a step (the basic step or frequency).

Once the smaller gearwheel fulfils a full rotation (by a sequence of steps), the immediately larger gearwheel turns by one step and the process starts again from the smaller wheels, and so on until the largest wheel has completed a full rotation (and all? premutations are produced).

One can easily see that this mechanism in fact generates permutations of $n$ items (with no duplicates?)

This is related to how permutations are factored into cycles and also how the Fisher-Yates-Knuth Shuffle algorithm works.

This can be modeled by complex numbers $e^{ik2\pi/n}$ (or equivalently as modulo arithmetic), $n$ is number of items and $k$ represents the $k$'th element (or maybe $k$'th element's gearwheel size).

This is reminiscent of Fourier transform.

Is the (discrete) Fourier transform related to generation of permutations? If so how?

Extra note What would be a randomized version of the previous process?

PS. As an aside this example provides an intuitive understanding of the $+ k2\pi$ periodicity. Like this: at a specific time a small wheel may have made several full rotations (while a larger wheel not a full rotation), in this sense, although the smaller wheel would be in a same position the $+ k2\pi$ periodicity could carry information about the larger(s) wheel(s) current rotation (extracted by appropriate factoring).