All Questions
14 questions
19
votes
9
answers
3k
views
How can I generate random permutations of [n] with k cycles, where k is much larger than log n?
I've been thinking a lot lately about random permutations. It's well-known that the mean and variance of the number of cycles of a permutation chosen uniformly at random from Sn are both ...
- 14k
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
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
10
votes
1
answer
519
views
Explicit algorithm for composing permutations in factorial notation
Given two permutations p1 and p2 in factorial notation, is there an algorithm which computes their composition directly, i.e. without translating to a different notation (like Cauchy's 2-line notation,...
- 11.8k
9
votes
0
answers
534
views
Generating $S_n$ with a fundamental transposition and a big cycle
I apologize in advance if this is too amateur, this is not really my area, but I'm very curious.
We have a permutation $\pi \in S_n$ and we want to represent it as a product of $\sigma = (1\;2)$ and $...
- 231
8
votes
1
answer
1k
views
Is there an efficient algorithm to check whether two matrices are the same up to row and column permutations?
Define $\mathcal M_n$ as the set of all $n\times n$ matrices with each entry either 1 or $x$. Two such matrices are equivalent iff they can be obtained from each other by swapping pairs of rows and ...
- 13.4k
4
votes
2
answers
2k
views
How to compute the rook polynomial of a Ferrers board?
Given a Ferrers board of shape $(b_1,\ldots,b_m)$, we define $r_k$ as number of ways to place $k$ non-attacking rooks (as in Chess). In section 2.4 of Stanley's Enumerative Combinatorics (vol. 1) it's ...
- 1,015
3
votes
2
answers
333
views
Combinatorial design for minimization problem over binary strings
Suppose the cost of a binary string $B$ of length $k$ is the number of $1$s that occur before the last $0$. For example, $1110$ has cost 3 while $0111$ has cost 0. Now suppose you can choose $k$ ...
3
votes
0
answers
627
views
Loopless algorithm for generating permutations (Steinhaus-Johnson-Trotter)
The following is a description of the well-known Steinhaus-Johnson-Trotter algorithm to generate all permutations of an $n$-element ground set using adjacent transpositions.
In fact, it is a loopless ...
- 499
1
vote
2
answers
163
views
Draws from multiple non-disjoint urns
Let $C = \{1,...,n\}$ be a set of $n$ colors. Let $S_1,...,S_k$ be non-empty subsets of $C$, that is, $S_i \subseteq C$ for all $i \in \{1,...,k\}$. It is helpful to think of the $S_i$ as urns with ...
- 83
1
vote
1
answer
94
views
Calculating the values of a generalization of binomials to permutations
let $$\Pi\binom{n}{k}:=\mathrm{card}\left( \left\lbrace \lbrace \Pi_1^n\,\cdots\,\Pi_k^n\rbrace\,|\,0\leq \pi_{r,c}\in\sum_{i=1}^k\Pi_i^n\ni\pi_{r,c}\leq 1\right\rbrace\right)$$ be the number of sets ...
- 13.2k
1
vote
1
answer
196
views
Algorithm for Removing Inverted Elements from a Permutation
I currently have a problem, whose solution requires to remove from a permutation of $\lbrace 1,\ \dots,\ n\rbrace$ those values that are to the left of a smaller one.
My idea was to remove the ...
- 13.2k
1
vote
1
answer
879
views
Generating fixtures for a chess league, with a twist
Hello,
I am in the process of building some software to generate fixtures for a chess league. Which has a little twist which complicates matters. I would like to introduce a constraint. Where by a ...
- 111
1
vote
0
answers
91
views
Generate the nth permutation [closed]
I'm just trying to write a little algorithm. I've got nine objects, so there's 9! permutations. My question is, is there a way of turning a number from 1 to 9! into a permutation?
for example, f(1)=[1,...
- 111