How to convert a set of sequential integers into a set of unique random numbers? I have a set of sequential and non-duplicate integers which I would like to convert into a set of non-duplicate random integers. 

What I want to achieve is this  - I have a list of sequential numbers like below

[1, 2, 3, 4, 5, 6, 7, 8, 9]


This list is going to be quite big in reality e.g. 100 million

I want to shuffle this list multiple times in order to rearrange the numbers in the list. Each shuffle should give me a new sequence in such a way that, if I pick a number at a particular position in the list after each shuffle, I should never get a duplicate. 

For example, if the above list is shuffled three times, I get the following three sequences after each shuffle

shuffle 1 --&gt; [9, 3, 4, 1, 7, 2, 6, 5, 8]
shuffle 2 --&gt; [8, 2, 7, 5, 4, 6, 3, 9, 1]
shuffle 3 --&gt; [1, 9, 6, 7, 5, 3, 4, 8, 2]


In the above lists, if you pick a number at any position, say 2,  from all the sets, you never get any duplicates. You will get a duplicate if you pick position 2 from the first sequence and position 5 from the third set and this is fine. 

For some reason, I feel that there should be a cryptographic function for this kind of shuffling to which I can pass my input sequence and I get a shuffled sequence back as described above. Is there any? I have looked at LFSR but just not sure if that solution works in this case.
Let $P$ be an arbitrary random fixed permutation of $n$ elements. Each of the desired shuffle can be generated from the previous as follows:


apply $P$ to the previous shuffle (or the initial set/vector, the first time);
rotate the result one to the left;
apply $P^{-1}$ to the result.


This will have the property asked by "if I pick a number at a particular position in the list after each shuffle, I should never get a duplicate". Proof: in applying the shuffle sequentially, the next application of $P$ with cancel the previous application of $P^{-1}$. It follows that the rotation will operate on the result of the previous rotation, thus that the property is met at the output of the rotation. It follows that the property is met after applying $P^{-1}$, thus at the output.

We can iterate this $n-1$ times (if we do it once more, we are back to the original, thus will get something clearly sequential, thus in the context distinguishable from the required "random integers" with great ease and near certainty).

We can use the Fisher-Yates shuffle to generate $P$. Or, if keeping it in memory is an issue because of size, we can use a cipher to implement $P$, and its reverse; that's a standard trick of Format Preserving Encryption.

Any isolated shuffle is indistinguishable from a random shuffle, but even the first two shuffles generated are distinguishable from random shuffles with the required property (which perhaps is undesirable, if not clearly prohibited).



If we remove the requirement that the same operation is iterated to go from one shuffle to the next (we are told that we can), we can do something better: pick three arbitrary random permutations $P$, $Q$, $R$ of $n$ elements, and get the $(j+1)^\text{th}$ shuffle as


apply $P$ to the initial state
rotate the result $Q(j)$ times to the left, where $Q(j)$ is the $(j+1)^\text{th}$ element of the vector obtained by applying $Q$ to the vector of the first $n$ non-negative integers; or, otherwise said, $Q(j)$ is an integer $q_j$ with $0\le q_j&lt;n$, such that $0\le i&lt;j&lt;n\implies q_i\ne q_j$.
apply $R$ to the result.


This time, we can obtain $n$ individually random-looking shuffles, which obviously is the maximum. Again, Fisher-Yates or FPE can be used to implement $P$, $Q$ and $R$. Even knowing the initial shuffle and the rank of any two generated shuffles, I vaguely conjecture (without proof) that they are indistinguishable from two random shuffles meeting the property asked. By a counting argument, three generated shuffles are distinguishable, at least by an unbounded adversary; thus we are far from generating the best randomness possible.

I have asked the question in more academic terms there.



Here is sample code in Java for the second method. Class MyCipher implements a Pseudo Random Permutation of size elements, made using cycling (arguably the simplest efficient FPE technique), and a basic iterated block cipher. Class MyShuffledArray is then a straightforward implementation of the technique that I propose. The code is usable for large parameters, and uses constant memory.

import java.util.Random;
import java.security.SecureRandom;

public class MyShuffledArrayDemo {

    // MyCipher implement a PRP of size elements
    static class MyCipher {
        private static final int R = 40;        // number of rounds
        private final int size;                 // size of PRP
        private final int mask;                 // bit mask for block
        // 0 &lt; size &lt;= mask+1  and mask+1 is a power of 2
        private final int rish;                 // right shift count
        private final int[] rk = new int[R];    // rk for each round

        // Constructor from rng source
        private MyCipher(int size, Random rng) {
            assert size&gt;0 : "MyCipher.size must be positive";
            int i,j;
            // find block cipher width j in bits; and mask 
            for (j = 3, i = 8; j&lt;31 &amp;&amp; i&lt;size; ++j)
                i += i;
            this.size = size;
            this.mask = i-1;    // one less than a power of two
            this.rish = j*3/7;  // shift count, at least 1
            i = R; do
                rk[--i] = rng.nextInt();
            while (i!=0);
        }

        // Implement PRP, using a basic iterated block cipher and cycling.
        // Input and output are a non-negative integer less than size.
        private int Perm(int x) {
            assert x&gt;=0 &amp;&amp; x&lt;this.size : "bad input to MyCipher.encrypt";
            do { // cycling loop; executed on average less than twice when size&gt;4
                int r = R;
                do {// Round loop; each losslessly transforms x by
                    // - multiplying by 0xADB modulo a power of 2
                    // - adding a round key
                    // - XORing x with a right-shifted version
                    // Here, x&lt;= mask  and mask+1 is a power of 2
                    x = (x*0xADB+this.rk[--r]) &amp; this.mask;
                    x ^= x&gt;&gt;&gt;this.rish;
                    }
                while (r!=0);
                }
            while (x&gt;=this.size);
            return x;
        }

    } // class MyCipher

    // MyShuffledArray implement a virtual square array where each line and column appears to be a random permutation
    static class MyShuffledArray {
        private final int size;         // dimension
        private MyCipher P,Q,R;

        // Constructor from rng source
        private MyShuffledArray(int size, Random rng) {
            assert size&gt;0 &amp;&amp; size&lt;=0x40000000: "MyShuffledArray.size must be positive and at most 1073741824";
            this.size = size;
            P = new MyCipher(size, rng);
            Q = new MyCipher(size, rng);
            R = new MyCipher(size, rng);
            }

        // Implement the virtual array
        private int Get(int col, int lin) {
            return R.Perm((P.Perm(col)+Q.Perm(lin))%this.size);
            }

        } // class MyShuffledArray

    // Example use
    final static int START_OF_RANGE  = 1;
    final static int END_OF_RANGE    = 9;
    final static int NUMBER_OF_LISTS = 3;
    final static int size = END_OF_RANGE - START_OF_RANGE + 1;

    public static void main(String[] args) {
        MyShuffledArray myShuffledArray = new MyShuffledArray(size, new SecureRandom());
        for (int j = 0; j &lt;NUMBER_OF_LISTS; j++) {
            for (int i = 0; i &lt;size; i++)
                System.out.print(String.format(i==0?"[%d":", %d", myShuffledArray.Get(i,j) + START_OF_RANGE));
            System.out.println("]");
        }
    }
}




This answer identifies that we are generating a latin square. Here is a literature survey.