Questions tagged [permutations]

Permutations are arrangements of the numbers $1,\ldots,n$ in an arbitrary order.

Filter by
Sorted by
Tagged with
-2 votes
0 answers
26 views

Permutation sort algo

You have to sort a permutation of a sequence into the original sequence using reinsertion. What type of algorithm could be used to minimize number of moves (reinsertions)? E.g. Transform $[4, 3, 1, 5, ...
1 vote
0 answers
85 views

How many ways we can partition a multiset, where each part/segment in the partition has distinct elements? [closed]

We define the set S as $\{(s_1, f_1), (s_2, f_2), ..., (s_i, f_i)\}$, where each $f_i$ is the frequency that $s_i$ is repeated in the multiset T. How many ways can we partition the multiset T into ...
-2 votes
0 answers
23 views

In permutation of n elements, count number inversions

Question: Let X be an array of form 1 to n different numbers. If X[i] > X[j] and i < j, then the pair (i, j) is called an inversion of X. In the permutation of n elements, the numbers of ...
1 vote
2 answers
113 views

Producing "moves" to permute one array to another

I have 2 arrays, A and B, which each contain the same N elements, but in a different order. (A different permutation) There are also no duplicates in A and B. I'm trying to devise an algorithm which ...
5 votes
2 answers
607 views

Compute Permutation Number

Given a permutation on the array of integers 1 through n, I want to find the index of the permutation in a list of all possible permutations of those integers, sorted in lexicographic order. For ...
  • 120
0 votes
1 answer
32 views

Construct an objective function that favors the sorted permutation

I was looking into complexity theory and disappointed by the fact that a problem as simple as sorting an array isn't in the class $P$. This is because the class is defined only for decision problems (...
0 votes
0 answers
29 views

Need math explaining calculation of number of binary tree topologies given n nodes

Grinding through leetcode, I came across the question of the number of binary tree topologies for n nodes. When looking up the best solutions, I saw the same line of code in each solution: ...
  • 101
0 votes
1 answer
30 views

Is this an inversion problem?

I understand that total inversion in a sequence is the number of swaps that need to be done, to sort the sequence. And the best approach to solve this problem is to count swaps in a merge sort of the ...
1 vote
1 answer
95 views

nth Permutation generator

I'm just trying to write a little algorithm. I've got nine objects, so there's 9! permutations. My question is, is there a way of turning a number from 1 to 9! into a permutation? for example, f(1)=[1,...
6 votes
0 answers
177 views

removing an item from n lists in $O(n^{1-\epsilon})$ amortized time

I have a straightforward task that can be done in $O(n^2)$ time. I'm now wondering if the task can be done in time $O(n^{2-\epsilon})$ if we are allowed to do some pre-processing. The problem exists ...
0 votes
0 answers
33 views

Circuit Complexity of Permutation

We are here considering permutations of the form $F_2^n \mapsto F_2^n$. I am interested in the $AC^k[2]$ circuit complexity of such functions. What are the upper and lower bounds in this context? Does ...
1 vote
1 answer
51 views

How many different boolean functions exist up to permutation of its $n$ variables

i am relatively new here, so if this was asked before, feel free to redirect me. I am searching for an answer in form of a (iterative or recursive) Formula or even better, an algorithm to list them ...
2 votes
1 answer
96 views

Question about stack permutations

I encountered an exercise in which I am struggling to understand the solution provided even though I spent a lot of time trying to figure it out. The exercise is the following and was taken from the ...
  • 117
1 vote
0 answers
46 views

Given a set, generate all permutations whose sums are less or equal to a given number

I am looking for a way to generate every permutation (so order does matter) of a set of positive numbers whose sum is less than (or equal to) a given limit. I need to find the permutations themselves, ...
  • 121
2 votes
1 answer
93 views

What loop invariant can be used for this loop? (Algorithm to check if a sequence is stack permutable)

I've written a function that gets a permutation and checks if that permutation can be reached using a stack from an input sequence which is <1,2,3,...,n>. (we take elements from left) For ...
  • 164
4 votes
2 answers
71 views

How can we prove QuickShuffle uniformly permutes it input array?

I'm studying Algorithms by Jeff Erickson. Consider this exercise from that textbook: Prove that the following algorithm, modeled after quicksort, uniformly permutes its input array, meaning each of ...
  • 1
0 votes
2 answers
66 views

Determining runtime of a theoretical program (question of extraordinary complexity)?

I apologize in advance, as I don't have a clue to which stackexchange to post this question! I beg you to not delete this question, as I have chronic pain and it is very important to me!!! I actually ...
3 votes
1 answer
69 views

Iteratively enumerating all permutations of $N$ objects using a generating set

The group theory of $S_n$ shows that all permutations of $n$ objects can be generated from the $n$-cycle $a:=(1 2 3 .. n)$ and the transposition $b:=(1 2)$. (See Theorem 2.5 at https://kconrad.math....
2 votes
2 answers
78 views

Memory-efficient list of N unique integers from 0..N-1 with fast lookup

We want to represent a list of $n$ unique integers between $0$ and $n-1$ in a memory-efficient way. The only operation we need to support is looking up the $n\text{-th}$ element. What are some of the ...
  • 121
6 votes
1 answer
188 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. ...
  • 63
1 vote
1 answer
82 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 ...
  • 937
3 votes
1 answer
552 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&...
  • 937
3 votes
1 answer
100 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-...
  • 55
4 votes
0 answers
71 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
1 answer
127 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
0 answers
57 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. ...
  • 177
1 vote
1 answer
193 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 ...
  • 119
1 vote
1 answer
139 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
4 answers
1k 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
1 answer
166 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
1 answer
44 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
1 answer
77 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
0 answers
71 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 ...
  • 141
2 votes
0 answers
117 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 ...
  • 21
0 votes
0 answers
39 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, ...
  • 101
0 votes
0 answers
58 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$. ...
  • 11
2 votes
1 answer
101 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
2 answers
94 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 ...
  • 11
1 vote
1 answer
1k 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
1 answer
73 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)$, ...
  • 133
1 vote
2 answers
41 views

encrypt with permutation ciphers

I came across this question: You are given a permutation cipher defined by the bijection t: N -> N where, ...
  • 167
3 votes
1 answer
150 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]$...
  • 155
2 votes
1 answer
52 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)....
  • 483
2 votes
1 answer
532 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 ...
  • 343
1 vote
0 answers
92 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 ...
  • 429
10 votes
2 answers
621 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
4 answers
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
1 answer
96 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 ...
  • 159
3 votes
0 answers
72 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,...
  • 41
2 votes
1 answer
81 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 ...
  • 99

1
2 3 4 5