0
votes
0answers
27 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
37 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
32 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
99 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
205 views

Count swap permutations

Given an array A = [1, 2, 3, ..., n]: ...
0
votes
1answer
50 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
42 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
62 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
72 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
46 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
54 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
24 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
92 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
242 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
318 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
79 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
88 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
3answers
136 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
179 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
84 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
62 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
481 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
84 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
92 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
101 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 ...
0
votes
0answers
119 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
193 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
166 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
118 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
292 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
165 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
367 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
147 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
776 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
402 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
222 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
758 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. ...
3
votes
2answers
1k views

Can someone explain the algorithm for composition of cycles?

Let $\sigma=(1\ 3),\ \tau=(2\ 4\ 5),\ \pi=(2\ 3\ 4) \in S_{5}$. Find $\pi\circ\tau\circ\sigma$. I know the solution is $(1\ 4\ 5\ 3)$. What i'm doing now is writing the permutations in the ...
4
votes
1answer
1k views

Finding all n×n permutation matrices

If I have a doubly stochastic matrix, how can I find the set of all basic feasible solutions? Here's Wikipedia on doubly stochastic matrices.