# Questions tagged [permutations]

The tag has no usage guidance.

15 questions
Filter by
Sorted by
Tagged with
992 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)|$ ...
• 563
5k 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 ...
• 18.2k
3k 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 ...
• 8,941
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$ ...
• 24.8k
859 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 ...
• 173
760 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 ...
• 443
755 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 ...
• 16.5k
5k 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 ...
• 623
2k views

• 13.7k
643 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 ...
• 271
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 ...