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
  • 158k
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
  • 38.8k
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.3k
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 ...
Yuval Filmus's user avatar
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.3k
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,817
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
  • 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$ ...
Nathaniel's user avatar
  • 13.7k
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.
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

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.'s user avatar
  • 158k
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
  • 12k
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
  • 12.9k
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
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
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

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
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,242
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
  • 158k
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
  • 158k
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

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