# Tagged Questions

The tag has no usage guidance.

1answer
27 views

0answers
31 views

### Clustering of matrices

I have a matrix of n lines and T columns, containing only 0's or 1's. I would like to make permutations of lines (and lines only) to make the largest submatrix of 1's possible (i.e. i want to find ...
1answer
37 views

### Restricting possible permutations in Graph Isomorphism problem

Given a $2n$ vertex undirected graph whose vertices are partitioned arbitrarily in pairs to say WLOG $(1,2)$, $(3,4)$, $\dots$, $(2n-1,2n)$. Call these vertices pairs as super vertices. Call two such ...
1answer
21 views

### restricted sub-permutations check

I am solving the following problem, motived by combinatorial optimization sampling proces. I have restriction (0,1) matrix to restrict which item (column index) can be on current position (row index) ...
2answers
97 views

### Shuffling a file on disk using $O(\log n)$ memory

How do you shuffle the bytes in a file (bytes for simplicity) on disk with a small, $O(\log n)$, amount of memory and preferably in-place? If the file had size $2^m$, then we can first split the file ...
0answers
156 views

### Data structures for ordering noisy data

In a certain robotics application, I encountered a problem in which we need to determine the order of positions of several robots on $\mathbb{R}$. Each measurement that we take of robot positions is ...
1answer
20 views

### Lower bound for comparison algorithm - checking whether permutation is odd or even

I consider problem: proving lower bound for comparison algorithm that check whether permutation is odd or even. I know that this bound is $\Omega(n\lg n)$. Could you give me a clue ?
0answers
18 views

### Bias for modified knuth shuffle? [duplicate]

The Knuth shuffle, also known in its original form as Fisher-Yates-shuffle, generates a random permutation, considered unbiased. I.e. all permutations are supposedly equally likely. The algorithm is ...
0answers
24 views

### Explanation of probability expression in finding maximum algorithm

On section 1.2.10, algorithm M, in The art of computer programming Vol. 1, there's an expression for finding the probability that the step number A is executed $k$ times. The expression reads:  p_{...
1answer
155 views

### Minimizing inversions in an array with a single swap

This was asked in the (very) recently concluded Hackerrank Worldcup. Paraphrased: Given a permutation $a$ of integers from $1$ to $N$, how can I minimize the number of inversions by a single ...
3answers
117 views

### probablistic procedure to permutate array

input : $array[1...n]$ output: permutated array Our algorithm should be probablistic and complexity should be $O(n)$. Could you give me hint ? My weakness is probability theory and it is why I have ...
1answer
75 views

### Random uniform sampling of position restricted permutations

Is there any efficient algorithm which is able to generate nearly uniform samples of permutations in case of position restrictions? Consider $N \times N$ restriction matrices $R$, that is matrices ...
1answer
488 views

1answer
68 views

1answer
190 views

### Searching the space of permutations

I'm given n objects, and a set of n permutations of these n objects (out of n! total permutations). There is a true underlying permutation, which I know is one among the set of n permutations, but I ...
1answer
225 views

### How many permutations in a trainset?

If I have the following pieces to a train set: (12) Curve (4) Straight Such as this train set. I'm looking for an algorithm (to which I can write a program) that creates/lists all permutations. ...
1answer
158 views

### Computing a Sequence of People Entering and Leaving a Room

I've been working on a problem for my Algorithms class, but I've found myself stuck. The prompt is as follows. You start with an empty room and a group of n people waiting outside. At each step, ...
3answers
555 views

### How should I design a hash table where all the keys are permutations?

I need to create a hash table to store values for (possibly all) permutations of 123456789, which is exactly 362 880 keys. Given that I know how all the keys look ...
1answer
40 views

### Probability of having a log(n) length monotone subsequence in a random permutation of {1,…,n}

How can I compute the probability of having a $\log(n)$ length monotone consecutive subsequence in a random permutation of $\{1,...,n\}$. I wish to upperbound it with $1/n$.
2answers
73 views

### Calculating the number of unique BST generatable from n keys, why is my number so large

I want to find the number of distinct BSTs I can get with 3 unique keys (i.e. 1, 2, 3) Here's my solution: In case 1, we have each node have possibility, 3, 2, 1, respectively, so 3*2*1 = 6 ways ...
3answers
73 views

### How can I keep track of the state of a sequence after rotating parts of it multiple times?

Given a sorted array 1 2 3 4 5 6 7 8 and an operation that takes the N-th element out the array and puts it in front (or rotates the first N elements to the ...
0answers
74 views

### Computing parity of a permutation in a streaming-fashion way

I'm looking for a one-pass algorithm which computes parity of a permutation. I assume that an input permutation is given by stream $\pi[1], \pi[2], \cdots, \pi[n]$. The output should be the parity of ...
1answer
53 views

### How do you come up with greedy algorithm for deadline scheduling when comparing x_subscript(i) and y_subscript(k)?

So there are two boxing teams, my team A and the opposing team B, each with m boxers. Based on the player's ranking of skill, x_subscript(i) being the ranking for ith boxer for team A and y_subscript(...
1answer
145 views

### Random permutations by probability matrix

I have the following problem: I need to generate $\ell$ random permutations each of length $n$ from a list of $m$ elements ($m \ge n$) by a predefined probability matrix $P$ of size $n$ x $m$. ...
1answer
131 views

### how to verify permutation generated in constant amortized time?

Here is an algorithm that generates the next permutation in lexicographic order, changing the given permutation in-place: Find the largest index k such that a[k] < a[k+1]. If no such index exists,...
2answers
181 views

### Given a permutation of 0..N-1, determine the index of that permutation in the lexicographic ordering of all permutations of 0..N-1, in linear time

There are various $\mathcal O(n \log n)$ or worse solutions, but I'm looking for one that runs in $\mathcal O(n)$, or a proof that none exist.
1answer
126 views

### Permutations in an k-sorted array

Definition of $k$-sorted array: An array in which an element is at-most $k$ places away from its sorted order. I have a question in my Algorithms assignment which asks to prove the lower bound to ...
0answers
79 views

### Iterative permutations, but favoring swaps of early elements

I'm familiar with the Steinhausâ€“Johnsonâ€“Trotter algorithm, which allows for the iterative yielding of permutations of a sequence by performing a single swap per iteration. It has the behavior, ...
1answer
133 views