What's the deal with Deno? We talk with a major contributor to find out. Listen now.

# Questions tagged [permutations]

The tag has no usage guidance.

173 questions
Filter by
Sorted by
Tagged with
34 views

### Simple incremental hash funcion

I have permutations: 4 1 2 5 3 4 3 2 5 1 numbers can be order magnitude of 1000 (fits in two bytes) I want compute 32 bit (or better 64 bit) hashes, it should be ...
42 views

### How do you write a python\pseudo code that generates all pair permutations?

What would be a good pseudo code or Python 3 code for the following permutations problem? Let us define a n-permutation as a bijective function $\pi: \{0,...,n-1\}\rightarrow \{0,...,n-1\}$ and ...
36 views

### finding the combinatorial solutions of series and parallel nodes

I have n nodes, and I want to find the (non duplicate) number of possible ways in which these nodes can be combined in series and parallel, and also enumerate all the solutions. For example, for n=3, ...
55 views

### Finding index of $p_{k}$ element in the original sorted array if elements were to be removed using a specific condition

Consider a sorted list of numbers $C_{0}=\{0,1,2,3,...,n-1\}$ from where one element will be eliminated at each step. We are also given a value $L$ in $[0, 1)$ and let the indexing start from $0$. ...
66 views

### Math behind leetcode problem 47 permutations II

Please tell me why the expression i>0 && nums[i] == nums[i-1] && !used[i-1] works on getting unique permutations. And what is the math behind it? ...
60 views

### Given $n$ unique items and an $m^{th}$ normalised value, compute $m^{th}$ permutation without factorial expansion

We know that the number of permutations possible for $n$ unique items is $n!$. We can uniquely label each permutation with a number from $0$ to $(n!-1)$. Suppose if $n=4$, the possible permutations ...
88 views

We have N tasks that need to be scheduled for processing. Each task consists of two parts that need to executed in order. The first one is guarded by a mutex and ...
44 views

### What is the maximum number of indices one can create on a table with N columns?

Say, I have a database table with $N$ columns. What is the (theoretical) maximum number of indices I can create on that table? For $N = 1,2,3$ it's easy enough to calculate the answer $(1, 4, 15)$, ...
20 views

### encrypt with permutation ciphers

I came across this question: You are given a permutation cipher defined by the bijection t: N -> N where, ...
30 views

### Reverse of In-place algorithm for interleaving an array

How to do the reverse process of In-place algorithm for interleaving an array question?
55 views

### Minimize function on permutations

Problem: Consider $[k] = \{ 1, 2, \dots, k \}$ and function (of two arguments) $f: [k]^{2} \rightarrow \mathbb{N}$ that is defined for all $(n, m) \in [k]^{2}$ (all ordered pairs of numbers from $[k]$...
38 views

### If I walk through list and delete every out-of-order element I come across, on average how many elements will be left?

I have a uniformly randomly permuted list of length $n$. I walk through the list element-by-element, and delete an element if it's out-of-order (compared to the previous in-order elements of the list)....
42 views

### Pseudo code of recursive method of printing all permutations of $n$ given integers

I really don't understand this pseudo code. The function prints all permutations of $n$ given integers, assuming that all numbers are different. Is there a way to explain this code more easily as I ...
42 views

224 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, ...
117 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 ...
181 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 ...
88 views

124 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 ...
66 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 ...
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$. ...
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 ...