Questions tagged [permutations]
The permutations tag has no usage guidance.
0
votes
0answers
16 views
Is there a specific search paradigm for finding pairs in a set?
I'm dealing with a very common problem in computer programming that involves, for example 4 people to be divided into 2 pairs. Mathematically, this is just a permutations problem, and the number of ...
0
votes
1answer
36 views
invite 12 person from 24 that we have 6 men and 6 womens [closed]
i had a question and its
"A man has 5 female and 7 male friends and his wife has 7 female and 5 male friends. In how many ways can they invite 6 males and 6 females if husband and wife are to invite ...
2
votes
0answers
12 views
How can I optimise a 8b10b encoding for maximum alignment?
Imagine you encode an 8 bit symbol as a 10 bit symbol that is sent sequentially over a wire. The goal at the receiver is to detect the byte boundary.
Since there are 4 times more encoded symbols than ...
0
votes
1answer
36 views
Find the cheapest combination of raw foods that fulfill nutritional requirements
I am starting a raw food diet and would like to properly plan it, and thus, would like to create a program that takes a list of available raw food, and finds the best combination of foods (multiples ...
0
votes
0answers
14 views
Applications of signed permutations to machine learning
Are there some applications of signed permutations to machine learning? I searched on google and only found one paper. Thank you very much.
2
votes
1answer
40 views
Does it hold that $F \equiv \sigma(F)$ for a CNF formula $F$ and a permutation $\sigma$ s.t. $F \vDash \sigma(F)$?
Suppose we have a CNF formula $F$ and a permutation $\sigma$ of its literals such that for any literal $x, \sigma(\neg x)=\neg \sigma(x)$ and $F \vDash \sigma(F)$.
Does it hold that $F \equiv \sigma(...
1
vote
0answers
119 views
which arrangement gets favoured in naive shuffling for a given numbers from 1 to n according to the algorithm given?
algorithm:
a=[1,2,3.....n]
for i in (1,n+1):
j=rand(1,n+1):
swap(a[i],a[j])
let us say that n=3:
132
213
231
these 3 are 5 times possible
and
123
312
321
are 4 times possible....
similarly
...
2
votes
1answer
30 views
Efficient algorithm to find the nth number in a base-k numeral system with only different digits
I am looking for an efficient algorithm for the following problem.
There is a base-k numeral system, and we want to have some k-length numbers, but all of the digits must be different ones.
It would ...
6
votes
1answer
152 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$. ...
5
votes
1answer
98 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
2answers
66 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
56 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 ...
2
votes
1answer
53 views
How to restore diagonal-symmetric matrix that has been shuffled?
I have a square matrix M, which originally looked like this:
133 199 101 121
142 133 199 101
156 142 133 199
108 156 142 133
(so symmetric around the diagonal). ...
0
votes
1answer
61 views
Simulated annealing to find the correct permutation of 20 words
I have 20 words. One permutation of these 20 words is the "correct" one. Assume I have a metric to find the correctness of the permutation.
I'm trying to figure out how to use simulated annealing to ...
0
votes
0answers
28 views
How does the following NP hardness proof work?
It is known that computing Kemeny optimal permutation, given a set of permutations is NP hard even when the given list has just four permutations. This is proved here (see Appendix B) along with all ...
1
vote
0answers
16 views
Splay Tree - Insert Permutation
Let $T$ be a Splay Tree. For a given permutation $\sigma$ on a set $S = \{1,2,3,...n \}$ we defined the following function:
...
0
votes
1answer
103 views
Are there any known implementations of a functional Heap's Algorithm?
TL;DR: Is an implementation of the Heap's Algorithm adhering to the principals of functional programming possible, and are any implementations of it known? And by "adhering to the principals of ...
1
vote
0answers
35 views
All permutations of N numbers with at least K-different positions
I'm trying to generate all permutations of N numbers where any two permutations are different by at least K positions. I would just like a push in the right direction, the trivial method of memorizing ...
0
votes
0answers
89 views
I'm having trouble calculating Big O for this bad permutation algorithm
I wrote this code to print all the permutations of a string. I believe it has time complexity of O(N^2). However, I'm not sure about it. Will inner loop run N! times?
Can you please help me ...
1
vote
1answer
36 views
Algorithm for this problem on generating all permutations
I am trying to come up with an efficient algorithm to solve the following problem but not able to design anything nice. I am encountering this problem for a project I am pursuing. Following is an ...
1
vote
1answer
35 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
120 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
48 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 ...
3
votes
1answer
22 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
145 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
94 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(...
3
votes
2answers
47 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 ...
3
votes
2answers
5k 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
115 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
28 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
266 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
55 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
66 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
469 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
180 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 ...
3
votes
1answer
344 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
288 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 ...
3
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
50 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 \...
3
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
377 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
26 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
369 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 ...
14
votes
2answers
197 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
873 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 ...
4
votes
4answers
163 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
118 views
Most Efficient Way to List All $n$-bit Permutations
Suppose we are asked to list all $n$-bit numbers in an order that is predetermined and random. What is the most efficient way to do such a listing using as few bits as possible?
Attempt: Start by ...
1
vote
0answers
90 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 ...
3
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
196 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 ...
