Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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,...
Elliott's user avatar
  • 111
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 ...
Manfred Weis's user avatar
  • 13.2k
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 ...
Torsten Mütze's user avatar
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 ...
Wolfgang's user avatar
  • 13.4k
9 votes
0 answers
535 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 $...
Artur Riazanov's user avatar
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 ...
Manfred Weis's user avatar
  • 13.2k
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 ...
Bryce Sandlund's user avatar
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,\...
Jesko Hüttenhain's user avatar
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,...
Jacques Carette's user avatar
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$ ...
Rodrigo Castro's user avatar
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 ...
Mathias's user avatar
  • 83
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 ...
froogz3301's user avatar
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 ...
didest's user avatar
  • 1,015
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 ...
Michael Lugo's user avatar