The permutations tag has no wiki summary.
2
votes
1answer
90 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 ...
1
vote
0answers
104 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 ...
16
votes
1answer
294 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
215 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
276 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] ...
29
votes
11answers
723 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 ...
14
votes
0answers
184 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 ...
11
votes
1answer
241 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
246 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 ...
6
votes
1answer
451 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
369 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 ...
22
votes
1answer
488 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
223 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 ...
7
votes
3answers
273 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
130 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 ...
