The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [permutations]

The tag has no usage guidance.

153 questions
Filter by
Sorted by
Tagged with
816 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 swap ...
3k views

What's a uniform shuffle?

What does it mean exactly a "uniform shuffle" algorithm ? Is this method considered a uniform shuffle ? ...
133 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 ...
164 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 ...
504 views

276 views

480 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 ...
261 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. It'...
210 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, ...
2k 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 ...
75 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$.
105 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 In ...
91 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 ...
146 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, \pi, \cdots, \pi[n]$. The output should be the parity of ...
161 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(...
273 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$. ...
156 views

Word tiling, where you must use each tile exactly once

Given words $w_1,\ldots,w_n$ in binary alphabet and another word $w$, decide if $w$ can be written as a product $w = w_{i_1} \cdots w_{i_n}$ (in the monoid $\{0,1\}^\ast$) for some permutation of ...
337 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, ...
543 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.
780 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 ...
153 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, ...
467 views

313 views

Permuting natural numbers

We have two integers $z, k$ We form a sequence now of first z natural numbers. i.e. $1, 2, 3, 4, \ldots z$. Now we have to find total number of permutations of this sequence such that the sum of ...
90 views

Rearrange a sequence of real numbers to satisfy polynomial inequalities

Assume we fix a degree $d$ polynomials $f$ of $k$ variables. (If it helps, let $t$ be the number of terms in $f$). Consider a list of real numbers $a_1,\ldots,a_n$, does there exist a permutation $\pi$...
I have come across the following problem. You have $N$ registers, numbered $1,2,\dots, N$, each of which can hold an integer value. You are given the initial values of the registers, which have the ...