Algorithm for retrieving all the permutations (randomized) for a vector sequence 1...N with only unique values

Question

Here is the problem: I have a vector of $N$ elements long (containing only unique values from $1...N$).

1. I am searching for an algorithm to obtain all the (randomized) combinations possible, where each value can only appear once.

That is for instance the following vectors in case $N=3$.

$(1, 2, 3)$

$(1, 3, 2)$

$(2, 1, 3)$

$(2, 3, 1)$

$(3, 1, 2)$

$(3, 2, 1)$

Any more?

Follow up questions:

1. Is there a way to filter out rules that seem to be systematic, for example the vector $(1,2,3,4)$, as I am only searching for randomized combinations.
2. How many combinations are there possible? Is it 100x100?
3. Is there a built-in Matlab function available for this?

Answer 1

These are not combinations but permutations. There are $n!$ permutations of $(1,2,\cdots,n)$, with $n!=1\cdot2\cdots n$.

There is a very simple algorithm to get them, one at a time, in lexicographic order (that is, the order you use in your example).

Start with a permutation $(a_1,a_2,\cdots,a_n)$, we want the next one in lexicographic order.

1. Find the smallest index $i$ such that the sequence $(a_i,a_{i+1},\cdots,a_n)$ is decreasing.
2. If $i=1$, you are done, because the whole permutation is decreasing, and it's the last.
3. Reverse this sequence $(a_i,a_{i+1},\cdots,a_n)$, so that it's now increasing.
4. Exchange $a_{i-1}$ with $a_j$, where $j$ is the smallest index, such that $j\geq i$ and $a_j>a_{i-1}$. You have then the next permutation.

See RosettaCode for several implementations. For Matlab, you have the perms function.

You will find this algorithm and other ones in Knuth's TAOCP volume 4 fasc. 2. The whole volume 4 is about combinatorial algorithms.