# Questions tagged [permutations]

The tag has no usage guidance.

165 questions
Filter by
Sorted by
Tagged with
63 views

### number of queries to recover the permutation

Imagine this game. I pick a permutation $p$ of $1..n$ and give you an oracle. When the oracle is queried with any sequence of $n$ numbers $\in 1..n$, it masks each number by applying some unknown ...
250 views

### Black-box combinatorial optimization problem over permutations

I am solving general black-box optimization problems like: x*: f(x) -> min, where x are permutations of length N (N = 50 for example, so brute force search is not possible). Objective function f(x) is ...
79 views

### Maximizing the sum of adjacent pairs of elements

I encountered the following interesting problem on stackoverflow: Given numbers $a(1)<\cdots<a(n)$, find a permutation $\pi$ that maximizes $$\sum_{i=1}^{n-1} a(\pi(i)) a(\pi(i+1)).$$ The ...
42 views

### Counting number of permutations respecting partial order

Suppose that we have an array $A$ of $n$ elements with some partial order known, e.g. for example as a $n\times n$ matrix containing $c_{ij} \in \{-1, 0, 1\}$ where $0$ represents unknown and $-1, 1$ ...
219 views

### How many similar binary search trees are made from different permutations?

If I have numbers ranging from 1 to n, and I generate all the permutations of these numbers. Now, I create Binary search tree from these permutations. For a value n i want to know how many BSTs would ...
125 views

32 views

### # of permutations satisfying special inequalties of each element0

Recently I was solving a counting problem, which needed this subproblem to be solved: Given integers $n$ and $t$ (where $1 \le t \le n$) and a decreasing function $f$, find the number of permutations ...
599 views

### Deriving the average number of inversions across all permutations

In the answer by Raphael to the question "Is there a system behind the magic of algorithm analysis?", there is an equation: \qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \...
78 views

### existence of a permutation that satisfies order-constraints

I would like to know if there is a simple algorithm for checking the existence of a permutation that satisfies a number of order-constraints. For example, suppose we have a set (1, 2, 3, 4, 5) and a ...
196 views

### Error correcting permutation code

Let's say you have $n$ symbols. You can encode a $\log_2(n!)$-bit message by permutating the symbols. I will call this a permutation code (if you have seen this concept before, I would love to see a ...
123 views

### Computing counts of combinations (?)

I'm not sure what terminology to use. Here is some input: John has items: A B D Peter has items: A C D And I want to produce such a table, that would count the #...
664 views

### Polynomial time solution for bipartite matching

Inspired by this StackOverflow question, I am wondering if there is an efficient algorithm for the following problem: Assume $n$ items and $n$ boxes, with all boxes numbered numerically and all ...
950 views

### What is the intuition behind Heap's Algorithm?

I am trying to get an intuition for Heap's Algorithm which is used to generate permutations of a given set. What I can't understand is why if n is even the letter swapped is i and when n is odd the ...