# Tag Info

Accepted

### What's a uniform shuffle?

A uniform shuffle of a table $a = [a_0, ..., a_{n-1}]$ is a random permutation of its elements that makes every rearrangement equally probable. To put it in another way: there are $n!$ possible ...
Accepted

### How hard is this constrained $n$-rooks problem?

This problem can be solved in polynomial time, using bipartite matching. For a bipartite graph with $n$ vertices on the left, corresponding to the $n$ rows, and $n$ vertices on the right, ...
Accepted

### Given a permutation of 0..N-1, determine the index of that permutation in the lexicographic ordering of all permutations of 0..N-1, in linear time

The 2007 paper Linear-time ranking of permutations gives a linear time ranking algorithm for the lexicographic order, assuming arithmetic on numbers of length $O(n\log n)$ takes constant time. The ...
Accepted

### How should I design a hash table where all the keys are permutations?

Simply compute the index of the permutation into the sorted list of all permutations and use that as your hash key. This can be achieved with a relatively simple algorithm: https://stackoverflow.com/...
Accepted

### Searching the space of permutations

Consider the following set of $n$ orders, which I give for $n = 6$: $$123456 \\ 213456 \\ 132456 \\ 124356 \\ 123546 \\ 123465$$ Hopefully the generalization to arbitrary $n$ is clear. If you never ...
Accepted

### Distance-preserving permutations

The only permutations who satisfy this condition are the identity and its inverse (as string inverse), $\pi(i)=n-i+1$. Note that $1$ has to be in one of the edges (if it has two neighbors, then at ...

### What's a uniform shuffle?

As Andrej explains in his answer, a random shuffle consists of applying a uniformly random permutation on the input, or equivalent. Your algorithm, in contrast, applies $n$ random transpositions. This ...

### Deriving the average number of inversions across all permutations

For $i < j$ and a random permutation $A$, let $X_{ij}$ be the indicator variable for the event $A[i] > A[j]$. Clearly $\Pr[X_{ij} = 1] = 1/2$ and so $E[X_{ij}] = 1/2$. The total number of ...

### Generate all permutations of 1 to n with i stacks

It is not clear in the question what operations are allowed on the input and how to view or access the output. However, since we are dealing with all permutations, the answer is the same whether the ...
Accepted

### Find an optimal ordering

This problem, which I'll call CO for Column Ordering, is NP-hard. Here's a reduction from the NP-hard problem Vertex Cover (VC) to it: Decision problem forms of VC and CO Let the input VC instance ...
Accepted

### Permute an array in O(n) time with O(1) extra space with a given ordering function?

Reverse the last half of the array in-place and then apply one of the interleaving algorithms mentioned in this question. That question is for even $n$, and I didn't check whether the answers work ...
Accepted

### What is the maximum number of indices one can create on a table with N columns?

I assume you mean the following: given $N$ columns, there are $N$ single columns, giving $N$ different indices $N(N-1)/2$ pairs of columns, and 2 ways to combine each pair, giving $N(N-1)$ different ...
This approach cannot work, for the following simple reason. The probability to obtain any permutation is of the form $A/n^n$, for integer $A$. However, we need it to be $1/n!$, so we need $A = n^n/n!$....
Here is a simple iterative solution. We maintain two arrays, an output array $L$, and a Boolean array $A$, which keeps track of the elements currently in $L$. We update $A$ as we add and remove ...