Questions tagged [permutations]
Permutations are arrangements of the numbers $1,\ldots,n$ in an arbitrary order.
229 questions
1
vote
1
answer
54
views
How can I sample from a pseudorandom permutation in constant time?
Is there a function
permute(size, seed, i) -> j
that runs in constant time that computes a pseudorandom permutation? In other words,
...
- 171
0
votes
0
answers
52
views
New Permutation Algorithm?
I believe that I have a new algorithm for touring the permutations of a list.
I have never formally studied Computer Science, so I do not know quite how to present my idea to a computer scientist. I ...
- 1
2
votes
2
answers
91
views
Finding permutations satisfying properties
I'm looking for two permutations $X$ and
$Y$ such that:
$$\begin{align}X^4&=1 \\
Y^3&=1 \\
(Y^2 X)^3&=1 \\
\text{but} \\
(YX^2)^2 &\ne (X^2 Y)^2\end{align}
$$
Do you have any ideas for ...
- 21
1
vote
1
answer
140
views
Incremental generation of random permutations?
I have a case where I need to choose a random subset of a list of know size $n$, but I don't know in advance how many items I will need (i.e. keep picking new indexes until $k$ are found that pass ...
- 156
0
votes
0
answers
28
views
Is direct fatoradics to find the nth lexicographic permutation possible?
I have been using an algorithm from here to find the nth lexicographic permutation of a set.
One part of the algorithm that I have been wondering about is the part where elements are pushed to a new ...
- 111
1
vote
1
answer
76
views
Find rank of vector of length $k$ with elements up to $n$ in graded lexicographic order (grlex)
Let $v = (a_1, a_2, …, a_k)$ be a vector of length $k$, such that $0 \leq a_i < n$. Also let $|v| = a_1 + a_2 + \dots + a_k$ be a total degree of $v$. There is finite number of such vectors.
We can ...
- 133
1
vote
1
answer
97
views
What is the fastest algorithm to determine the nth lexicographic permutation?
Consider inputs n and m, where n is the length of a set, e.g., ...
- 111
1
vote
0
answers
102
views
Back to back Beneš networks
A Beneš network can be used to create any permutation on $2^n$ wires with only $O(n)$ time steps. I have 2 permutations $\pi_0(x),\pi_1(x)$ that I already have the Beneš network for, i.e. the binary ...
- 11
1
vote
1
answer
79
views
Find a set of permutations which minimises the maximum tree-distance between any 2 elements
I have an ordered sequence of $n=2^k$ elements, denoted $a_{1:n}=(a_1,...,a_n)$
The elements are organised in a balanced binary tree, so EG $a_1$ and $a_2$ share a parent, $a_1$ and $a_3$ share a ...
- 131
1
vote
0
answers
53
views
Optimal cycle for minimizing distance between vectors
I faced this problem recently, and am looking for an efficient solution.
We are given $X = (x_1,...,x_n)$ and $Y = (y_1,...,y_n)$ two vectors with ascending coordinates.
Considering a cycle $\sigma = (...
- 11
4
votes
1
answer
732
views
An algorithm for generating a permutation of N numbers ranging from 1 to N with the maximum of smallest neighbouring differences
I encountered this question in a programming contest (New Zealand Informatics Competition 2024, unfortunately no link to the question is available). I was asked to write a program which generates a ...
- 43
0
votes
1
answer
72
views
Calculating nth permutation with repetition efficiently, with variable number of elements
After a long night of Calculating nth permutation without repetition efficiently, with variable number of elements, I realized I actually want permutations with repetition.
Given the ordered set ...
- 151
0
votes
1
answer
62
views
Calculating nth permutation without repetition efficiently, with variable number of elements
I know I can use the factorial number system to calculate ordered permutations of a set efficiently, given a constant length (for example, ...
- 151
3
votes
2
answers
127
views
Generating all unique permutation cycle types and their weights
Consider the set $1, 2, \dots, N$, where $N>1$ is a natural number. In general, there are $N!$ permutations of this list. Let $\sigma$ be one such permutation. We define the tuple $\varphi(\sigma) =...
- 33
0
votes
0
answers
57
views
Counting left to right maxima in permutations in Sage
I'd like to count the number of left to right maxima in a permutation in Sage/Python, i.e. the number of times a number appears in the permutation that is greater than all of the previous numbers. The ...
- 1