16 votes
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 ...
user avatar
10 votes
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, ...
user avatar
  • 140k
9 votes
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 ...
user avatar
9 votes
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/...
user avatar
  • 206
8 votes
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 ...
user avatar
8 votes
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 ...
user avatar
  • 13.1k
7 votes

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 ...
user avatar
7 votes

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 ...
user avatar
7 votes

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 ...
user avatar
  • 33k
7 votes
Accepted

Faster algorithm for a specific inversion

Each element $j$ contributes $1$ to the cardinality of all sets $\{j > i \mid \sigma_j > i\}$ for which $i < \min\{\sigma_j, j\}$, and $0$ to the other sets. You can compute all $n$ values $K(...
user avatar
  • 22.7k
6 votes
Accepted

Indexing into a pattern database - Korf's Optimal Rubik's Cube solution

You don't explain what the numbers from 0 to 23 mean, but according to this answer, you can represent the state of the corners using eight pairs $(p_i,o_i)$, where $(p_0,\ldots,p_7)$ is a permutation ...
user avatar
6 votes
Accepted

Deriving the average number of inversions across all permutations

You can not go directly from one equation to the other; you need to add a whole proof which is separate from what I explain there. Hence my statement "it has been shown". A boring proof using ...
user avatar
  • 70.8k
6 votes
Accepted

Using backtracking to find all possible permutations in a string

Backtracking is a general algorithm "that incrementally builds candidates to the solutions, and abandons each partial candidate ("backtracks") as soon as it determines that the candidate cannot ...
user avatar
  • 9,592
6 votes
Accepted

Stack Permutation Algorithm

Ok here's my attempt 2 which won't construct the sequence of moves, but it at least proves what the optimal number of moves is and gives an indicator of how to construct the sequence. I'm addressing ...
user avatar
  • 464
5 votes

Random permutations by probability matrix

Your problem is not well-defined. As David Eisenstat notes in his comment, your matrix actually has to be bistochastic rather than just stochastic, since every convex combination of permutation ...
user avatar
5 votes

Minimizing inversions in an array with a single swap

Let's calculate the difference in number of inversions given that you swap $a_i$ and $a_j$. We can assume that $i < j$. There are three kinds of pairs of indices whose status (being inversions or ...
user avatar
5 votes

Shuffling a file on disk using $O(\log n)$ memory

The algorithm you suggest doesn't result in a uniform permutation. An in-place algorithm which works for every file size is the Fisher–Yates shuffle.
user avatar
5 votes
Accepted

number of permutation with k inversions

This is only a sketch of solution (there might be some off-by-ones) Looking at a permutation of $\{1\ldots,n\}$ is equivalent at looking its inversion table $(a_1, \ldots, a_n)$ where $a_i$ is the ...
user avatar
  • 626
4 votes

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

Since you have only 362,880 possible keys, you can uniquely represent every key with just 19 bits. (Where a really naïve representation of the key might take 9*4 = 36 bits). I can't see a way to ...
user avatar
4 votes

Algorithm to compose identity from a set of permutations

Assuming that "smallest composition" means smallest number of permutations used in the composition, then the NP-complete Pancake Flipping Problem is a special case of your problem.
user avatar
  • 1,944
4 votes

Invertible function that randomizes order

You are looking for a pseudorandom permutation on the set $\{0,1,2,\dots,n-1\}$. In cryptography, this has been studied under the (counter-intuitive) name "format-preserving encryption". There are a ...
user avatar
  • 140k
4 votes
Accepted

Lexicographically k-th small string

You are asking two questions. The first is an enumeration question, and the second is about generation or encoding/decoding. The enumeration question is a standard combinatorial exercise, which can be ...
user avatar
4 votes
Accepted

Chernoff-like Concentration Bounds on Permutations

Chernoff's bound applies to negatively correlated random variables, such as your hypergeometric distribution. You can find a full treatment in Dubhashi and Panconesi's very useful monograph ...
user avatar
4 votes
Accepted

Does it hold that $F \equiv \sigma(F)$ for a CNF formula $F$ and a permutation $\sigma$ s.t. $F \vDash \sigma(F)$?

The crucial observation is that if $A \vDash B$ then also $\sigma(A) \vDash \sigma(B)$. This follows since all $\sigma$ does is rename variables and flip some variables. For example, if $\sigma(x) = \...
user avatar
4 votes

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 ...
user avatar
4 votes
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 ...
user avatar
  • 12.3k
4 votes
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 ...
user avatar
4 votes
Accepted

What's wrong with the following shuffle algorithm?

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!$....
user avatar
4 votes
Accepted

Enumerating all partial permutations of given length in lexicographic order

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 ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible