# Questions tagged [permutations]

The tag has no usage guidance.

76 questions
Filter by
Sorted by
Tagged with
1 vote
152 views

### Decomposition of a permutation into increasing subsequences

Given a permutation $P$, the goal is to decompose this permutation into $k$ increasing subsequences $L_1,L_2,\ldots,L_k$, such that every element in $P$ appears exactly once in some increasing ...
• 137
197 views

### What does width $4$ permutation branching program correspond to?

$L$ can be computed by a family of programs over $S_3$ of polynomial length if and only if $L$ can be computed by a family of $MOD3 ◦ MOD2$ circuits of polynomial size. $L$ can be computed by a family ...
• 12.5k
92 views

### Inverting Kronecker product on vectors is in P?

Problem: Given a vector V of positive integers, find two vectors v1 and v2 such that the Kronecker product of v1 and v2 is equal to p(V) (where p(V) is a suitable permutation of V). Example: Input: V={...
• 61
50 views

### Dynamic permutation cycle data

Let $\pi \in S_n$ be a permutation of $\{1, \ldots, n\}$. Does there exist a simple data structure that admits the following operations in polylogarithmic time? sameCycle($\pi,x,y$): determines ...
• 121
111 views

273 views

### Distinguishability a set of permutations

Given integers $d<n$, find the largest $k$ such that there exists a set of $k$ permutations $\sigma_1,\cdots,\sigma_k$ on $[n]$, such that any size-$d$ subset $T\subseteq [n]$ is distinguishable''...
• 437
70 views

• 1,552
162 views

### Computing size of permutation group from generators

You're given $k$ permutations $a_1,\dots,a_k$. Consider closure of this set under the composition operation. What are most efficient and simple algorithms to calculate the size of this closure?
115 views

• 13.4k
69 views

### Efficient (non-crypto-grade?) pseudorandom permutations with arbitrary domain size

I'm looking for an efficient/simple (even if not necessarily cryptographically strong) algorithm for implementing pseudorandom permutations with domain cardinality other than a power of 2. (FWIW, the ...
• 531
333 views

### Recent progress in permutation groups algorithms?

I am interested in algorithms for finite groups as implemented in the GAP package. It seems that all known algorithms in this field deal with permutation groups/matrix groups; two fundamental ones are ...
118 views

### The rank-polynomial of a graded poset

Let $P$ be a graded poset with rank function $r$. We may then define its rank-polynomial as: $R_P(q) = \sum_{x \in P} q^{r(x)}$. This definition can be applied to several interesting posets, for ...
• 1,292
1 vote
176 views

### More questions about permutations

I'm interested in permutations classes defined by one or several excluded patterns of length 4. In particular, the following classes seem interesting but not so-well studied algorithmically. the skew-...
• 1,292
299 views

### Generalizations of the determinant/permanent problem?

A tantalizing open question in computational complexity is to understand the 'behavioral differences' between the determinant and the permanent. While the former is computable in polynomial time with ...
• 1,292
1 vote
125 views

### Some algorithmic questions on permutations

I'm interested in the possibility of fast algorithms for the following two problems on permutations. 1) Given a permutation $\pi$ and an integer $k$, compute a pair $(\mathcal{C},\mathcal{A})$ where ...
• 1,292
For a class $\mathcal{C}$ of permutations, we cannot expect to sort the permutations of $\mathcal{C}$ with less than $O(\log |\mathcal{C}_n|)$ comparisons, where by convention $\mathcal{C}_n := \... • 1,292 10 votes 1 answer 131 views ### Encoding sets of permutations with a generating set and a set of excluded elements Polynomial-time algorithms are known for finding generating sets of permutation groups, which is interesting since we can then represent those groups succinctly without giving up on polynomial-time ... • 3,234 21 votes 2 answers 1k views ###$NP$-completeness of recognizing the difference of two permutations Shor stated, in his comment to anonymous moose's answer to this question Can you identify the sum of two permutations in polynomial time?, that it is$NP$-complete to identify the difference of two ... 8 votes 0 answers 395 views ### Permutation optimization problem Here is the problem as posed by Jerrum: "The computational complexity of the following problem is investigated: Given a permutation group specified as a set of generators, and a single target ... • 2,331 4 votes 1 answer 162 views ### Compatible partial permutations Please, correct my terminology as I am not a combinatorician (I am using http://en.wikipedia.org/wiki/Partial_permutation). Please, refer me to the solution if this is a solved problem. Let$P_k$be ... • 223 0 votes 0 answers 111 views ### "Partial" invert a one-way permutation First of all, to my best understanding, traditionally, if$f$is a one-way function that maps a length$l$bit string to another length$l$bit string (i.e.,$f:\{0,1\}^l\rightarrow\{0,1\}^l$), then ... 2 votes 1 answer 116 views ### Effect of constraints Density on the hardness of Betweness problem Betweeness problem is well known NP-complete permutation problem. Given a family$M$of triples$(a_i, a_j, a_k)$, the problem is to decide whether a permutation$\Phi$of elements$a_1, a_2, ..., a_n$... -1 votes 1 answer 54 views ### Algorithm for calculating substitution combination with ordering I need to calculate the combinations of elements with a substitution element. For example for elements [A,B] if the substitution is X the results should be ... • 101 12 votes 1 answer 2k views ### Efficient algorithm for existence of permutation with differences sequence? This question is motivated by this post, Can you identify the sum of two permutations in polynomial time? , and my interest in computational properties of permutations. A differences sequence$a_1, ...
I have the following problem: I'm given a list of size $K$ of random integer permutations of $[1..n]$, named $P_1$ to $P_K$, and an additional random permutation $Q$. How hard is to find a sequence \$...