4
votes
1answer
54 views

How to check if $\text{position}\left(\frac{a + b} 2\right )$ is in range $\text{position}\left(a\right )$ and $\text{position}\left(b\right )$

Given a permutation of $n$ number $1, 2, 3,\dots,n$. How to check if it is exist $a,\ b$ with the same parity such that $\frac {a + b} 2$ is between $a, b$. How to solve this problem efficiently ? ...
1
vote
0answers
56 views

Sparse matrix algorithms involving data-driven or random access / walk

I am looking for some well-known algorithms in which sparse matrix elements are accessed in a non-structured way, i.e. row/column depends on a value of another (sparse) matrix/vector element or some ...
0
votes
0answers
31 views

Inversion and permutations

Let call two arrays A and B with length n almost equal if for every i (1 <= i <= n) CA(A[i]) = CB(B[i]). CX[x] equal to number of index j (1 <=j <= n) such that X[j] < x. For two ...
3
votes
1answer
40 views

Total number of possible sub sequence with given condition

Given a sequence of two letters A and B find the total number of possible sub sequences where number of letter A is two times the number of letter B without ...
-1
votes
2answers
61 views

How to generate all possible combinations for X numbers in PHP? [duplicate]

I would like to make function in PHP which would print all possible combinations for X numbers. For example, for input 2 result would be: 12 21 For input 3 ...
4
votes
2answers
104 views

Count Number of Sequences

The question is: Given a sequence of positive integers A={1,2,3,...,N}. Count the number of sequences you can get after making K swaps between adjacent element on it for a given N ? My approach: My ...
2
votes
0answers
212 views

Count swap permutations

Given an array A = [1, 2, 3, ..., n]: ...
0
votes
1answer
56 views

What is the meaning of nCk X nPk?

I am trying to understand the bulls and cows document, Page 6 , equivalences . Can someone please tell me what author means when he says nCk x nPk like 4P0 X 4C0 , 4P1 X 4C1 ?
2
votes
1answer
44 views

Possible Ways to reach a Sum

Imagine that I have a N long set of numbers. I would like to know the possible ways that I could reach a specific sum using only the numbers in my set. As an example: ...
0
votes
1answer
66 views

Finding the 'n'th k-permutation of a set, and finding 'n' for a given k-permutation (lexicographical ordering)

Suppose you have a set, and want to order the k-permutations of the set (for example, the permutations of 5 elements of the set {1, 2, 3, ..., 16}). Is there a fast way of finding 'n' (the ...
2
votes
2answers
74 views

Algorithm to compute maximum permutation sum in matrix

Given a matrix $A_{n\times n}$ of real numbers, what fast algorithms do there exist to compute the maximum value of $a_{1,\sigma(1)}+a_{2,\sigma(2)}+\ldots+a_{n,\sigma(n)}$ over all permutations ...
2
votes
0answers
48 views

Composing permutations in factorial notation

Given two permutations $p_1$ and $p_2$ in factorial notation, is there a direct algorithm which computes their composition directly, i.e. without translating to a different notation or via computing ...
0
votes
0answers
55 views

Summing the product of combinations of matrix elements

I have a situation where I have an $NxN$ matrix $A$ where each element $a_{i,j}\in\mathbb{R}_{\leq 0}$. I would like to consider the set of all collections of elements such that each collection of $N$ ...
2
votes
1answer
28 views

Permutation query

Would anyone be able to help here with this one ? Let $A = \{a, …, z, A, …, Z, 0, …, 9\}$ be some alphabet and let $$q = q_1, …, q_m \text{ and } w = w_1, …, w_n$$ be finite-length words in $A^*$. ...
0
votes
1answer
71 views

Alternating Pair

I want to find the number of permutations of $1,2,\ldots,N$ having exactly $k$ triples satisfying the condition that either $n_{i-1}>n_i<n_{i+1}$ or $n_{i-1}<n_i>n_{i+1}.$ For example for ...
1
vote
1answer
59 views

Finding Required Permutation

I have numbers from $1$..$n$. I want to find number of permutation from all $n!$ permutation where the numbers have following arrangement. $L$ $G$ $L$ $G$ $L$ or $G$ $L$ $G$ $L$ $G$. Where L means ...
3
votes
1answer
93 views

Expected Value of this function

Let’s consider a random permutation p1, p2, …, pN of numbers 1, 2, …, N and Function F is calculated as F=(X[2]+…+X[N-1])^K, where ...
1
vote
0answers
261 views

Finding the number of arrangement of N people of different height such that K of them are visible from front

Moderator Note: This is a current contest question on codechef.com. [Initially, I had asked this question in stackoverflow, but someone suggested to post it here, and hence this question is ...
0
votes
2answers
346 views

How do I find the maximum number of knights on a chess board?

I came across this problem and after thinking a lot I could not get any idea how to calculate it. Please suggest to me the right way to calculate it. Given a position where a knight is placed on ...
3
votes
1answer
54 views

How to arrange $n$ pairs of numbers so that this expression is minimized

Consider $n$ pairs of positive integers, $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$. Make a permutation $(a_1, b_1), (a_2, b_2), \dots, (a_n, b_n)$ of these pairs, such that for all $x_i, y_i$, a ...
1
vote
3answers
81 views

Distribute Gifts among students

$N$ students are to be provided with gifts We know that the $i$'th student wants to get at least $a_i$ gifts. The teacher wants to give distinct gifts meaning if he give $x$ gifts to one student then ...
1
vote
0answers
91 views

Permutation for arranging letters in such a way that no similar letters come together (except SPACE)

I would like to get a general expression for arranging n letters such that any similar letters in them never come together (except SPACE). For example : Lets take AABBCCC and three ...
2
votes
4answers
150 views

Divisibility by seven

Given number n, whose decimal representation contains digits only $1, 6, 8, 9$. Rearrange the digits in its decimal representation so that the resulting number will be divisible by 7. If number is m ...
5
votes
1answer
184 views

Numbers permutation

Given $n$ numbers and $k$ positions I want the total number of permutations of these n numbers on these $k$ positions if repetition is allowed and if the following two arrangements are considered ...
0
votes
0answers
15 views

If $A_j=\sum_{x,y,z}B_{x}B_{y}B_{z}$, where $x+y=z+j$, is there a closed form expression for $\frac{\partial A_j}{\partial{B_k}}$?

I am working on a problem involving equations whose interaction is governed by a conservation of momentum condition. Essentially I have two vectors $\mathbf{A}=\left\{A_j\right\}$ and ...
2
votes
1answer
88 views

number of derangements

In the normal derangement problem we have to count the number of derangement when each counter has just one correct house,what if some counters have shared houses. A derangement of n numbers is a ...
1
vote
0answers
63 views

number of ways to arrange

There are N 1s and N 0s We have to arrange them in a row such that at no position in this row the number of 0s from the beginning exceed the number of 1s from the beginning. Also the number of ...
2
votes
2answers
126 views

Maximum number of seating plans

15 people will be seat in a row of 15 chairs. Two seating plan are considered the same if two plans share same adjacent quadruples. What is the maximum number of seating plans can be made? For ...
0
votes
0answers
68 views

How is the algorithm for recursively printing permutations of a set of numbers this equation our professor gave us?

I'm having a great amount of trouble understanding where my prof got $T(m, n) = n(T(m+1, n-1) + m+1 + n)$ if $n > 1$ as the recursive formula for the algorithm for recursively printing the ...
2
votes
4answers
519 views

distributing z different objects among k people almost evenly

We have z objects (all different), and we want to distribute them among k people ( k < = z ) so that the distribution is ...
1
vote
0answers
30 views

Finding k-d sum for all numbers upto maxVal [duplicate]

a number n is a k-d number if either of the following holds true: a) number of digits <=k b) sum of first k digits is equal ...
0
votes
2answers
88 views

Determine no of combinations for cutting stock algorithm

I have to buy $n$ wooden logs of size 2000 each, from which I have to cut different pieces of smaller size say: 255*10 750*7 550*13 In a manner that cutting will ...
0
votes
1answer
95 views

Explanation on step $\rho$ of the SHA-3 algorithm

I'm working on implementing SHA-3 in a PIC microcontroller. In the block permutation, I don't quite understand step $\rho$: Bitwise rotate each of the 25 words by a different triangular number 0, ...
1
vote
1answer
105 views

Minimum number of moves to convert a list of any integers into a permutation

Given a list of integers of size n, how to find the minimum number of moves to convert it to a Permutation? In one move, we are allowed to decrease or increase any element of the list by one. For ...
1
vote
1answer
130 views

Generating a random derangement

I'm having a problem about derangements that I'm trying to solve. Given a set $S = \{1,\ldots,n\}$, I want to generate a random derangement. I've considered generating a permutation and checking ...
5
votes
1answer
194 views

Algorithm creating subsets with certain properties

I'm trying so solve following problem: Let's say, we have a set $A=\{1,2,3,...,49\}$. Now, I am defining sets $A_1, A_2, A_3,...,A_n$ as follow: $A_1=\{a_1,a_2,a_3,...,a_{30}\}$, $A_2= ...
32
votes
1answer
1k views

Is War necessarily finite?

War is an cardgame played by children and drunk college students which involves no strategic choices on either side. The outcome is determined by the dealing of the cards. These are the rules. A ...
1
vote
0answers
168 views

Who invented the breadth-first permutation algorithm?

My initial problem was solved here. It is about enumerating all n-tuples of a permutation in a specific order. The solution algorithm is very simple and I'm sure has been used before. However, I did ...
2
votes
1answer
125 views

How to find a canonical member of an equivalence class of matrices under row and column swaps?

Call two matrices "swap-equivalent" if one matrix can be transformed into the other via some sequence of row swaps and column swaps. I'd like a computationally efficient algorithm that can transform ...
3
votes
1answer
299 views

How many non-isomorphic permutation selections are on an arbitrary N x N square matrix with rotations applied?

My question is an extension to a classic one: On a square $N \times N$ grid, select exact $N$ cells that satisfy condition: only one cell selected in same row and column. How many solutions will ...
-2
votes
1answer
167 views

How many possible ways are there

Suppose i have the given data set of length 11 of scores p=[2, 5, 1 ,2 ,4 ,1 ,6, 5, 2, 2, 1] I want to select 6 ,5 , 5 , 4 , 2 , 2 scores from the data set. How many ways are there? For the above ...
0
votes
0answers
74 views

Calculate pairing in a rotational system

I'm not even sure how to word this question. So I'll explain it out. I've got these values: A1, A2, B1, B2, B3, C1, C2, I need each A to be paired with each B and C each B with each A and C ...
7
votes
1answer
370 views

Algorithm for scrolling through different orbits in a permutation group

Given an $n\in\mathbb{N}$, and a permutation $\pi\in S_{n}$, denote the centralizer of $\pi$ by $C_{\pi}$. Now we can look on the conjugation action of $C_{\pi}$ on $S_{n}$ and then divide $S_{n}$ to ...
17
votes
4answers
3k views

How does one compute the sign of a permutation?

The sign of a permutation $\sigma\in \mathfrak{S}_n$, written ${\rm sgn}(\sigma)$, is defined to be +1 if the permutation is even and -1 if it is odd, and is given by the formula $${\rm sgn}(\sigma) ...
1
vote
1answer
151 views

Question on permutation

I asked this question : Composition of permutation to generate all permutations earlier but I didn't phrase it well, here is my new question. My question is a little bit different I'm looking for a ...
4
votes
3answers
787 views

Composition of permutation to generate all permutations

Looking at permutations I came up with the following question: Can you find a permutation S of a set of n elements such that by composing this permutation n! times you will describe all the possible ...
4
votes
1answer
407 views

Is it possible to efficiently factor a semiprime given a bit-permutation relating the factors?

Is it possible to efficiently factor a semiprime given a bit-permutation relating the factors? For example, suppose we have $n = p * q = 167653$; in this case, $p = 359 = 101100111_2$ and $q = 467 = ...
1
vote
0answers
226 views

Anti-prime sequence

I have permutation from $x$ to $y$. And how to make sequence which $d$ summed numbers from this sequence ISN'T a prime number. if we have sequence $x_1,x_2,x_3,x_4,x_5 \dots y$ than $d$ means : ...
2
votes
4answers
169 views

Is this a kind of Permutation?

I'm trying to design an algorithm to generate something that I don't know how exactly to call! Ok, I'm not a mathematician, I'm studying computer science and thought this would be a great moment to ...
1
vote
6answers
792 views

Why is the number of possible subsequences $2^n$?

If anyone here is familiar with the Lowest Common Subsequence problem, they probably know that the number of posibble subsequences in a sequence is $2^n$; $n$ being the length of the sequence. ...