We stop the topic about "Generating a Random Permutation of the First one G Nature Numbers", because "Recursive Random Bit Flip Permutation" is a different topic or just because of convenience. I deeply worry about the completeness of the premutation created -- it may fall within particular pattern(s) of numbers. My shallow attempt of group theory was not continuous. At least this program struggles to provide a set or a none-repeating collection of numbers, so I would continue the analysis without requiring very high mathematics background.

How to start:

wget www.heteroclinic.net/attached/RecursiveRandomBitFlipPermuationGeneration.cpp g++ -o RecursiveRandomBitFlipPermuationGeneration.exe RecursiveRandomBitFlipPermuationGeneration.cpp ./RecursiveRandomBitFlipPermuationGeneration.exe

First we set size=5, generate a permutation:
In the source cpp file, int size = 5; printULLinBits (*p_start_pattern);// remove comment of this line recursiveRandomBitsFlipPermute(&start_pattern, size, 1, array,true ) ;// change false to true in main

The results are a little bit confusing, but the numbers looks like a random permutation of intergers in [0,31] $ ./RecursiveRandomBitFlipPermuationGeneration.exe 0000000000000000000000000000000000000000000000000000000000011000 24 28 0000000000000000000000000000000000000000000000000000000000011100 0000000000000000000000000000000000000000000000000000000000001000 8 12 0000000000000000000000000000000000000000000000000000000000001100 0000000000000000000000000000000000000000000000000000000000011001 25 29 0000000000000000000000000000000000000000000000000000000000011101 0000000000000000000000000000000000000000000000000000000000001001 9 13 0000000000000000000000000000000000000000000000000000000000001101 0000000000000000000000000000000000000000000000000000000000010000 16 20 0000000000000000000000000000000000000000000000000000000000010100 0000000000000000000000000000000000000000000000000000000000000000 0 4 0000000000000000000000000000000000000000000000000000000000000100 0000000000000000000000000000000000000000000000000000000000010001 17 21 0000000000000000000000000000000000000000000000000000000000010101 0000000000000000000000000000000000000000000000000000000000000001 1 5 0000000000000000000000000000000000000000000000000000000000000101 0000000000000000000000000000000000000000000000000000000000011010 26 30 0000000000000000000000000000000000000000000000000000000000011110 0000000000000000000000000000000000000000000000000000000000001010 10 14 0000000000000000000000000000000000000000000000000000000000001110 0000000000000000000000000000000000000000000000000000000000011011 27 31 0000000000000000000000000000000000000000000000000000000000011111 0000000000000000000000000000000000000000000000000000000000001011 11 15 0000000000000000000000000000000000000000000000000000000000001111 0000000000000000000000000000000000000000000000000000000000010010 18 22 0000000000000000000000000000000000000000000000000000000000010110 0000000000000000000000000000000000000000000000000000000000000010 2 6 0000000000000000000000000000000000000000000000000000000000000110 0000000000000000000000000000000000000000000000000000000000010011 19 23 0000000000000000000000000000000000000000000000000000000000010111 0000000000000000000000000000000000000000000000000000000000000011 3 7 0000000000000000000000000000000000000000000000000000000000000111 It took 0.015 seconds for size=5.

Let's only show the last five bits:
11000 11100 01000 01100 11001 11101 01001 01101 10000 10100 00000 00100 10001 10101 00001 00101 11010 11110 01010 01110 11011 11111 01011 01111 10010 10110 00010 00110 10011 10111 00011 00111
For bit No.1, there is a clear bipartite pattern of 1s and 0s (as programming convention, the least bit is No.0). For each bit, there is another bit showing a bipartite pattern and the size is halved. The permutation we generate will always be in such a pattern. Definitely, we have many other patterns missing. This is not a hole, it is something porous.

If you trouble yourself by studying the program RecursiveRandomBitFlipPermuationGeneration.cpp. You may find some of the terms I use here. For this program, we chose size=n, so we will have $2^n$ (Latex formula for 2 to the power of n) start_patterns. Given a fixed claw, the program can create $2^n$ different permutations of integers in [0,2^n). Obviously, not even requiring basic mathematical analysis like MATH30x or something, 2^n << (2^n)!. Since we use n bits, we can create n! claws. It is not rigorous to claim that function(start_pattern,claw) (it is returns a unique result, thus a function), will be the bi-jection map between a tuple(start_pattern,claw) and a permutation returned by the function. I also believe, it still holds that (2^n) * n! << (2^n)!, simple by observation, the pattern of permutation created misses a lot of other patterns. In the coming episode, we will try to fill the hole or, to say, to make the program less porous.

In fact, from the begginning, we are not far from a solution. "Recursive Random Bit Flip Permutation" clearly categorizes numbers in [0,2^n) into the tiered-bipartite hierarchy. For example, 2^40 numbers can be grouped into 1024*1024 groups. Each group's size would be 1024*1024. Using "Recursive Random Bit Flip Permutation", we can control which single group we want to compute. We assign the 1024*1024 groups each an index. Then we shuffle the indices, in previous programs, we have been able to shuffle 1G numbers. Suppose we have a cache size of 10*1024*1024 (10M unsigned long long is 80MB). Then each time we compute 10 groups of numbers and fill them in the cache. Shuffle the cache. Carry on till all groups are processed. For number in [0,2^n), there won't be numer(s) repeated, there won't be number(s) missed. We believe this cache-shuffle will seal the hole(s) of "Recursive Random Bit Flip Permutation".

You may argue, you can directly put 10^10 numbers to 100 groups. Shuffle the indices, shuffle the cache. Voila!

But "Recursive Random Bit Flip Permutation" definitely makes the numbers more statistically dispersed ( but easy to guess the over-all pattern). Plus indices shuffle and cache shuffle, it is fair enough against guessing.

In the coming episode, we will try to use program to prove this idea.

QtWagon is a computer graphics project to study 3D objects with the assistance of QT framework GUI. I publish the source code. Although the GUI for camera, lights and complex rigid body are not ready, the glMovingObject class can be used independently in a GL machine. You can use to it simulate a Qbit to verify Shor's algorithm.

qtwagonprototype.zip

Prerequisite: - Visual c++ or other c++ compiler - OpenGL properly installed e.g. freeglut you may need freeglut.dll to be at the same folder with the exe build. - QT framework 4.7 or above qmake -project add the following two lines in the .pro file generated: CONFIG += console debug QT += opengl nmake or make

File list:
window.h
window.cpp
to_string.h
to_string.cpp
READMEnInstall.txt
qtwagonprototype.pro
qtmovingobjectSingleton.h
qtmovingobjectSingleton.cpp
qtMovingObject.h
qtMovingObject.cpp
qtLightSingleton.h
qtLightSingleton.cpp
qtLight.h
qtLight.cpp
qtCameraSingleton.h
qtCameraSingleton.cpp
qtCamera.h
qtCamera.cpp
orientation.h
mathVector.h
mathPoint.h
mathMatrix.h
mathBasics.h
main.cpp
glwidgetSingleton.h
glwidgetSingleton.cpp
glwidget.h
glwidget.cpp
glOrientation.h
glMovingObject.h
glLight.h
glLight.cpp
enumops.h
drawablesSingleton.h
drawablesSingleton.cpp
camera.h
camera.cpp