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 ...
- 29.1k
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/...
- 206
9
votes
Compute Permutation Number
This task is known as ranking permutations. It can be solved with the factorial number system (https://en.wikipedia.org/wiki/Factorial_number_system). See also https://stackoverflow.com/q/1506078/...
D.W.♦
- 150k
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 ...
- 273k
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 ...
- 13.3k
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 ...
- 273k
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 ...
- 273k
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 ...
- 37.3k
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(...
- 26.1k
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 ...
- 273k
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 ...
- 71.6k
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 ...
- 9,702
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 ...
- 489
6
votes
Accepted
Compute Permutation Number
A first observation is that for all $k\in \{1, …, n\}$, there are $(n-1)!$ permutations of size $n$ beginning with $k$.
For a permutation $\sigma = (k_1, …, k_n)$, that means that the rank of $\sigma$ ...
- 11.8k
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.
- 273k
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 ...
- 273k
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 ...
- 626
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.
- 1,977
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 ...
- 17.5k
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 ...
D.W.♦
- 150k
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 ...
- 273k
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 ...
- 273k
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) = \...
- 273k
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 ...
- 5,314
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 ...
- 12.5k
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 ...
- 740
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!$....
- 273k
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 ...
- 273k
4
votes
Enumerating all partial permutations of given length in lexicographic order
The most appealing solution so far seems to be a spin on Python's own permutations function (source) that can be slightly simplified for this use case; thanks @...
- 237
Only top scored, non community-wiki answers of a minimum length are eligible