All Questions
7 questions
4
votes
0
answers
155
views
Permutation generation problem using swaps
This is motivated by Aaronson's post, Probability of generating a desired permutation by random swaps. I am interested in a related problem where the swaps are given in the input.
We're given as input ...
- 2,993
1
vote
1
answer
209
views
Deciding if given number is a permanent of matrix
The permanent of an $n$-by- $n$ matrix $A=\left(a_{i j}\right)$ is defined as
$$
\operatorname{perm}(A)=\sum_{\sigma \in S_{n}} \prod_{i=1}^{n} a_{i, \sigma(i)}
$$
The sum here extends over all ...
12
votes
2
answers
292
views
Permutation search problems with no known $o(n!)$ algorithms
I am looking for problems for whose solution no known subfactorial algorithms are known. I am particularly interested in questions of isomorphism; that is, is there a permutation that converts one ...
- 333
2
votes
0
answers
151
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 ...
- 2,993
15
votes
2
answers
512
views
Does a classification of simultaneous conjugacy classes in a product of symmetric groups exist?
Let the symmetric group $S_n$ on $n$ letters act on $S_n^d=S_n\times\cdots\times S_n$ by simultaneous conjugation, i.e. $\pi\in S_n$ acts on $(\sigma_1,\ldots,\sigma_d)\in S_n^d$ by $\pi.(\sigma_1,\...
- 4,902
1
vote
1
answer
321
views
Cycles of Permutation Related to Rectangular Matrix Transposition
let the entries of a rectangular matrix $A\in\mathbb{C}^{m\times n}; m,n\in\mathbb{N}$ be stored in row-order in a linear vector $v$, i.e. $A_{i,j}=v_{i*m+j}$
Question:
How can the first element ...
- 13.2k
35
votes
1
answer
2k
views
How hard is reconstructing a permutation from its differences sequence?
My interest in combinatorially motivated computational problems led me to search for simple problems that turn out to be computationally hard. In this pursuit, I came up with a problem which I hope is ...
- 2,993