# Questions tagged [permutations]

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

217 questions
Filter by
Sorted by
Tagged with
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 ...
1 vote
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$ ...
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 ...
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. ...
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 ...
1 vote
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 ...
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 ...
1 vote
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): ...
1 vote
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 ...
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. ...
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 ...
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 ...
48 views

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 ...
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 ...
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 ...
1 vote
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 ...
22 views

1 vote
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. ...
1 vote
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 ...
1 vote
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 ...
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
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 ...