# Questions tagged [permutations]

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

174 questions
Filter by
Sorted by
Tagged with
29 views

349 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, ...
792 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 ...
43 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 ...
31 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 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 ...
56 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 ...
754 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 ...
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$ ...
795 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 ...
72 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 ...
206 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$ ...
383 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 ...
88 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 ...
75 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). ...
118 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 ...
62 views

### Lexicographic permutation list

Does anyone have an algorithm for stepping through all permutations of n given arbitrary objects in lexicographic order? Thanks.
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$...
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 ...
139 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 ...
114 views

71 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 ...
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 ...
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 ...
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 ...
81 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 ...