The tag has no wiki summary.

learn more… | top users | synonyms

11
votes
2answers
283 views

Efficient algorithm to generate two diffuse, deranged permutations of a multiset at random

Background $\newcommand\ms[1]{\mathsf #1}\def\msD{\ms D}\def\msS{\ms S}\def\mfS{\mathfrak ...
7
votes
1answer
130 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 ...
2
votes
1answer
112 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. ...
2
votes
1answer
80 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, ...
3
votes
3answers
264 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 ...
1
vote
1answer
33 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$.
1
vote
2answers
40 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 ...
0
votes
3answers
60 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 ...
4
votes
0answers
55 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 ...
-1
votes
1answer
24 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 ...
4
votes
1answer
83 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$. ...
1
vote
1answer
80 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 ...
5
votes
2answers
69 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.
1
vote
1answer
90 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 ...
1
vote
0answers
47 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, ...
5
votes
1answer
102 views

How hard is this constrained $n$-rooks problem?

I asked this over on math.stackexchange.com, then I found out about this forum. Suppose you have an $(n\times n)$-chessboard, together with a constraining function $C : n \times n \to 2$ where ...
0
votes
2answers
61 views

Finding the kth element of a permutation [closed]

Is there a way to generate a random permutation of the numbers 1 to N such that I can find the k-th element of the permuted list without needing to either 1) store the entire permuted list, or 2) ...
1
vote
0answers
28 views

Conjecture about a matrix column swapping challenge problem

So here is the challenge problem statement: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1512 Basically, given a 0/1 matrix, you ...
1
vote
1answer
83 views

Permute the subintervals of an interval partition to most closely align with a model partition

You are given two things: A fixed initial 'model' partition of an interval, e.g. I------I---I-----I-------I----... where each ...
2
votes
1answer
229 views

How can we minimize the total distance of cross pairs in an array

Suppose we had 2 arrays of the same size with positive numbers and we wanted to pair up the elements of each array such that the total difference between the pairs is minimized. The first thought ...
3
votes
1answer
52 views

A canonical representative, for this equivalence relation on matrices

This question is inspired by Constructing inequivalent binary matrices. Define the equivalence relation $\sim$ as follows: If $M,N$ are two $8\times 8$ binary matrices (all elements are $0$ or $1$), ...
1
vote
0answers
42 views

Quadratic programming problem involving permutation matrices

Does anyone know a good algorithm for quickly finding an approximate solution to the following problem? Given two square matrices $A$ and $B$, minimize $\| P A P^\top - B \|$ over all permutation ...
3
votes
3answers
409 views

Number of ways to fill a 2xN grid with M colors

This question was asked in the onsite regionals for ACM ICPC 2013 at Amritapuri. In short, the question asked to find the number of ways to fill a $ 2\times N$ grid with $M$ colors such that no two ...
3
votes
2answers
103 views

Is there a proof of the recursive algorithm for generating all permutations of a sequence?

For clarity, I attach below a concise implementation of the algorithm in Python. I understand that it checks all possible element swaps, but I don't see how that necessarily means that all possible ...
2
votes
2answers
115 views

Prove this language is decidable? [closed]

$L$ is defined over the alphabet $\{a,b\}$ and it's decidable. The language is $\mathrm{perm}(L)$ which is the set of all permutations of all words in $L$. So far my proof is the following: ...
4
votes
2answers
1k views

Rearrange an array using swap with 0

This is a Google interview question. I got it from a website. You have two arrays source and target, containing two permutations of the numbers [0..n-1]. You ...
0
votes
1answer
138 views

Number of permutation cycles in matrix transposition

I am trying to solve a problem on Sphere Online Judge (SPOJ) link to which is: http://www.spoj.com/problems/TRANSP/ The matrix can be thought of as a permutation and its transposition as another ...
2
votes
1answer
362 views

Count number of special onto functions

We define an onto function from $[n] \times [n]$ to $[n-2] \cup \{0\}$ as follows, where $[n] = \{1,2,3,\ldots ,n\}$, $$f : [n] \times [n] \rightarrow [n-2] \cup \{0\}.$$ 1) $f(x,x) = 0$. 2) ...
2
votes
1answer
288 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 ...
4
votes
1answer
168 views

Sorting Problem

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 ...
2
votes
0answers
68 views

Collisions of a compression function

I tried posting this in the math forum but I didn't get any responses. I was hoping someone could give me some advice for how to approach the following problem. If $n$ is a positive integer, let ...
3
votes
1answer
453 views

Are permutations of context-free languages context-free?

Given a context-free language $L$, define the language $p(L)$ as containing all permutations of strings in $L$ (i.e. all strings in $L$ such that the order of symbols is not important). Is $p(L)$ ...
8
votes
2answers
386 views

Is there a “sorting” algorithm which returns a random permutation when using a coin-flip comparator?

Inspired by this question in which the asker wants to know if the running time changes when the comparator used in a standard search algorithm is replaced by a fair coin-flip, and also Microsoft's ...
12
votes
1answer
386 views

Interesting problem on sorting

Given a tube with numbered balls (random). The tube has holes to remove a ball. Consider the following steps for one operation: You can pick one or more balls from the holes and remember the order ...
1
vote
2answers
261 views

Best random permutation employing only one random number

The ideal random permutation algorithm of Fisher and Yates (Algorithm P in Knuth vol.2) for a sequence of $n$ objects requires $n-1$ random numbers. In some card games one first does a "cut" and ...
1
vote
1answer
150 views

A puzzle in Permutation

There are two stacks A and B. A : a,b,c,d ('a' is on top and 'd' is at the bottom of the stack) B : (empty) There are two rules. ...
8
votes
2answers
236 views

Finding number of smaller elements for each element in an array efficiently

I am stuck on this problem: Given an array $A$ of the first $n$ natural numbers randomly permuted, an array $B$ is constructed, such that $B(k)$ is the number of elements from $A(1)$ to ...
5
votes
1answer
80 views

Maximal derangements

When one shuffles playing cards, the goal is evidently to achieve a possibly big derangement of a given deck. For manual shuffling there are terms like inshuffle, outshuffle etc. I like to know ...
6
votes
1answer
757 views

Alternative to Hamming distance for permutations

I have two strings, where one is a permutation of the other. I was wondering if there is an alternative to Hamming distance where instead of finding the minimum number of substitutions required, it ...