# Tag Info

## Hot answers tagged permutations

### 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/...
• 161k
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.4k

### 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 ...
• 278k

### 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 ...
• 39.1k
Accepted

• 278k

### 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,479
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 ...
• 13.6k
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 ...
• 646
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 ...
• 752
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!$....
• 278k

### 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 @...
• 247
Accepted

### Contained optimal combination of inputs

It is a well known problem, known as the multidimensional knapsack problem, and it is easily solvable by dynamic programming for the parameter / problem size you are dealing with here. A very similar ...
• 4,272
Accepted

### Correctness proof of the algoritm to generate permutations in lexicographic order

One can try to come up with the algorithm by oneself (thereby proving its correctness) after incremental understanding of: (a) how to define a permutation as "larger" (lexciographically) ...
• 307

### In-place algorithm for interleaving an array

Here is a non-recursive in-place in linear time algorithm to interleave two halves of an array with no extra storage. The general idea is simple: Walk through the first half of the array from left to ...
• 161
Accepted

### Computing counts of combinations (?)

These combinations of items are sometimes called itemsets. There are algorithms for finding itemsets that are especially common in a database; see association rule learning. In general there is no ...
• 161k

### Polynomial time solution for bipartite matching

This actually has nothing to do with the stable marriage problem; it's an instance of bipartite matching. (It's not related to stable marriage, becuase you don't have an ordering on the preferences ...
• 161k
Accepted

### Can we count the number of inversions in time $\mathcal{O}(n)$?

There are $o(n\log n)$ algorithms in the RAM model. Dietz gave an $O(n\log n/\log\log n)$ algorithm in his 1989 paper Optimal algorithms for list indexing and subset rank, and Chan and Pătraşcu gave ...
• 278k
Your algorith isn't correct. Take $abbc = [1, 2, 2, 3]$ and $acd = [1, 3, 4]$. Their product is $12$ and their sum $8$, yet they aren't permutations of each other; they don't even have the same ...
You need a function that uniquely maps multi-sets of symbols to numbers -- a bijection. Here is one example that is easy to understand. Say your string is $w = w_1 \cdot \dots \cdot w_n$ over ...