Questions tagged [permutations]
The permutations tag has no usage guidance.
73
questions
0
votes
0answers
111 views
“Partial” invert a one-way permutation
First of all, to my best understanding, traditionally, if $f$ is a one-way function that maps a length $l$ bit string to another length $l$ bit string (i.e., $f:\{0,1\}^l\rightarrow\{0,1\}^l$), then ...
3
votes
1answer
111 views
Effect of constraints Density on the hardness of Betweness problem
Betweeness problem is well known NP-complete permutation problem. Given a family $M$ of triples $(a_i, a_j, a_k)$, the problem is to decide whether a permutation $\Phi$ of elements $a_1, a_2, ..., a_n$...
-1
votes
1answer
50 views
Algorithm for calculating substitution combination with ordering
I need to calculate the combinations of elements with a substitution element.
For example for elements [A,B] if the substitution is X the results should be ...
3
votes
2answers
503 views
Finding the identity with permutation chains
I have the following problem: I'm given a list of size $K$ of random integer permutations of $[1..n]$, named $P_1$ to $P_K$, and an additional random permutation $Q$.
How hard is to find a sequence $...
-3
votes
1answer
275 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)...
4
votes
2answers
173 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 ...
2
votes
1answer
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 ...
17
votes
1answer
720 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 ...
3
votes
2answers
2k views
Counting length-k increasing subsequences in a permutation
(Originally posted on Math.SE.)
Let $f$ be a permutation on $n$ letters. I want to count the number of $k$-long increasing subsequences quickly.
One approach is to first use divide and conquer to ...
2
votes
0answers
132 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 ...
9
votes
2answers
390 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 ...
8
votes
1answer
927 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] ...
15
votes
1answer
362 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 ...
5
votes
1answer
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 ...
27
votes
1answer
699 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
...
7
votes
4answers
596 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 ...
1
vote
1answer
257 views
finding permutations which fulfills given conditions
Let $K$ be an ordered finite set. Consider some function $g:K^2 \rightarrow R$ such that
$g(k1,k1') + g(k2,k2') \ge g(k1,k2') + g(k2,k1')$
where $k1 > k2$ (in order A1) and $k1&#...
2
votes
1answer
149 views
List the $k$-faces of an $n$-dimensional simplex
Suppose you are given an $n$-dimensional simplex
S = [ 0 1 ... n ]
which for the time being we think of as an ascending array of numbers from $0$ to $n$. Given $...
6
votes
0answers
208 views
Lowerbounds for in-situ permutation
What is the best known lowerbound for the worst case complexity of in-situ permutation (also called in-place rearrangement)? Has there been any reported progress after the 1970's article by Knuth (...
17
votes
2answers
762 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 ...
0
votes
1answer
637 views
How to compute ROOK Polynomials for NxM Matrices [closed]
How to compute ROOK Polynomials for NxM Matrices for k objects ?
16
votes
6answers
3k 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 ...
6
votes
0answers
149 views
Constraint Satisfaction Problem: Choosing real numbers with variance in a certain range
I have a set of n real numbers. I want to repeatedly choose subsets of k elements such that the variance of these k numbers falls within some specified range, r = [l, u]. Moreover I want to do this ...
