Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.
43

Here is the answer which elaborates upon the algorithm from the paper linked by Joe: http://arxiv.org/abs/0805.1598 First let us consider a $\Theta(n \log n)$ algorithm which uses divide and conquer. 1) Divide and Conquer We are given $$a_1, a_2, \dots , b_1, b_2, \dots b_n$$ Now to use divide and conquer, for some $m = \Theta(n)$, we try to get the ...


18

I'm pretty sure I've found an algorithm that does not rely on number theory or cycle theory. Note that there are a few details to work out (possibly tomorrow), but I'm quite confident they will work out. I handwave as I'm supposed to be sleeping, not because I'm trying to hide problems :) Let A be the first array, B the second, |A| = |B| = N and assume N=2^...


14

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

Define the run-partition number of a permutation $\pi$, denoted $r(\pi)$, using the following process. Let $k$ be the maximal integer such that the numbers $\min(\pi),\ldots,k$ appear in increasing order in $\pi$. Remove them from $\pi$, and repeat the process. The number of rounds it takes to consume the entire permutation is $r(\pi)$. For example, let's ...


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 $...


9

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

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

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! ...


8

Regardless of the algorithm you use, if you have $i$ bits of random data, you can generate a maximum of $2^i$ possible permutations. If $i$ is smaller than $log_2(n!)$, then there will be some permutations which cannot be produced, and you will have, in effect, decided which permutations those are when you encode your algorithm. (You may not be able to ...


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


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

Let's assume that the numbers $a_1,\ldots,a_n$ are integers, so that the problem is in NP for any fixed $f$. We construct a polynomial $f$ so that the problem is NP-complete, by reduction from vertex cover in cubic graphs ($3$-regular graphs). Let the instance of cubic vertex cover consist of a cubic graph $G=(V,E)$ and an integer $m$, and let $|V| = n$. ...


6

By Landauer's principle, if you want to take a uniform random permutation of $n$ keys to a sorted one, and not keep any bits in the computer which reveal what the uniform random permutation was, you need to erase $log n! \approx n \log_2 n$ bits. This will take $(n \ln n) k T$ energy. On the other hand, the computation taking the sorted array and $n \log_2 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 ...


5

Start with simple context-free (or even regular) languages, and see what happens. For instance determine $p(L)$ for $L = (ab)^*$ and $L=(abc)^*$.


5

The parametrization you present is quite arbitrary, and the condition that the mapping be onto only serves to confuse; let's ignore it for now. Instead, given $n,c$, let us consider the number of colorings of $K_n$ using $c$ colors (in your case, $c=n-2$) such that condition (3) is satisfied: for every three vertices $i,j,k$, $$ c(i,j) \leq \max(c(i,k),c(j,k)...


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

I second Raphael's remark that when shuffling cards, you don't want the deck to be "unsorted", but rather random. However, when analyzing any specific shuffle, there can be measures of randomness that can be used to prove that a small number of shuffles isn't enough to make the deck random enough. As a simple example, consider the "top card shuffle", in ...


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.


4

No, this is impossible unless $n \leq 2$. The probability that a permutation is generated by your algorithm using a random comparator is dyadic, i.e. of the form $A/2^B$, whereas the probability should be $1/n!$. When $n > 2$, there is no way to write $1/n!$ in the form $A/2^B$.


4

If you can get a random number in the range $\{0,\ldots,n!-1\}$, you can generate a permutation on $n$ elements using the Fisher-Yates algorithm. The idea is to think of this number as encoding the numbers used in the Fisher-Yates algorithm, using "mixed-base" notation.


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.


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