Questions tagged [permutations]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
23 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
21 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 ...
0
votes
2answers
82 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
33 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
81 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
23 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
63 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$ ...
2
votes
1answer
127 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
45 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
59 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
78 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
44 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
24 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
23 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
125 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
87 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
175 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, ...
1
vote
0answers
63 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 ...
2
votes
2answers
53 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 ...
3
votes
0answers
75 views

Adjacent Gray code

Gray code is permutation of $\{0,1,2,\dots,2^n-1\}$ such that each of consecutive number is differs only one bit in binary representation. Example for $n = 3$ $000\\ 001\\ 011\\ 010\\ 110\\ 111\\ ...
0
votes
0answers
16 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 ...
0
votes
1answer
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 ...
2
votes
0answers
21 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 ...
0
votes
3answers
75 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 ...
0
votes
0answers
14 views

Applications of signed permutations to machine learning

Are there some applications of signed permutations to machine learning? I searched on google and only found one paper. Thank you very much.
2
votes
1answer
44 views

Does it hold that $F \equiv \sigma(F)$ for a CNF formula $F$ and a permutation $\sigma$ s.t. $F \vDash \sigma(F)$?

Suppose we have a CNF formula $F$ and a permutation $\sigma$ of its literals such that for any literal $x, \sigma(\neg x)=\neg \sigma(x)$ and $F \vDash \sigma(F)$. Does it hold that $F \equiv \sigma(...
1
vote
0answers
123 views

which arrangement gets favoured in naive shuffling for a given numbers from 1 to n according to the algorithm given?

algorithm: a=[1,2,3.....n] for i in (1,n+1): j=rand(1,n+1): swap(a[i],a[j]) let us say that n=3: 132 213 231 these 3 are 5 times possible and 123 312 321 are 4 times possible.... similarly ...
2
votes
1answer
49 views

Efficient algorithm to find the nth number in a base-k numeral system with only different digits

I am looking for an efficient algorithm for the following problem. There is a base-k numeral system, and we want to have some k-length numbers, but all of the digits must be different ones. It would ...
6
votes
1answer
158 views

Chernoff-Hoeffding bounds for the number of nonzeros in a submatrix

Consider a $n \times n$ matrix $A$ with $k$ nonzero entries. Assume every row and every column of $A$ has at most $\sqrt{k}$ nonzeros. Permute uniformly at random the rows and the columns of $A$. ...
5
votes
1answer
134 views

Permutation of words that have matched parentheses

Let $L$ denote the (context-free) language of matched parentheses over the alphabet $\Sigma$. Consider the following problem: Input: words $x_1,\dots,x_n \in \Sigma^*$ Question: does there exist a ...
5
votes
2answers
93 views

Chernoff-like Concentration Bounds on Permutations

Suppose I have $n$ balls. Among them, there are $m \leq n$ black balls and the other $n - m$ balls are white. Fix a random permutation $\pi$ over these balls and denote by $Y_i$ the number of black ...
5
votes
1answer
63 views

Applying a permutation on a sequence with multiplication

We are given a sequence of $n$ numbers called $\alpha$ and an arbitrary number $x$. Give an algorithm to find a permutation $\pi$ of size $n$ such that $\sum_{i=1}^n{\alpha_i.\pi_i} = x$ or tell if ...
2
votes
1answer
105 views

How to restore diagonal-symmetric matrix that has been shuffled?

I have a square matrix M, which originally looked like this: 133 199 101 121 142 133 199 101 156 142 133 199 108 156 142 133 (so symmetric around the diagonal). ...
0
votes
2answers
132 views

Simulated annealing to find the correct permutation of 20 words

I have 20 words. One permutation of these 20 words is the "correct" one. Assume I have a metric to find the correctness of the permutation. I'm trying to figure out how to use simulated annealing to ...
1
vote
0answers
21 views

Splay Tree - Insert Permutation

Let $T$ be a Splay Tree. For a given permutation $\sigma$ on a set $S = \{1,2,3,...n \}$ we defined the following function: ...
0
votes
1answer
234 views

Are there any known implementations of a functional Heap's Algorithm?

TL;DR: Is an implementation of the Heap's Algorithm adhering to the principals of functional programming possible, and are any implementations of it known? And by "adhering to the principals of ...
1
vote
0answers
49 views

All permutations of N numbers with at least K-different positions

I'm trying to generate all permutations of N numbers where any two permutations are different by at least K positions. I would just like a push in the right direction, the trivial method of memorizing ...
1
vote
1answer
38 views

Algorithm for this problem on generating all permutations

I am trying to come up with an efficient algorithm to solve the following problem but not able to design anything nice. I am encountering this problem for a project I am pursuing. Following is an ...
1
vote
1answer
42 views

number of queries to recover the permutation

Imagine this game. I pick a permutation $p$ of $1..n$ and give you an oracle. When the oracle is queried with any sequence of $n$ numbers $\in 1..n$, it masks each number by applying some unknown ...
1
vote
1answer
188 views

Black-box combinatorial optimization problem over permutations

I am solving general black-box optimization problems like: x*: f(x) -> min, where x are permutations of length N (N = 50 for example, so brute force search is not possible). Objective function f(x) is ...
1
vote
1answer
68 views

Maximizing the sum of adjacent pairs of elements

I encountered the following interesting problem on stackoverflow: Given numbers $a(1)<\cdots<a(n)$, find a permutation $\pi$ that maximizes $$\sum_{i=1}^{n-1} a(\pi(i)) a(\pi(i+1)).$$ The ...
2
votes
1answer
33 views

Counting number of permutations respecting partial order

Suppose that we have an array $A$ of $n$ elements with some partial order known, e.g. for example as a $n\times n$ matrix containing $c_{ij} \in \{-1, 0, 1\}$ where $0$ represents unknown and $-1, 1$ ...
2
votes
0answers
179 views

How many similar binary search trees are made from different permutations?

If I have numbers ranging from 1 to n, and I generate all the permutations of these numbers. Now, I create Binary search tree from these permutations. For a value n i want to know how many BSTs would ...
0
votes
1answer
106 views

Minimizing the SUM algorithm

We are given $2n$ positive integers $a_1,a_2\ldots,a_n$ and and $$b_1,b_2,\ldots,b_n$$ as input. The question is to find a permutation $O$ on $\{1,2,\ldots,n\}$ that minimizes $$\sum_{i=1}^n \left(...
2
votes
2answers
53 views

Indexing a random permutation

I am curious if there exists a method for specifying a permutation $F_k: X \to X$ with a small(ish) $k$. Something that comes very close to my goal is a block cipher, say AES. But block ciphers have ...
4
votes
2answers
8k views

Using backtracking to find all possible permutations in a string

I came across this algorithm in a book, and have been struggling to understand the basic idea. The books says it uses backtracking to print all possible permutations of the characters in a string. In ...
1
vote
1answer
180 views

Determine if a string is a permutation of another string efficiently [duplicate]

Given two strings of the same length, determine if they are permutations of each other. I can come up with two solutions, one in O(n log n) time with O(1) extra space, and one in O(n) time with O(n) ...
0
votes
0answers
34 views

Efficient permutation of given ranking that preserves given distance

Ranked Biased Overlap (RBO) is a metric for comparing two rankings and is used when the sizes of the given rankings are different and/or the elements that they carry are not the same. Ranked Biased ...
0
votes
0answers
343 views

Interleaving first and second half of an array of even length in place

If A is an array with the following elements: $$ a_1,a_2,...,a_n,b_1,b_2,...,b_n $$ How to shuffle A to form: $$ a_1,b_1,a_2,b_2,...,a_n,b_n $$ with minimal swaps and using no additional space? I ...
1
vote
1answer
68 views

Finding a subset of triplets of digits 0-9 such that each digit occurs 40 times in each position in the triplets

I am trying to generate a list of digit triplets to specify stimuli in an auditory (speech-in-noise) perception experiment. Each triplet has to have three different digits (i.e., no repetition within ...