Questions tagged [permutations]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
27 views

Applying permutations with moves rather than swaps

Everything I can easily find on applying permutations in-place relies on treating swaps as elementary operations. But in reality, every swap requires at least two moves (to move the first item into ...
Logan R. Kearsley's user avatar
1 vote
0 answers
51 views

Computational complexity of an algorithm involving permutations

I'm interested in getting a precise estimate of the computational complexity of an algorithm I wrote involving permutations. Permutations are represented in my code as arrays of the integers $1$ ...
Matt Samuel's user avatar
4 votes
0 answers
195 views

Game of permutations as a minimization problem

Consider the following "game". There is an ant on a strip of length N. The ant can perform the following actions: move left, move right, and paint the cell he is on with white or black. The ...
TRP's user avatar
  • 41
0 votes
0 answers
35 views

How to handle duplicates with Heap's algorithm for permutations?

I was able to use Heap's algorithm for generating permutations and I was able to solve the duplicates problem by looking at all the results and filtering out duplicates myself using a HashSet in Java. ...
ashish singh's user avatar
0 votes
1 answer
47 views

Efficient algorithms to generate partial permutations?

I want to efficiently generate partial permutations. That is, I want to generate the set of ordered arrangements of K distinct elements selected from a set from N items. For example, with the set ...
Ana's user avatar
  • 11
1 vote
2 answers
110 views

Heap's Algorithm for k-permutations?

Heap's Algorithm enumerates the permutations of a set of N objects. It's described as: Permute the elements in positions 1 to n−1 by applying this algorithm to those elements. Apply the following ...
Ana's user avatar
  • 11
0 votes
0 answers
19 views

Minimum number of swaps to achieve prefix constraint

(An isogram is a word in which no letters repeat.) I'd like to know if there's a standard name for this problem, and/or any standard algorithms. If not, I'm interested in whether anyone has any ideas ...
SocraticMathTutor's user avatar
1 vote
1 answer
93 views

Proof of correctness of some optimization of Heap's algorithm for producing permutations

Good day. Some time ago I found a page on (en.) wikipedia about Heap's algorithm for permutations. Here it is. Original algorithm can be written as next (copy from (en.) wikipedia): ...
Forelyl's user avatar
  • 11
1 vote
1 answer
63 views

Check if Two Arrays Sorted in Decreasing and Increasing Order Satisfy a Condition

Given 2 arrays $A, B$ each of size $n$. If we want to find if the two arrays satisfy the condition that $A[i] + B[i] \ge k$ for all indices $i$, it's sufficient to fulfill 3 conditions below: Sum of ...
Avv's user avatar
  • 493
0 votes
1 answer
25 views

Ranked voting method where unranked candidates on a preference list aren't taken to be the least preferred?

Say there are 5 candidates, A, B, C, D, and E. An election is held using a ranked voting method. That is to say, each voter submits a preference list (the order in which they prefer candidates). E.g. ...
chausies's user avatar
  • 532
0 votes
0 answers
17 views

Weighted permutation bucketting

Given a set of weighted permutations of numbers, an operation can be performed to combine multiple permutations that share numbers into a single rolled up permutation. What is the optimal algorithm to ...
Peter's user avatar
  • 1
0 votes
0 answers
13 views

One-shot capacity achieving input, permutation invariance and i.i.d. decomposition

Suppose I have $n$ iid copies of a channel $W_{Y|X}$ and denote this by $W_{Y|X}^{\otimes n}$. I found a one-shot capacity of $W_{Y|X}^{\otimes n}$ to be an entropic quantity (specifically, it is the ...
JRT's user avatar
  • 101
0 votes
1 answer
48 views

What can I read about permutations in 3D space?

I'm interested in the theory of calculating the position of an element when the face of a cube is moved - like in a Rubik's Cup. That is, for example, I rotate the face of the cube - how can I ...
BadCatss's user avatar
  • 113
2 votes
0 answers
62 views

Permuting matrix entries to lower rank

Suppose I have a rank-$k$ matrix $A \in \mathbf{R}^{m \times n}$. Now suppose this matrix has its elements shuffled by an adversary to maximize the rank. Is there a way to reverse this permutation and ...
Calvin Elder's user avatar
0 votes
2 answers
31 views

Doubt regarding conjugations of permutations

I was studying the Barrington Theorem in https://homes.cs.washington.edu/~anuprao/pubs/CSE531Sp2020/lecture2.pdf when I found a doubt regarding permutations. Particularly, with conjugations. It is ...
441Juggler's user avatar
1 vote
1 answer
156 views

Finding Optimal Configuration of Formula without trying every Permutation

I have a math problem I need to solve so I can complete an optimisation in a computer program. My initial approach was just to brute force all the possible permutations but it got out of hand quite ...
Anters Bear's user avatar
0 votes
0 answers
22 views

Manipulating a binary tree representation

I am designing a discrete probability distribution with a string of binary values as an input $\{s_i\}\in\{S_i\}$, and binary outputs $e\in E$ with Bernoulli probability $P(E=1|\{S_i\})=XOR[\{S_i\}]=...
Jordan K's user avatar
1 vote
0 answers
108 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 ...
AmirHosein Adavoudi's user avatar
2 votes
2 answers
140 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 ...
123veggie123's user avatar
5 votes
2 answers
628 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 ...
LogicalX's user avatar
  • 120
0 votes
1 answer
42 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 (...
Rohit Pandey's user avatar
0 votes
0 answers
48 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: ...
RBZ's user avatar
  • 101
0 votes
1 answer
49 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 ...
Ogunleye Ayowale Pius's user avatar
1 vote
1 answer
125 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,...
Elliott Price's user avatar
6 votes
0 answers
183 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 ...
Albert Hendriks's user avatar
1 vote
1 answer
58 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 ...
vreithinger's user avatar
2 votes
1 answer
128 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 ...
Yarin's user avatar
  • 229
1 vote
0 answers
73 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, ...
charon25's user avatar
  • 121
2 votes
1 answer
132 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 ...
Pwaol's user avatar
  • 164
4 votes
2 answers
78 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 ...
Er7's user avatar
  • 53
0 votes
2 answers
135 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 ...
empleat's user avatar
3 votes
1 answer
84 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....
Jared Stewart's user avatar
2 votes
2 answers
92 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 ...
glebm's user avatar
  • 121
6 votes
1 answer
220 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. ...
MeyCJey's user avatar
  • 163
1 vote
1 answer
85 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 ...
Nikos M.'s user avatar
  • 957
3 votes
1 answer
556 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&...
Nikos M.'s user avatar
  • 957
3 votes
1 answer
137 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-...
st210's user avatar
  • 55
3 votes
0 answers
72 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(...
Jonathan Mcgee's user avatar
1 vote
1 answer
152 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=\...
User2021's user avatar
1 vote
0 answers
77 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. ...
mavzolej's user avatar
  • 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 ...
Emma Nic.'s user avatar
  • 119
1 vote
1 answer
211 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 ...
B.Mr.W.'s user avatar
  • 143
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, ...
Reinderien's user avatar
1 vote
1 answer
262 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 ...
Jake Greene's user avatar
1 vote
1 answer
46 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,\...
Harsha Limaye's user avatar
1 vote
1 answer
95 views

What's wrong with the following shuffle algorithm?

Suppose I have an array A of size n, with the initial state of: ...
so.very.tired's user avatar
0 votes
0 answers
85 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 ...
Saku's user avatar
  • 141
2 votes
0 answers
130 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 ...
Yoav's user avatar
  • 21
0 votes
0 answers
43 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, ...
R71's user avatar
  • 101
0 votes
0 answers
59 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$. ...
Ganesh's user avatar
  • 11

1
2 3 4 5