Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

4
votes
0answers
110 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, ...
10
votes
3answers
303 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 ...
10
votes
1answer
269 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 ...
2
votes
1answer
55 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 ...
7
votes
1answer
113 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 ...
4
votes
0answers
74 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
vote
1answer
149 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 ...
11
votes
0answers
211 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
vote
0answers
104 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 ...
8
votes
1answer
156 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 := ...
9
votes
1answer
79 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 ...
16
votes
0answers
360 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 ...
5
votes
0answers
112 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 ...
4
votes
1answer
83 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$ ...
0
votes
0answers
84 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
1answer
79 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, ..., ...
-1
votes
1answer
45 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 ...
11
votes
1answer
1k 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, ...
2
votes
2answers
168 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 ...
25
votes
2answers
1k 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$ ...
-3
votes
1answer
109 views

the product of a matrix and a permutation matrix [closed]

Can a permutation matrix (P) be used to change the rank of another matrix (M)? Is there any literature to this effect, or to the contrary? I've tried a few small examples and the resulting matrix ...
3
votes
2answers
137 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 ...
2
votes
1answer
138 views

Computing unique subset intersections

Given a set S = {si : {zj : z ∈ N} }, what is a time-efficient algorithm for computing the unique sets of intersections of all of the subsets of S? As per @JeffE's comment below, there are edge ...
2
votes
0answers
116 views

Complexity of the standardization

Let $(A, \leq)$ be a totally ordered alphabet. The standardization ${\tt std}(u)$ of a word $u \in A^n$ is the unique permutation of $n$ elements having the same inversions as $u$ (recall that an ...
17
votes
1answer
467 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 ...
8
votes
2answers
245 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 ...
7
votes
1answer
432 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] ...
31
votes
12answers
1k 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 ...
21
votes
1answer
462 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 ...
13
votes
1answer
300 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 ...
5
votes
1answer
523 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 ...
7
votes
1answer
485 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 ...
7
votes
4answers
406 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 ...
25
votes
1answer
576 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 ...
1
vote
1answer
234 views

finding permutations which fulfills given conditions

Let $K$ be an ordered finite set. Consider some function $g:K^2 \rightarrow R$ such that $g(k1,k1') + g(k2,k2') \ge g(k1,k2') + g(k2,k1')$ where $k1 > k2$ (in order A1) and ...
9
votes
3answers
409 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 ...
2
votes
1answer
144 views

List the $k$-faces of an $n$-dimensional simplex

Suppose you are given an $n$-dimensional simplex S = [ 0 1 ... n ] which for the time being we think of as an ascending array of numbers from $0$ to $n$. Given ...
6
votes
0answers
153 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
2answers
450 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 ...
23
votes
4answers
1k 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 ...
3
votes
2answers
1k 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 ...
13
votes
2answers
542 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 ...
0
votes
1answer
508 views

How to compute ROOK Polynomials for NxM Matrices [closed]

How to compute ROOK Polynomials for NxM Matrices for k objects ?
6
votes
0answers
140 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 ...
13
votes
6answers
926 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 ...