Questions tagged [permutations]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
63 views

number of queries to recover the permutation

Imagine this game. I pick a permutation $p$ of $1..n$ and give you an oracle. When the oracle is queried with any sequence of $n$ numbers $\in 1..n$, it masks each number by applying some unknown ...
1
vote
1answer
250 views

Black-box combinatorial optimization problem over permutations

I am solving general black-box optimization problems like: x*: f(x) -> min, where x are permutations of length N (N = 50 for example, so brute force search is not possible). Objective function f(x) is ...
1
vote
1answer
79 views

Maximizing the sum of adjacent pairs of elements

I encountered the following interesting problem on stackoverflow: Given numbers $a(1)<\cdots<a(n)$, find a permutation $\pi$ that maximizes $$\sum_{i=1}^{n-1} a(\pi(i)) a(\pi(i+1)).$$ The ...
2
votes
1answer
42 views

Counting number of permutations respecting partial order

Suppose that we have an array $A$ of $n$ elements with some partial order known, e.g. for example as a $n\times n$ matrix containing $c_{ij} \in \{-1, 0, 1\}$ where $0$ represents unknown and $-1, 1$ ...
2
votes
0answers
219 views

How many similar binary search trees are made from different permutations?

If I have numbers ranging from 1 to n, and I generate all the permutations of these numbers. Now, I create Binary search tree from these permutations. For a value n i want to know how many BSTs would ...
0
votes
1answer
125 views

Minimizing the SUM algorithm

We are given $2n$ positive integers $a_1,a_2\ldots,a_n$ and and $$b_1,b_2,\ldots,b_n$$ as input. The question is to find a permutation $O$ on $\{1,2,\ldots,n\}$ that minimizes $$\sum_{i=1}^n \left(...
2
votes
2answers
63 views

Indexing a random permutation

I am curious if there exists a method for specifying a permutation $F_k: X \to X$ with a small(ish) $k$. Something that comes very close to my goal is a block cipher, say AES. But block ciphers have ...
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 ...
1
vote
1answer
198 views

Determine if a string is a permutation of another string efficiently [duplicate]

Given two strings of the same length, determine if they are permutations of each other. I can come up with two solutions, one in O(n log n) time with O(1) extra space, and one in O(n) time with O(n) ...
0
votes
0answers
43 views

Efficient permutation of given ranking that preserves given distance

Ranked Biased Overlap (RBO) is a metric for comparing two rankings and is used when the sizes of the given rankings are different and/or the elements that they carry are not the same. Ranked Biased ...
0
votes
0answers
385 views

Interleaving first and second half of an array of even length in place

If A is an array with the following elements: $$ a_1,a_2,...,a_n,b_1,b_2,...,b_n $$ How to shuffle A to form: $$ a_1,b_1,a_2,b_2,...,a_n,b_n $$ with minimal swaps and using no additional space? I ...
1
vote
1answer
71 views

Finding a subset of triplets of digits 0-9 such that each digit occurs 40 times in each position in the triplets

I am trying to generate a list of digit triplets to specify stimuli in an auditory (speech-in-noise) perception experiment. Each triplet has to have three different digits (i.e., no repetition within ...
1
vote
1answer
72 views

How to find number of permutations of 1-N length, each [1-N] with k values

This imaginary problem involves a vector of length 5, with each value to be selected from a unique range of values. A real-world example might include 5 different single-digit combination locks. ...
1
vote
1answer
817 views

Space and time complexity of balanced parentheses enumeration algorithm

Consider the following recursive algorithm for printing all balanced strings with $n$ left and right parentheses. It is called with prefix = $\epsilon$ (the empty string): A(prefix): If prefix ...
0
votes
1answer
220 views

How to encode a sequence of non-decreasing integers with an integer without redundancy, loops, and recursions

How to encode a sequence of n non-decreasing integer of [0, ..., m] fulfilling the following conditions: no or minimal redundancy only use 1 integer variable or k independent integer variables with a ...
2
votes
1answer
362 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
420 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
79 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
57 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
635 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
29 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
605 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
240 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
1k 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
193 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
179 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
124 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
350 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
175 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
166 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
84 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
299 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
2answers
39 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
56 views

Can randomization be proven?

There exists a collection c where c = {1, 2, 3} and a randomization of c, ...
2
votes
1answer
146 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
74 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
464 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
1k 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
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 ...
3
votes
2answers
599 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
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 ...
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 ...
2
votes
1answer
123 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
664 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
950 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
114 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
229 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
833 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 ...