# Questions tagged [permutations]

The tag has no usage guidance.

75 questions
Filter by
Sorted by
Tagged with
271 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 (M2)...
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 ...
145 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 ...
130 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 ...
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 ...
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 ...
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] ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
257 views

149 views

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 ...
625 views

### How to compute ROOK Polynomials for NxM Matrices [closed]

How to compute ROOK Polynomials for NxM Matrices for k objects ?