The permutations tag has no wiki summary.
4
votes
1answer
99 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
53 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
53 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)$ ...
7
votes
2answers
151 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
293 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
132 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
49 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
124 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
60 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
189 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 ...
