Questions tagged [permutations]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
43
votes
12answers
4k views

Applications of representation theory of the symmetric group

Inspired by this question and in particular the final paragraph of Or's answer, I have the following question: Do you know of any applications of the representation theory of the symmetric group in ...
29
votes
2answers
2k views

Can you identify the sum of two permutations in polynomial time?

There were two questions asked recently on cs.se which were either related to or had a special case equivalent to the following question: Suppose you have a sequence $a_1, a_2, \ldots a_n$ of $n$ ...
27
votes
1answer
692 views

Deciding if a given $\mathsf{NC}^0$ circuit computes a permutation

What is the complexity of deciding whether an $\mathsf{NC}^0$ circuit with $n$ input bits and $n$ output bits computes a permutation of $\{0,1\}^n$? in the other words, whether every bit strings in ...
27
votes
2answers
721 views

Deciding whether an NC${}^0_3$ circuit computes a permutation or not

I would like to ask about a special case of the question “Deciding if a given NC0 circuit computes a permutation” by QiCheng that has been left unanswered. A Boolean circuit is called an NC0k circuit ...
27
votes
4answers
2k views

Complexity of applying a permutation in-place

To my surprise, I was not able to find papers about this - probably searched the wrong keywords. So, we've got an array of anything, and a function $f$ on its indices; $f$ is a permutation. How do ...
25
votes
1answer
752 views

Recognizing sequences with all permutations of $\{1, \ldots, n\}$ as subsequences

For any $n > 0$, I say that a sequence $s$ of integers in $\{1, \ldots, n\}$ is $n$-complete if, for every permutation $\mathbf{p}$ of $\{1, \ldots, n\}$, written as a sequence of pairwise distinct ...
21
votes
2answers
974 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 ...
17
votes
2answers
754 views

Set Cover for Permutation Matrices

Given a set S of nxn permutation matrices (which is only a small fraction of the n! possible permutation matrices), how can we find minimal-size subsets T of S such that adding the matrices of T has ...
17
votes
1answer
709 views

Asymptotically, how many permutations of $[1..n]$ have at most $k$ inversions?

Consider a permutation $\sigma$ of $[1..n]$. An inversion is defined as a pair $(i, j)$ of indices such that $i < j$ and $\sigma(i) > \sigma(j)$. Define $A_k$ to be the number of permutations ...
16
votes
1answer
792 views

Computing parity of a permutation in a streaming-fashion way

I'm looking for a one-pass algorithm which computes parity of a permutation. I assume that an input permutation is given by stream $\pi[1], \pi[2], \cdots, \pi[n]$. The output should be the parity of ...
15
votes
6answers
3k views

Complexity of the Fisher-Yates Shuffle Algorithm

This question is in regard to the Fisher-Yates algorithm for returning a random shuffle of a given array. The Wikipedia page says that its complexity is O(n), but I think that it is O(n log n). In ...
15
votes
1answer
360 views

Two matrices related by a permutation $B = P A P^T$ - complexity

What is computational complexity of the following problem: given two complex $n\times n$ matrices $A$ and $B$ check if there is a permutation matrix $P$ such that: $$B = P A P^T.$$ If it helps, one ...
15
votes
1answer
754 views

Permutations with forbidden subsequences

Let $[n]$ denote the set $\{1,...,n\}$ and C(n,k) denote the set of all $k$-combinations of elements from $[n]$ without repetition. Let $p= p_1p_2...p_k$ be a $k$-tuple in $C(n,k)$. We say that a ...
13
votes
2answers
633 views

Complexity of permutation related problems

Given a group $G$ of permutations on $[n]=\{1, \cdots, n\}$, and two vectors $u,v\in \Gamma^n$ where $\Gamma$ is a finite alphabet which is not quite relevant here, the question is whether there ...
12
votes
4answers
550 views

Reordering data (set of strings) to optimize for compression?

Are there any algorithms for reordering data to optimize for compression? I understand this is specific to the data and the compression algorithm, but is there a word for this topic? Where can I ...
12
votes
1answer
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, ...
11
votes
1answer
270 views

Reversible polynomial circuit iff polynomial reversible circuit?

My question is about efficiently computable bijective functions. Informally I'm interested in: If a bijection is computable in polynomial time, can we compute it by a polynomial number of bijective ...
11
votes
0answers
289 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 ...
10
votes
1answer
676 views

Probability of generating a desired permutation by random swaps

I'm interested in the following problem. We're given as input a "target permutation" $\sigma\in S_n$, as well as an ordered list of indices $i_1,\ldots,i_m\in [n-1]$. Then, starting with the list $L=...
10
votes
1answer
298 views

Evaluating symmetric polynomials

Let $f:\mathbb{K}^n \to \mathbb{K}$ be a symmetric polynomial, i.e., a polynomial such that $f(x)=f(\sigma(x))$ for all $x \in \mathbb{K}^n$ and all permutations $\sigma \in S_n$. For convenience, we ...
10
votes
1answer
309 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 ...
10
votes
3answers
769 views

Permutation pattern matching in strings

Loosely speaking, permutation pattern matching deals with problems of the following kind: Given permutations $\pi$ in $S_n$ and $\sigma$ in $S_m$, with $m\leq n$, does $\pi$ contain a subsequence $...
10
votes
2answers
690 views

How to shuffle colour balls?

I have 400 balls, in which 100 are red, 40 are yellow, 50 are green, 60 are blue, 70 are purple, 80 are black. (balls of the same colour are identical) i need an efficient shuffling algorithm, so ...
10
votes
1answer
128 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 ...
9
votes
2answers
164 views

Complexity of Computing Lexicographically Minimal Element of Orbit

Given strong generators for a group $(G \leq S_n, *)$ acting on bitstrings of length $n$ and an element $s \in \{0, 1\}^n$, how hard is it to compute the lexicographically minimal element of $G.s$, ...
9
votes
2answers
386 views

Is there an efficient algorithm to find the i-th dearrangement?

Here is the background for this question. Friends and I were playing a game where everyone needs to give another people some gift. In order to determine who should give gift to whom, we decide to drew ...
8
votes
1answer
905 views

Efficiently finding the minimum number of transpositions needed to sort a list

I'd like an efficient method for calculating the minimum number of transpositions needed to sort a list. I don't need to know what the transpositions actually are. For example, the list [1, 1, 2, 0] ...
8
votes
1answer
227 views

Hierarchical sorting strategies for pattern-avoiding permutations?

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 := \...
8
votes
0answers
386 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 ...
7
votes
3answers
784 views

Choosing random permutations in “strict” polynomial time

This question compares "strict" polynomial time, as opposed to "expected" polynomial time. Let $S = \{1,2,…,n\}$, and let $O$ be an ordering on elements of $S$ (the number of orderings is $n!$). A ...
7
votes
2answers
594 views

Is this vertex ordering optimization NP-Hard?

Could you help me to prove that the following problem is NP-hard? Problem. Given an undirected graph $G=(V,E)$, find an ordering of the nodes such that $\sum\limits_{v\in V}|succ(v)|\times|pred(v)|$ ...
7
votes
4answers
586 views

How to shuffle cards with restrictions?

I want as uniformly as possible to pick from all full shuffles such that this additional criterion applied. For example, i would like to shuffle 4 decks of cards, and make sure: Any consecutive 4 ...
7
votes
1answer
266 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''...
7
votes
0answers
195 views

Can every efficiently computable permutation be written as the composition of two efficiently computable involutions?

It is well-known that every permutation can be written as the composition of two involutions. Suppose that $p$ is a polynomial. Then does there exist a polynomial $q$ such that if $f:\{0,1\}^{n}\...
6
votes
0answers
213 views

Proving P-Isomorphism between two languges

The famous Isomorphism Conjecture states that all NP-complete problems are isomorphic via polynomial-time computable and invertible bijections (reductions). Padability is the only property that I know ...
6
votes
0answers
208 views

Lowerbounds for in-situ permutation

What is the best known lowerbound for the worst case complexity of in-situ permutation (also called in-place rearrangement)? Has there been any reported progress after the 1970's article by Knuth (...
6
votes
0answers
149 views

Constraint Satisfaction Problem: Choosing real numbers with variance in a certain range

I have a set of n real numbers. I want to repeatedly choose subsets of k elements such that the variance of these k numbers falls within some specified range, r = [l, u]. Moreover I want to do this ...
5
votes
2answers
1k views

Matrix permanent is 0

Valiant's theorem says that computing the permanent of an $n\times n$ matrix is #P-hard. Is the problem of determining if a permanent is 0 any easier? This arises in the context of sequence A006063 in ...
5
votes
1answer
1k views

Number of permutations which have the same Kendall-Tau distance

Input: The number of elements $m$ and an (positive) integer distance $d$. Ouput: The number of permutations of $m$ elements which have Kendall-Tau distance $d$ from a fixed permutation. I think there ...
4
votes
1answer
256 views

The complexity of decomposing a bi-stochastic matrix

A bistochastic matrix $A$ is a matrix with positive entries in which each row/column sums to $1$. By the Birkhoff von-Neumann theorem $A$ is a convex combination of permutation matrices. Further, by ...
4
votes
1answer
149 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 ...
4
votes
0answers
128 views

Characterizing the ANF of Single-Cycle Boolean Permutations

Given a function $F: \{0, 1\}^n \to \{0, 1\}^n$, we say that $F$ is a boolean permutation (also sometimes called a vectorial boolean function or an s-box in the literature) if $F$ is a bijection. We ...
4
votes
0answers
76 views

Finding a largest symmetrical subset of a k-CNF propositional formula

I have a k-CNF propositional formula $F$ which do not admit any global symmetry i.e. there is no permutation $\sigma$ of its variables such that $\sigma(F) = F$ . I'm interested in finding the largest ...
4
votes
0answers
65 views

Can an efficiently computable non-one way permutation be written as the composition of polynomially many easy to compute involutions?

Suppose that $p$ is a polynomial. Then does there exist a polynomial $q$ where if $f:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ is a bijection where both $f$ and $f^{-1}$ are computable by circuits with at ...
4
votes
0answers
146 views

Recognition problem of cycle permutation graphs

A cycle permutation graph is a cubic graph composed from two $n$-cycles each labeled $1, 2,..., n$, with additional edges connecting vertex $i$ in the first cycle to vertex $\pi(i)$ in the second, ...
4
votes
0answers
103 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 ...
3
votes
2answers
493 views

Finding the identity with permutation chains

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 $...
3
votes
2answers
171 views

Sort with random deviations

I'm looking for an algorithm that will take a sorted array of numbers and generate a random permutation of this array in such a way that the probability of finding a larger element earlier in a ...
3
votes
1answer
203 views

How hard is recognizing a permutation that is a square for the shift product?

This is a continuation of my attempts to generate simple combinatorial computational problems that turn out to be computationally hard (NP-complete). In this pursuit, I came up with a permutation ...
3
votes
2answers
2k views

Counting length-k increasing subsequences in a permutation

(Originally posted on Math.SE.) Let $f$ be a permutation on $n$ letters. I want to count the number of $k$-long increasing subsequences quickly. One approach is to first use divide and conquer to ...