Skip to main content
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.'s user avatar
  • 161k
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 ...
Ariel's user avatar
  • 13.4k
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 ...
Yuval Filmus's 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 ...
John L.'s user avatar
  • 39.1k
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(...
Steven's user avatar
  • 29.5k
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 ...
Raphael's user avatar
  • 72.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 ...
fade2black's user avatar
  • 9,837
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 ...
Matthew C's user avatar
  • 499
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$ ...
Nathaniel's user avatar
  • 15.8k
5 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 ...
Yuval Filmus's user avatar
5 votes
Accepted

Does this algorithm for permuting rows and columns of a matrix converge?

For an $n \times m$ matrix $M$, define the potential function $$ \Phi(M) = \sum_{i=1}^n \sum_{j=1}^m 2^{n-1-i} 2^{m-1-j} M(i,j). $$ If we write it as $$ \Phi(M) = \sum_{i=1}^n 2^{n-1-i} \sum_{j=1}^m 2^...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
4 votes
Accepted

Are there any known implementations of a functional Heap's Algorithm?

I'm really not very familiar with clojure. I think this is probably the longest clojure program I've written so far. But I guess it provides some sort of answer. On the whole, functional enumerations ...
rici's user avatar
  • 12.1k
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 ...
Yuval Filmus's 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) = \...
Yuval Filmus's 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 ...
j_random_hacker's 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 ...
orlp's user avatar
  • 13.6k
4 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 ...
md5's user avatar
  • 646
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 ...
Glorfindel's 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!$....
Yuval Filmus's user avatar
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 @...
Reinderien's user avatar
3 votes
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 ...
quicksort's user avatar
  • 4,272
3 votes
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) ...
Nitin Verma's user avatar
3 votes

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 ...
AShelly's user avatar
  • 161
3 votes
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 ...
D.W.'s user avatar
  • 161k
3 votes

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 ...
D.W.'s user avatar
  • 161k
3 votes
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 ...
Yuval Filmus's user avatar
3 votes

Mathematically determine if two strings are permutations of each other

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 ...
Roukah's user avatar
  • 771
3 votes

Mathematically determine if two strings are permutations of each other

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 ...
Raphael's user avatar
  • 72.6k

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