Questions tagged [permutations]
The permutations tag has no usage guidance.
168
questions
0
votes
1answer
37 views
Given $n$ unique items and an $m^{th}$ normalised value, compute $m^{th}$ permutation without factorial expansion
We know that the number of permutations possible for $n$ unique items is $n!$.
We can uniquely label each permutation with a number from $0$ to $(n!-1)$.
Suppose if $n=4$, the possible permutations ...
0
votes
1answer
40 views
Greedy sequential/parallel task scheduling
We have N tasks that need to be scheduled for processing. Each task consists of two parts that need to executed in order. The first one is guarded by a mutex and ...
1
vote
1answer
42 views
What is the maximum number of indices one can create on a table with N columns?
Say, I have a database table with $N$ columns. What is the (theoretical) maximum number of indices I can create on that table? For $N = 1,2,3$ it's easy enough to calculate the answer $(1, 4, 15)$, ...
1
vote
2answers
20 views
encrypt with permutation ciphers
I came across this question:
You are given a permutation cipher defined by the bijection t: N -> N where,
...
0
votes
0answers
30 views
Reverse of In-place algorithm for interleaving an array
How to do the reverse process of In-place algorithm for interleaving an array question?
3
votes
1answer
53 views
Minimize function on permutations
Problem:
Consider $[k] = \{ 1, 2, \dots, k \}$ and function (of two arguments) $f: [k]^{2} \rightarrow \mathbb{N}$ that is defined for all $(n, m) \in [k]^{2}$ (all ordered pairs of numbers from $[k]$...
2
votes
1answer
37 views
If I walk through list and delete every out-of-order element I come across, on average how many elements will be left?
I have a uniformly randomly permuted list of length $n$. I walk through the list element-by-element, and delete an element if it's out-of-order (compared to the previous in-order elements of the list)....
1
vote
1answer
34 views
Pseudo code of recursive method of printing all permutations of $n$ given integers
I really don't understand this pseudo code. The function prints all permutations of $n$ given integers, assuming that all numbers are different.
Is there a way to explain this code more easily as I ...
1
vote
0answers
38 views
Is there an algorithm to generate all permutations of a multiset through swaps?
I am currently working on a project where I have to perform a computation over all possible permutations of a multiset $S$. In my setting, each multiset is a list of small positive integers such as $S ...
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, ...
8
votes
4answers
569 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 ...
0
votes
1answer
37 views
Analysis of Pan-cake sorting
i was implementing pan-cake sorting. We can implement it by taking largest element to start and flipping it recursively (Like selection sort).
However it is mentioned that the A[i] has to be a ...
3
votes
0answers
21 views
Generating permutations with a given bubblesort distance
I'm looking for an algorithm to randomly generate permutations on 1:n, which though have a defined bubblesort distance d from 1:n, e.g. (2,3,1) and (3,1,2) are distance 1 from (1,2,3), (2,3,1) and (3,...
0
votes
0answers
8 views
Creating a specific hash setup
While solving a practice exam, this is the question I could not answer. Any help is appreciated. I am new to hashing and have no idea how to solve this question.
Let $H$ be a $(0.15, 0.85, 0.9, 0.1)$-...
2
votes
1answer
39 views
Combinations and Permutations of M sets of distinct items?
I'm wokring on this problem for a while. I want to know:
The correct name of this problem, so I can look it up in textbooks\online.
Here is the problem descirption:
The (un-ordered) combinations to ...
1
vote
1answer
38 views
Applying subproblem technique to permutations with grouping
I am trying to apply overlapping subproblems and dynamic programming to permutations.
Say, we have a set of $n$ elements in a string. Each of these elements could be a $1$ or a $0$.
Given some ...
0
votes
2answers
262 views
number of permutation with k inversions
We are given two numbers N and K.
N <= 10^9.
K<=min{1000,(N*(N-1))/2}
We need to find numbers of permutations of ( 1 to N ) such that inversions are exactly K.
If N was <= 10^3. It would ...
0
votes
0answers
34 views
Complexity of Rearranging a Prefix Tree/Alternative Data Structures
Let $S$ be a subset of $[0,1]^l$. Is there some data structure that can represent $S$ and can perform the following operations/queries efficiently*?
$ADD(s \in [0,1]^l)$ - operation which updates $S$ ...
0
votes
2answers
647 views
How to generate all combinations given an array of elements using backtracking?
Given an array, generate all combinations
For example:
Input: {1,2,3}
Output: {1}, {2}, {3}, {1,2}, {2,1}, {1,3}, {3,1}, {2,3}, {3,2}, {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1}
I am ...
0
votes
1answer
45 views
Minimize same placed elements in a list of permutations (Heap)
I'm trying to optimize the permutations generated from a set of n elements.
Here is the pitch:
I have a set of 6 elements $\{1,2,3,4,5,6\}$ and I want to create 10 permutations. I could use Heap ...
1
vote
2answers
157 views
Permute an array in O(n) time with O(1) extra space with a given ordering function?
This question arises from a problem on a problem solving site (https://practice.geeksforgeeks.org/problems/-rearrange-array-alternately/0).
Given a sorted (ascending order) array $A$ of $N$ ...
3
votes
1answer
319 views
Generate all permutations of 1 to n with i stacks
Assume we have i stacks. the possible actions are:
push to first stack form input
pop from stack i and push it to stack i+1
pop from last stack to output
If we have numbers of 1 to n starting from 1 ...
1
vote
2answers
80 views
Check if two separate ranges have some number in common
We are given two permutations: A of size N and B of size M. We need to process Q queries, each query is given by two ranges, one subarray range in permutation A and one in B. We should check if there ...
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 ...
1
vote
2answers
54 views
Lexicographic permutation list
Does anyone have an algorithm for stepping through all permutations of n given arbitrary objects in lexicographic order?
Thanks.
1
vote
1answer
26 views
Does “$\forall x\in L, \sigma(\neg x)=\neg \sigma(x)$” hold given that $\sigma(F)\equiv F$ for a CNF formula $F$ built on a set $L$ of literals?
Suppose we have a CNF formula $F$ built on the set of literals $L=\{x_1,\neg x_1,\cdots,x_n,\neg x_n\}$ where each variable is used in at least one clause of $F$. Consider a permutation $\sigma$ of $L$...
0
votes
0answers
24 views
Finding “good” order of elements for the purpose of material minimization
I am working with metallic shapes which are curved and highly irregular. The initial order of them is random and by default they are merely sorted by size, which is simple. However the resulting order ...
2
votes
1answer
130 views
Permutation of n-size array with possible repeated elements. E.g [1, 2, 1]
What would it be a recursive algorithm to get permutations for any list of n elements that might contain or not repeated elements?
For the following 3-element list ...
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 $...
9
votes
2answers
219 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,
...
2
votes
0answers
96 views
How to find big-O for an in-place perfect shuffle algorithm
I've found a simple algorithm to interleave two halves of an array in place. It involves swapping the first 1/2 of the items into the correct place, then unscrambling the permutation of the 1/4 of ...
2
votes
2answers
157 views
O(B) algorithm to find positions of all permutations of smaller string in a bigger string with length B - how is this possible?
Context: I've been working through Cracking the Code Interview and on page 70 the book asserts that there is a O(B) solution to this problem.
If
s = little string and S = len(s)
b = big string and ...
3
votes
0answers
85 views
Adjacent Gray code
Gray code is permutation of $\{0,1,2,\dots,2^n-1\}$ such that each of consecutive number is differs only one bit in binary representation.
Example for $n = 3$
$000\\
001\\
011\\
010\\
110\\
111\\
...
3
votes
1answer
64 views
Generation of all k-combinations of a set in max-differing order
I'm looking for an algorithm that generates all k-combinations of a set, such that each successive combination generated differs as much as possible (or in practice, a lot) from all previous ...
0
votes
0answers
18 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
40 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
29 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
3answers
80 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
47 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
124 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
60 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
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$. ...
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
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
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 ...
2
votes
1answer
135 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
2answers
166 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 ...
1
vote
0answers
69 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:
...
