The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
62 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
84 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 ...
4
votes
1answer
39 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
34 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
270 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 ...
2
votes
2answers
73 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
559 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
101 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
343 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
278 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
145 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
65 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
238 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
295 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
362 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
179 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
87 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
175 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
75 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
412 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 ...