The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [permutations]

The tag has no usage guidance.

21 questions
Filter by
Sorted by
Tagged with
11k views

2k views

Are permutations of context-free languages context-free?

Given a context-free language $L$, define the language $p(L)$ as containing all permutations of strings in $L$ (i.e. all strings in $L$ such that the order of symbols is not important). Is $p(L)$ ...
527 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 ...
53 views

Indexing a random permutation

I am curious if there exists a method for specifying a permutation $F_k: X \to X$ with a small(ish) $k$. Something that comes very close to my goal is a block cipher, say AES. But block ciphers have ...
273 views

Random permutations by probability matrix

I have the following problem: I need to generate $\ell$ random permutations each of length $n$ from a list of $m$ elements ($m \ge n$) by a predefined probability matrix $P$ of size $n$ x $m$. ...
50 views

Counting permutations whose elements are not exactly their index ± 1

This is a special case of the question: Counting permutations whose elements are not exactly their index ± M The $M=0$ case has already been solved, but no one was sure how to work out the non-...
77 views

Algorithm to generate integer sets fulfills restrictions

I'm trying to solve the following problem. Input positive integers $v$, $b$ and $\ell$. ($\ell\leq v\leq b\ell$.) Output A list $S_1, \dots, S_k$ of all possible integer multisets (a ...
188 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 ...
Is there any efficient algorithm which is able to generate nearly uniform samples of permutations in case of position restrictions? Consider $N \times N$ restriction matrices $R$, that is matrices ...