The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
31 views

Optimizing Permutation Algorithm

I'm looking at Permutations Algorithm, the complexity of this algorithm is pretty high O(N*N!). The algorithm is based on this observations. GeneratePermutations("ABC")= [ABC; ACB; BAC ; BCA ; CBA ...
-1
votes
1answer
9 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 ...
0
votes
0answers
10 views

Translate Haskell code into Standard ML (permutation with repetition) [closed]

I am writing a code for the permutation with repetition for n elements drawn from choice of k values. So the cardinality of my resulting set should have n^k elements. In Haskell, it is fairly easy. ...
4
votes
1answer
65 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
votes
1answer
47 views

Number of ways to form N digit number from M unique digits [closed]

Eg. if M=3{1,2,3} and N=5 then Ans=150{12333, 12322, 12311, 11123, 11231, 11223, ....} You must use each of M digits atleast once and N>=M always. We have to find the total number of N-digit ...
0
votes
1answer
49 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 ...
1
vote
1answer
20 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 O(N log N) or worse solutions, but I'm looking for one that runs in O(N), or a proof that none exist.
0
votes
1answer
55 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
34 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
81 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
48 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) ...
0
votes
0answers
26 views

The time complexity to find the largest rising left-neighbourhood for every element in an sequence? [duplicate]

For example, in sequence 3, 4, 3, 2, 4, the largest rising left-neighbourhood for 2 is 4 3 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
78 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
123 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
47 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
41 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
347 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
78 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
919 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
121 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
357 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
286 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
158 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
299 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
324 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
374 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
222 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
115 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
196 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
571 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 ...