Questions tagged [permutations]
The permutations tag has no usage guidance.
168
questions
65
votes
3answers
12k views
In-place algorithm for interleaving an array
You are given an array of $2n$ elements
$$a_1, a_2, \dots, a_n, b_1, b_2, \dots b_n$$
The task is to interleave the array, using an in-place algorithm such that the resulting array looks like
$$...
18
votes
2answers
853 views
What's harder: Shuffling a sorted deck or sorting a shuffled one?
You have an array of $n$ distinct elements. You have access to a comparator (a black box function taking two elements $a$ and $b$ and returning true iff $a < b$) and a truly random source of bits (...
14
votes
1answer
474 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 in ...
13
votes
2answers
241 views
Counting permutations whose elements are not exactly their index ± M
I was recently asked this problem in an algorithmic interview and failed to solve it.
Given two values N and M, you have to count the number of permutations of length N (using numbers from 1 to N) ...
13
votes
2answers
718 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 S}\newcommand\mfm[1]{#1}\def\po{\color{#f63}{\mfm{1}}}\def\pc{\color{#6c0}{\mfm{c}}}\def\pt{\color{#08d}{\mfm{...
11
votes
1answer
1k views
Indexing into a pattern database - Korf's Optimal Rubik's Cube solution
As a fun project, I've been working on a C# implementation of Richard Korf's - Finding Optimal Solutions to Rubik's Cube Using Pattern Databases.
https://www.cs.princeton.edu/courses/archive/fall06/...
9
votes
2answers
910 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 ...
9
votes
2answers
220 views
Find an optimal ordering
I came across this problem and am struggling to find a way to approach it. Any thoughts would be greatly appreciated!
Suppose we are given a matrix $\{-1, 0, 1\}^{n\ \times\ k} $, for example,
...
9
votes
1answer
258 views
Subset sum problem for permutations
Given permutations $g_1,\,\ldots, g_m \in S_n$ of size $n$ and target permutation $g \in S_n$, decide if there exists a subset of $\{g_1,\, \ldots, g_m\}$, which composition in some order (or, ...
9
votes
3answers
1k 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 $A(k-1)...
8
votes
4answers
571 views
Stack Permutation Algorithm
I was recently designing a Forth stack machine. I have an atomic instruction which rotates the top N elements.
For example if the top of the stack is on the left, then say the N=3 rotate instruction ...
8
votes
1answer
553 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 ...
8
votes
2answers
2k 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 ...
7
votes
2answers
621 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.
6
votes
1answer
569 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 $C(i,j)...
6
votes
3answers
132 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
2answers
116 views
Invertible function that randomizes order
I am looking for an invertible discrete function $f:\{0,1,2,\dots,n-1\} \to \{0,1,2,\dots,n-1\}$ for some given integer $n$. I want $f(0),f(1),\dots,f(n-1)$ to return all the integers in range $[0..n)...
6
votes
2answers
171 views
Algorithm to compose identity from a set of permutations
Given a subset P of all the possible permutations of a fixed set of elements, is there a non-exponential or optimized algorithm for computing the smallest composition of P that yields the identity ...
6
votes
1answer
112 views
Index matching algorithm without hash-based data structures?
I am programming in C, so I do not want to implement a hash-based datastructure such as a hashset or hashmap/dictionary. However, I need to solve the following task in linear time.
Given two arrays $...
6
votes
1answer
160 views
Chernoff-Hoeffding bounds for the number of nonzeros in a submatrix
Consider a $n \times n$ matrix $A$ with $k$ nonzero entries. Assume every row and every column of $A$ has at most $\sqrt{k}$ nonzeros. Permute uniformly at random the rows and the columns of $A$. ...
6
votes
1answer
196 views
Error correcting permutation code
Let's say you have $n$ symbols. You can encode a $\log_2(n!)$-bit message by permutating the symbols. I will call this a permutation code (if you have seen this concept before, I would love to see a ...
6
votes
0answers
232 views
Is greedy minimax permutation rejecting sorting optimal?
I sketch an impractical, theoretical comparison sort.
Initialize a list of all $n!$ permutations of size $n$.
For each possible pair of indices $i, j$, count how many permutations would get rejected ...
5
votes
3answers
4k views
What's a uniform shuffle?
What does it mean exactly a "uniform shuffle" algorithm ?
Is this method considered a uniform shuffle ?
...
5
votes
3answers
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 ...
5
votes
2answers
117 views
Chernoff-like Concentration Bounds on Permutations
Suppose I have $n$ balls. Among them, there are $m \leq n$ black balls and the other $n - m$ balls are white. Fix a random permutation $\pi$ over these balls and denote by $Y_i$ the number of black ...
5
votes
1answer
93 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$...
5
votes
1answer
326 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$.
...
5
votes
2answers
158 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 ...
5
votes
1answer
142 views
Permutation of words that have matched parentheses
Let $L$ denote the (context-free) language of matched parentheses over the alphabet $\Sigma$. Consider the following problem:
Input: words $x_1,\dots,x_n \in \Sigma^*$
Question: does there exist a ...
5
votes
1answer
80 views
Applying a permutation on a sequence with multiplication
We are given a sequence of $n$ numbers called $\alpha$ and an arbitrary number $x$. Give an algorithm to find a permutation $\pi$ of size $n$ such that $\sum_{i=1}^n{\alpha_i.\pi_i} = x$ or tell if ...
5
votes
0answers
962 views
What is the intuition behind Heap's Algorithm?
I am trying to get an intuition for Heap's Algorithm which is used to generate permutations of a given set.
What I can't understand is why if n is even the letter swapped is i and when n is odd the ...
4
votes
3answers
2k 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 ...
4
votes
2answers
11k views
Using backtracking to find all possible permutations in a string
I came across this algorithm in a book, and have been struggling to understand the basic idea. The books says it uses backtracking to print all possible permutations of the characters in a string. In ...
4
votes
2answers
422 views
Mathematically determine if two strings are permutations of each other
I've come across many coding exercises that require me to determine whether or not two strings are permutations of each other and I've repeatedly wondered if it would be possible to convert each ...
4
votes
1answer
900 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 ...
4
votes
4answers
3k 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 would ...
4
votes
2answers
67 views
Algorithm for factoring elements of permutation groups?
You can solve a Rubik's cube by factoring its permutation into a sequence of "elementary" permutations (a subset of permutations that is sufficient to construct every other permutation in the group). ...
4
votes
1answer
104 views
Indexing Edge Permutations for the Rubik's Cube
I'm working on a Rubik's Cube solver that implements Korf's algorithm, as published in his 1997 paper, Finding Optimal Solutions to Rubik's Cube Using Pattern Databases. His method involves creating ...
4
votes
1answer
32 views
# of permutations satisfying special inequalties of each element0
Recently I was solving a counting problem, which needed this subproblem to be solved:
Given integers $n$ and $t$ (where $1 \le t \le n$) and a decreasing function $f$, find the number of permutations ...
4
votes
0answers
189 views
Data structures for ordering noisy data
In a certain robotics application, I encountered a problem in which we need to determine the order of positions of several robots on $\mathbb{R}$. Each measurement that we take of robot positions is ...
4
votes
0answers
151 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 ...
3
votes
2answers
611 views
Deriving the average number of inversions across all permutations
In the answer by Raphael to the question "Is there a system behind the magic of algorithm analysis?", there is an equation:
$$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \...
3
votes
2answers
252 views
Shuffling a file on disk using $O(\log n)$ memory
How do you shuffle the bytes in a file (bytes for simplicity) on disk with a small, $O(\log n)$, amount of memory and preferably in-place?
If the file had size $2^m$, then we can first split the file ...
3
votes
1answer
78 views
existence of a permutation that satisfies order-constraints
I would like to know if there is a simple algorithm for checking the existence of a permutation that satisfies a number of order-constraints.
For example, suppose we have a set (1, 2, 3, 4, 5) and a ...
3
votes
1answer
388 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) $f(x,y)...
3
votes
1answer
2k 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)$ ...
3
votes
4answers
195 views
Optimization problem where penalty is sensitive to permutation
Say, I have the situation where I am looking into all the possibilities to obtain a value of e.g. 20 (exactly) by taking all possible combinations of sums using values from 1 to 5. While doing this, I ...
3
votes
1answer
465 views
Lexicographically k-th small string
The origin problem is here. Now it is deleted.
Suppose I have 3 'available' copies of a, 2 of b, 3 of ...
3
votes
3answers
300 views
Contained optimal combination of inputs
I have 100 football (soccer) players, each with an "expected score" (higher is better) and price (e.g. 4300 dollars). I want to select the optimal combination of players with the highest combined ...
3
votes
1answer
315 views
In-place “clumping-by-color” algorithm faster than sorting by color?
I don't know what to call this, so I'm calling it "clumping by color".
Suppose I have an array of length $n$
where each of the items has one of $m$ "colors". I'd like to permute the elements so that ...
