Questions tagged [permutations]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
350 views

Distance-preserving permutations

In the scope of my scheduling research, the question has been raised on whether distance-preserving permutations can be constructed easily. Suppose that our domain is the set of natural numbers up ...
4
votes
2answers
344 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 ...
2
votes
1answer
77 views

Algorithm to generate integer sets fulfills restrictions

I'm trying to solve the following problem. Input positive integers $v$, $b$ and $\ell$. ($\ell\leq v\leq b\ell$.) Output A list $S_1, \dots, S_k$ of all possible integer multisets (a ...
1
vote
0answers
53 views

Canonical permutation faster than O(n)

Given a set of permutations $P$ of size $n$, is it possible to create a data structure that, given a sequence $s$, returns $p \cdot s$ where $p \in P$ such that $p \cdot s$ is canonical wrt. $\{\,q \...
2
votes
1answer
50 views

Counting permutations whose elements are not exactly their index ± 1

This is a special case of the question: Counting permutations whose elements are not exactly their index ± M The $M=0$ case has already been solved, but no one was sure how to work out the non-...
1
vote
1answer
517 views

Can we count the number of inversions in time $\mathcal{O}(n)$?

It is possible to find the total number of inversions by $\mathcal{O}(n\log{}n)$ running time (extension of merge-sort algorithm for example). Is there more asymptotically efficient way to do it? $\...
1
vote
1answer
27 views

Gray-like code with maximum value <= maximum value of original symbol

I want to iterate through the numbers $0,1,2,\dots,n-1$ in some order, where each number in the sequence differs by only one bit from the previous bit. I'm going to be using each number as an index ...
1
vote
3answers
503 views

Finding longest balanced parentheses using $n$ smaller strings

Given $n$ strings consisting only of '$($' and '$)$', how one can compute the length of the longest string that can be built by concatenating a subset of these strings in some order such that the ...
13
votes
2answers
211 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) ...
1
vote
1answer
971 views

Sort array with minimum swaps

Given an array, I need to sort the array (if not already sorted) in either decreasing or increasing order so that number of swaps are minimized. I was thinking of first determining whether it is ...
3
votes
4answers
172 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 ...
0
votes
1answer
161 views

Most Efficient Way to List All $n$-bit Permutations

Suppose we are tasked with expressing a randomized list of all numbers up to but excluding $2^n$ (ie. a random list of all n-bit numbers). What are some efficient ways to do such a listing using as ...
1
vote
0answers
104 views

Optimal permutation of matrix rows and columns

Let $M$ be a square matrix and $S(M) = \sum_{i<j} m_{i,j}$ the sum of the elements in the upper triangular part of $M$. Is there an efficient algorithm to find a permutation matrix $A$ that ...
2
votes
0answers
16 views

permuting points for range compression between subsets

For $k = 0,\ldots, K - 1$, $M_k$ is a subset of $\{0, \ldots, N - 1\}$, and the subsets $M_k$ are not necessarily disjoint. I want to find a permutation on $\{0, \ldots, N - 1\}$ such that the range ...
1
vote
2answers
265 views

Enumerating the List of `nPr` (n Permute r) objects [closed]

I have been using MATLAB for a particular project, and have seemed to find a function that may or may not exist. This question isn't MATLAB specific, more algorithm specific. I have a list of 12 ...
1
vote
1answer
140 views

Finding Permutations with Exclusions

Recently, I was given a puzzle by a friend of mine, which has 6 pieces. Giddy to try it out, I took it apart without batting an eye to follow what I was removing or moving or sliding. I've been ...
2
votes
0answers
134 views

Correctness proof of the algoritm to generate permutations in lexicographic order

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place. Find the largest index k such that a[k] < a[k + 1]. ...
0
votes
0answers
77 views

no of ways to fill a row (1xN grid) with a set of 1D bars with some constraints?

Given a row of length N, and a set of 1D bars having lengths A[1...M], how many ways I can fill the row? A is an integer array, the bars are having dimensions $\{1\times A_1,1\times A_1,1\times A_1,....
3
votes
3answers
245 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 ...
2
votes
1answer
28 views

Print to video permutations

You want to print vectors with n elements, where: the first element can have the values: e1.1, e1.2, e1.2; the second element can assume the values: e2.1, e2.2, e2.3; ...; ...; the nth element can ...
-1
votes
1answer
53 views

Can randomization be proven?

There exists a collection c where c = {1, 2, 3} and a randomization of c, ...
2
votes
1answer
97 views

Computing $n$th lexicographically smallest permutation of length up to $k$

I wonder how to tackle such problem, to be more specific: Given a set and an integer $k$, find the $n$th lexicographically smallest permutation (with repetitions allowed) of the set. We will say ...
0
votes
0answers
71 views

Yarn Resource Allocation

Say for an example,i have Color codes that are : A , B , C I want to repeat this colors so i ll put them as : 5A , 10B , 10C = 25 So now A will repeat 5 times ,B will repeat 10 times and C will repeat ...
3
votes
1answer
389 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
1answer
813 views

How to solve an ILP problem with conditions in an objective function?

I have came accross this link. I have an integer linear programming (ILP) problem $$\max_{(x_1, x_2,\ldots, x_n)}\sum_{i=1}^n x_i\cdot f(x_i),$$ $$\text{subject to } \begin{cases} ..., &(1)\\ L≤...
4
votes
1answer
31 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 ...
3
votes
2answers
468 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
1answer
76 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 ...
6
votes
1answer
174 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 ...
2
votes
1answer
106 views

Computing counts of combinations (?)

I'm not sure what terminology to use. Here is some input: John has items: A B D Peter has items: A C D And I want to produce such a table, that would count the #...
2
votes
1answer
520 views

Polynomial time solution for bipartite matching

Inspired by this StackOverflow question, I am wondering if there is an efficient algorithm for the following problem: Assume $n$ items and $n$ boxes, with all boxes numbered numerically and all ...
5
votes
0answers
738 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 ...
2
votes
1answer
111 views

Minimum number of transpositions

Let's have two permutations $A$ and $B$ of $n$ numbers. What is the minimal number $m$ of transpositions to transform $A$ to B in the worst case? After analysing some algorithms my guess is that $m \...
6
votes
0answers
222 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 ...
2
votes
1answer
766 views

Need explanation of Heap's Algorithm

Okay I am trying to understand the Heap's Algorithm from the original research paper published by B.R Heap. The most confusing aspect I found that while Heap says that the example described on the ...
2
votes
1answer
82 views

How can I reduce a product of transpositions?

I'm looking for an algorithm to solve the following task: Input: a set $T$ of transpositions; a permutation $\pi$ expressed as a product of transpositions from $T$ Desired output: express $\pi$ as ...
2
votes
1answer
231 views

Permutation on matrix to fill main diagonal with non-zero values

I am currently working on some sparse non-singular matrices. One of the algorithms I use requires divisions by the elements on the main diagonal so I have to ensure that my main diagonal is filled ...
3
votes
0answers
86 views

How to determine Isomorphism of Non-Symmetric Matrix when Permutation-Set is given?

Consider, two $m \times n$ matrices $A, B$ such that there is a permutation $\kappa$ that such that such that $A^{\kappa}=B$ (Wielandt's notation), i.e. $A, B$ are isomorphic but not equal. Since,...
2
votes
1answer
64 views

Transitivity of concat comparison

I am trying to solve the problem of finding the permutation, amongst all possible ones, of an array of strings, where the concatenation of them compares smallest lexicographically. I solve it with an ...
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/...
6
votes
2answers
101 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)...
1
vote
0answers
38 views

Clustering of matrices

I have a matrix of n lines and T columns, containing only 0's or 1's. I would like to make permutations of lines (and lines only) to make the largest submatrix of 1's possible (i.e. i want to find ...
0
votes
1answer
46 views

Restricting possible permutations in Graph Isomorphism problem

Given a $2n$ vertex undirected graph whose vertices are partitioned arbitrarily in pairs to say WLOG $(1,2)$, $(3,4)$, $\dots$, $(2n-1,2n)$. Call these vertices pairs as super vertices. Call two such ...
1
vote
1answer
66 views

restricted sub-permutations check

I am solving the following problem, motived by combinatorial optimization sampling proces. I have restriction (0,1) matrix to restrict which item (column index) can be on current position (row index) ...
3
votes
2answers
224 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 ...
4
votes
0answers
187 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 ...
2
votes
1answer
28 views

Lower bound for comparison algorithm - checking whether permutation is odd or even

I consider problem: proving lower bound for comparison algorithm that check whether permutation is odd or even. I know that this bound is $\Omega(n\lg n)$. Could you give me a clue ?
4
votes
1answer
788 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 ...
5
votes
3answers
3k views

What's a uniform shuffle?

What does it mean exactly a "uniform shuffle" algorithm ? Is this method considered a uniform shuffle ? ...
1
vote
3answers
133 views

probablistic procedure to permutate array

input : $array[1...n]$ output: permutated array Our algorithm should be probablistic and complexity should be $O(n)$. Could you give me hint ? My weakness is probability theory and it is why I have ...