Questions tagged [permutations]
Permutations are arrangements of the numbers $1,\ldots,n$ in an arbitrary order.
185
questions
0
votes
0answers
49 views
Sequential Tasks with Greedy Algorithm
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 therefore only one task can be ...
6
votes
0answers
124 views
Counting number of swaps to make two strings equal in linear time
The input to our problem is a pair of strings, say $x$ and $y$. We treat our alphabet size as a constant, i.e., our input is effectively a pair of arrays with the values therein bounded by a constant.
...
1
vote
1answer
74 views
Faster algorithm for specific inversion count (part 2)
Following the issue from Faster algorithm for a specific inversion:
We have a permutation (a derangement actually) $\sigma$ of the set $\{0,1,\dots,n-1\}$ with cardinality $n$.
I want to compute ...
3
votes
1answer
535 views
Faster algorithm for a specific inversion
There is a permutation (more precisely a derangement) $\sigma$ of the set $\{0,1,\dots,n-1\}$ with cardinality $n$.
I want to compute the following counts (a kind of inversion):
$$K(\sigma )_{i}=\#\{j&...
3
votes
1answer
41 views
Does this algorithm for permuting rows and columns of a matrix converge?
Given a binary matrix, define the magnitude of a row by reading off the numbers in it left to right and similarly for columns, reading the numbers going down. For instance, the row magnitude of the 1-...
4
votes
0answers
64 views
Number of permutations with satisfactory triangles
We are given $N$ points($N \leq 40$), where no combination of three or more points is colinear. The values of $x$ and $y$ are bounded by [$0$,$10^4$]. The problem is to find the number of permutations(...
1
vote
1answer
99 views
Iterated multiplication of permutation matrices
Given $m$ matrices of size $n\times n$ each of which is promised to be a permutation is it in $\mathit{quasiAC}^0$ or $\mathit{AC}^0$ to multiply the permutations where
$m=\mathit{poly}(n)$
$m=\...
1
vote
0answers
35 views
Binary ↔ Gray permutation matrix
Generating a Gray code representation of a binary number can be thought of as mapping one binary number onto another binary number. Therefore, $n$-bit Gray code is a permutation of $2^n$ elements.
...
1
vote
1answer
187 views
number of ways evaluation of expression such that value not changed [closed]
one example:
How many ways we can do possible value-preserving parenthesis the following expression in such a way that value not changed after parenthesis with one constraint that parenthesis among ...
1
vote
1answer
77 views
Find Optimal Permutation/Positioning to Minimize the Total Distance for a Given Path
Summary:
A task for picking certain objects is given in the form of an ordered sequence (eg. to pick apple, banana, apple, apple, orange, order matters). The objects have to be preassigned to certain ...
4
votes
4answers
544 views
Enumerating all partial permutations of given length in lexicographic order
I need to generate all unique tuples of length k chosen from a series of unique, positive integers. In my case n choose k will have n=10, 1 <= k <= 10; and the series I am choosing from is { 0, ...
1
vote
1answer
60 views
Find The "Best" Permutation of Inputs to Maximize Sum of Functions (or approximate "best")
The Problem (in words)
I want to sort $N$ items where the value of item $i$ at position $p$ is given by the function $f_i(p)$. The "best" order for these items is the one that maximizes the ...
1
vote
1answer
34 views
Given permutation $p$, compute $p^{-2}$
I'm now to problem solving, and I need some help and insight on the following problem from HackerRank:
Given a sequence $p(1),\ldots,p(n)$ of distinct numbers from $1$ to $n$, find numbers $y_1,\...
1
vote
1answer
52 views
What's wrong with the following shuffle algorithm?
Suppose I have an array A of size n, with the initial state of:
...
0
votes
0answers
45 views
Simple incremental hash funcion
I have permutations:
4 1 2 5 3
4 3 2 5 1
numbers can be order magnitude of 1000 (fits in two bytes)
I want compute 32 bit (or better 64 bit) hashes, it should be ...
2
votes
0answers
70 views
How do you write a python\pseudo code that generates all pair permutations?
What would be a good pseudo code or Python 3 code for the following permutations problem?
Let us define a n-permutation as a bijective function $\pi: \{0,...,n-1\}\rightarrow \{0,...,n-1\} $ and ...
0
votes
0answers
38 views
finding the combinatorial solutions of series and parallel nodes
I have n nodes, and I want to find the (non duplicate) number of possible ways in which these nodes can be combined in series and parallel, and also enumerate all the solutions. For example, for n=3, ...
0
votes
0answers
55 views
Finding index of $p_{k}$ element in the original sorted array if elements were to be removed using a specific condition
Consider a sorted list of numbers $C_{0}=\{0,1,2,3,...,n-1\}$ from where one element will be eliminated at each step. We are also given a value $L$ in $[0, 1)$ and let the indexing start from $0$.
...
2
votes
1answer
89 views
Math behind leetcode problem 47 permutations II
Please tell me why the expression i>0 && nums[i] == nums[i-1] && !used[i-1] works on getting unique permutations. And what is the math behind it?
...
1
vote
1answer
72 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
602 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
54 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
24 views
encrypt with permutation ciphers
I came across this question:
You are given a permutation cipher defined by the bijection t: N -> N where,
...
3
votes
1answer
75 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
40 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)....
2
votes
1answer
134 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
62 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
2answers
470 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
1k 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
58 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
48 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,...
2
votes
1answer
54 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
73 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 ...
1
vote
2answers
917 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
1k 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
95 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
326 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$ ...
4
votes
1answer
526 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
162 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
129 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
187 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
86 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
27 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
25 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
260 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
119 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
258 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
173 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 ...
3
votes
2answers
350 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 ...
