15

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 rearrangements of $n$ elements and you need to pick one of them uniformly at random. Many methods for shuffling seem uniform to people but are not and so it is ...


10

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, corresponding to the $n$ columns. Include an edge from $i$ to $j$ if $C(i,j)=1$, i.e., if you're allowed to place a rook in the $(i,j)$ square (in the $i$th row and $j$th ...


9

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/questions/5131497/find-the-index-of-a-given-permutation-in-the-sorted-list-of-the-permutations-of Once you have that index, you can make a table with exactly 9! ...


9

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 2001 paper Ranking and unranking permutations in linear time presents a linear time ranking algorithm not requiring fast arithmetic on large numbers, but not for ...


9

Without loss of generality you can assume that the target array is $0,1,...,n-1$: you can "relabel" the target array as 0,1,2,...,n-1 (and relabel the corresponding numbers in the source array, too). The allowed operation becomes "swap a number with x" (where x is not necessarily 0) and the target array is 0,1,2,...,n-1. You can build a directed graph with $...


8

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 compare $i$ and $i+1$ then you cannot tell apart permutation $1$ from permutation $i+1$. This means that you need at least $n-1$ comparisons (this is not an ...


8

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 least one of them is bigger than $2$ and the condition is not satisfied). Placing $1$ in the left edge forces the entire permutation to be the identity, and ...


8

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(\sigma)_i$ in $O(n)$ time as follows. Maintain an array $A[0, \dots, n-1]$ where each entry $A[i]$ is initialized to $0$. Then, for each $j$, increment $A[\min\...


7

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 cannot possible produce an exact random shuffle, since the probability of each resulting permutation is of the form $A/n^{2n}$, which cannot equal $1/n!$. ...


6

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 of $(0,\ldots,7)$, $o_i \in \{0,1,2\}$, and $o_7$ (say) is determined by $o_0,\ldots,o_6$. In total, this gives $8! \cdot 3^7 = 88179840$ degrees of freedom. ...


6

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 induction is here. For a constructive proof, you can follow the idea from here: Show that the maximum number of inversions is $\binom{n}{2}$. Observe that every ...


6

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 inversions is $\sum_{i<j} X_{ij}$, and so the average number of inversions is $$ E\left[\sum_{i<j} X_{ij}\right] = \sum_{i<j} E[X_{ij}] = \sum_{i<j} \frac{...


6

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 possibly be completed to a valid solution." (Wikipedia). So, basically, what you do is build incrementally all permutations. As soon as as you build a single ...


6

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 the inverse problem of turning "σ(1)σ(2)…σ(n)" to "12…n" using the moves "insert the current leftmost element somewhere different in the array", but they are ...


5

You can use inclusion-exclusion. There are $M!/(M-N)!$ choices for the first row. Fix these choices. The number of choices for the second row in which $T$ specific columns are bad (but the row itself is good) is $(M-T)!/(M-N)!$. According to the inclusion-exclusion principle, the required number is $$ \frac{M!}{(M-N)!} \sum_{T=0}^N (-1)^T \binom{N}{T} \frac{(...


5

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 matrices is bistochastic. Also, there could be many ways of representing a given bistochastic matrix as a convex combination of permutation matrices. As a simple ...


5

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 not) could change as a result of the swap: $(i,j)$ and, for $i < k < j$, $(i,k)$ and $(k,j)$. We can distinguish two cases: $a_i < a_j$ and $a_i > ...


5

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.


5

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 number of elements to the left of $i$ that are greater than $i$. Basically that gives you a bijection between $S_n$ and $\prod_{1\le i\le n} \{0,\ldots,i-1\}$ and ...


4

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 have this help you with hashing. The size of the hash table is determined by how many keys you need to store, not by the size of the space of possible keys. The ...


4

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.


4

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 number of constructions you could use for your purposes. There's a bunch of research literature on the problem, with different schemes that are optimized for ...


4

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 solved using exponential generating functions (and algorithmically, using dynamic programming). For example, the number of strings of length $\ell$ in your ...


4

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 Concentration of measure for the analysis of algorithms, as well as in many lecture notes, such as this one by Hariharan Ramesh.


4

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) = \lnot y$, $\sigma(y) = z$, and $\sigma(z) = x$, then $A(x,y,z) \vDash B(x,y,z)$ implies also $A(\lnot y, z, x) \vDash B(\lnot y, z, x)$. Let $G$ be the set of ...


4

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 be $(V, E, k)$. It represents the question: "Given the graph $(V, E)$, is it possible to choose a set of at most $k$ vertices from $V$ such that every edge in $...


4

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 for odd $n$ as well. If they don't and it's needed you can do a left rotation to move the middle element to the end (its correct position) and then use one of the ...


4

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 indices $\frac{N(N-1)(N-2)}{2 \cdot 3}$ triples of columns, and $3 \cdot 2$ ways to combine each triple, giving $N(N-1)(N-2)$ different indices and so on. This ...


4

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!$. Unfortunately, for $n \geq 3$ this is not an integer. One can still ask why we might expect this algorithm to work, and where is the gap between our ...


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