# Questions tagged [combinatorics]

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.

487 questions
Filter by
Sorted by
Tagged with
98 views

### Program to generate a tree of permutations

There is a computation I'm doing with permutations (permutations of varying length of an entire interval [1,N] for some N) in python that I feel could be faster. ...
• 205
79 views

### Effective encoding-decoding chain determination (time optimization)

Could you please help with speeding-up this code? Input: UTF-8 text (encoded 1-3 times from known pool of encodings). Every time was encoded and decoded by random encoding from pool. Original was koi8-...
698 views

### Find all combinations of length 3 whose sum is divisible by a given number

I came up with a suitable solution to a HackerRank problem that failed because the execution took longer than 10 seconds on lists that were of very large size. The problem: Given a list ...
905 views

### Print all "balanced" sequences of 'A' and 'B'

the aim of the code below is to print all balanced sequences with equal number of 'A' and 'B'. A sequence is balanced if every prefix of length $\geqslant 4$ is balanced. A prefix is balanced if the ...
• 441
51 views

### Check if two semistandard Young tableaux are compatible

I have a question about how to check if two tableaux are compatible (will define below). Here we only consider tableaux of rectangular shape. A tableau is called semistandard if its rows are weakly ...
• 183
80 views

### Iterating over all simple unique cycles in an undirected graph in Java - brute-force approach

This post is about an Iterator iterating over simple loops of an undirected graph. In the above graph, the cycle $\langle 1, 2, 3, 4, 5, 3, 1 \rangle$ is not ...
• 26.6k
36 views

### Query for sequential column permutations in SQLite

For dummy's sake, let's say that I have a database with columns text, ind and sentid. You ...
• 495
56 views

### An algorithm that minimizes the number of ingredients necessary

I am working on a code that will minimize the number of ingredients necessary to make some dishes. Each dish can be prepared in an arbitrary large number of ways, with combinations of two ingredients. ...
111 views

### Boolean evaluation

Given a boolean expression consisting of the symbols 0 (false), 1 (true), & (AND), | (OR), and ^ (XOR), and a desired boolean result value result, implement a function to count the number of ways ...
1 vote
24 views

### Scheme Procedure for Permuting Characters in a String

The following is a Scheme procedure to permute the characters in an input string. It outputs permutations of all lengths from 1 character up to the number of characters in the input string. ...
• 277
1 vote
569 views

...
• 111
101 views

### A more elegant way to uniformly sample from non-negative integers with a fixed sum

Given a positive integer n, I would like to randomly output n non negative integers that sum to ...
• 191
1 vote
240 views

### Printing subarrays ⚡

I was trying to to print all subarrays of an array in quadratic time. Here is my code: ...
365 views

### Subarrays with length

You are given an array A of length N (where N is as large as 2×105). All elements of the array are positive integers less than or equal to N. Determine the count of subarrays (contiguous subsequences) ...
147 views

### Pascal's triangle solution in Python code

I have solved the pascal's triangle problem. I am not good at writing efficient programs, hence any suggestions/ comments shall be welcomed. ...
83 views

### Subset Product Algorithm

Subset Product is an NP-complete problem and is my favorite problem. So, I've written a slightly smarter way of solving the problem. Will performance impact matter if I use multi-cpus and my GPU? Do ...
• 431
1 vote
29 views

### Iterating over de Bruijn sequences in JavaScript

I have just put this code together, it's not quite the most elegant but it seems to get the job done. Does it seem alright? I could not find anywhere a "de Bruijn sequence algorithm", so I ...
• 351
1k views

### Find non-overlapping pairs of elements in a list whose difference is less than some given threshold

I have the following task: Let us have a list (denoted by L, and for simplicity, the elements come from the interval [0,1]). We are given a parameter (denoted by C), and we want to find as many pairs ...
• 153
221 views

### Count five-digit octal numbers with alternating even and odd digits, without repeated digits

I need to find the number of five-digit octal numbers in which all digits are different and no two odd or even digits are adjacent. My code below gives the correct answer, but I'm not satisfied. Can ...
• 53
200 views

### Given a number of points, generates all paths between all points that does not overlap

I wrote this code in 4 days, I want to see if I can optimize this code some more, and have some suggestion on what can I improve. This code takes in any number of points then naming them ...
77 views

### Calculate the largest palindrome under x-digits multiplication

Here is my Rust program: ...
• 11
1 vote
117 views

### Minimum re-labeling to make an array as close as possible to another one

I have an array with integer labels in [0, n-1], say arr1=[1, 0, 3, 2] with n = 3. And then I have another array again with integer labels in [0, n-1], say arr2=[0, 0, 2, 3]. How can I find the ...
• 13
1 vote
225 views

### Calculating all combinations from arrays AND (arrays OR floats)

Context: My question comes from needing to iterate different np.arange arrays. The main motivation is to calculate all the possible combinations between the arrays, ...
• 163
1 vote
77 views

### Absolute Permutation | Hacker Rank: Any way to make this python code faster without changing it's whole logic?

https://www.hackerrank.com/challenges/absolute-permutation/problem I know that if you work out the math and logic first, the algorithm can be simplified greatly (shifting indices), but is that the ...
141 views

### Finding possible combinations for n<7 with rust

I am trying to learn rust and as such have been redoing some of the challenges on project Rosalind. This one relates to the challenge Enumerating Gene Orders. ...
1 vote
28 views

### Mean and variance of element-wise distances in a set of multi-dimensional arrays in Matlab - follow-up

This is a follow-up question for Calculate distances between two multi-dimensional arrays in Matlab and Mean and variance of element-wise distances in a set of multi-dimensional arrays in Matlab. For ...
• 3,666
630 views

### Generate possible combinations by range and length

I am learning Haskell and I implemented a recursive function that generates possible strings by length and array (e.g. ['a'..'z']): ...
• 143
52 views

### Increase speed of lapply function identifying the sum of all existing combinations

I have a dataframe of cases that score 0-1 on a group of binary attributes. What I want to do is extract all possible ombinations of attribute triplets (e.g. A/B/C, A/B/D... out of A-E) and then sum ...
• 163
146 views

### In how many different ways can a group of 9 people be divided into 3 groups, with each group containing 3 people?

To divide 9 persons into 3 groups, when the ordering of groups is not important can be done in (9C3 * 6C3 * 3C3) / (3!) = 280 ways Here, we divide by (3!) because the ordering of 3 groups is not ...
36 views

### Loop through the nearest switch and deletion neighbours of a Boolean assignment

My goal is to look for nearest neighbours in a Boolean-assigned mapping (a Python dictionary). For this purpose I'm looping through the candidates, starting from those with the closest distance. The ...
613 views

### Generate all subsets of a set

The goal of the function below is to generate all subsets of a given set, i.e. a collection of sets that contain all possible combinations of the elements in the set. Note that for my application I do ...
84 views

### Building a tree containing all permutations of arithmetic expressions given some numbers

Given any series of numbers, for example 1,2,3,4,5 and given the arithmetic operands + - * / including parenthesis, what would be the most optimal way to build a tree that contains all permutations ...
• 133
217 views

### Find all combinations of numbers of a set that add up to a given target - avoid for loops

I am thinking about the following problem: Consider a 3-numbers lock, i.e. a lock which has three little number wheels that opens whenever the sum of these three numbers equals 75. I know, this doesn'...
• 141
97 views

...
533 views

### Rust implementation of next-permutation

I am translating this next permutation algorithm in C++: ...
1k views

### Generate all possible unique combinations of positive numbers these have sum equal to N

This is my function to generate all possible unique combinations of positive numbers these have sum equal to N. For example: If the input is 4 The output should ...
• 315
1 vote
456 views

### Fast brute force numpy array combination

I want to extract the combinations of numpy arrays in this way: ...
• 265
1 vote
977 views

### Find All Permutations of String in Scala

I created the following function, permutations, to produce all permutations of a List[A]. Example: ...
• 3,183
206 views

### Next different permutation in C

This is a program which you can get the next "different", i.e. elements in A[] can be identical, permutation at each call. I've written a C++ program for ...
• 531
717 views

### Generating permutations fast

I run into a performance bottleneck in a program. I have to generate all permutations for a given sequence with size up to n=11. My code: ...
• 3,036
82 views

### Count the different positions reached in a cycle of permutations

I have come across a problem on cyclic permutations. It is about swapping numbers around. It starts out with input N < 100,000 which makes the first N natural numbers as orders: 1 2 3 ... N-1 N ...
58 views

### Generating random permutation with forced change of order (Secret Santa)

I wrote this function to generate random permutation of input vector, while making sure every element has switched place (for a Secret Santa like purpose). ...
• 123
83 views

### Ruby: possible Poker holds for a hand of length n

Hello everyone and thanks in advance for taking the time to read my post!! In the process of learning Ruby, I'm writing a video poker machine that analyzes hands represented by arrays of Cards, like ... 263 views

### Creating some Loaded Dice to make our board game fairer

Some friends and I were playing a board game and decided that the random dice rolls just weren't fair! So we came up with a scheme for making the rolls slightly more evenly distributed, and I ...
• 2,290
1 vote
45 views

### Summing Sequence with Combinatorics

I am looking for help for two things. proof of correctness (the tests have passed, but I do not now how to prove it correct) Improvements on the Algorithm Efficiency. The algorithm goes through 2 ...
• 315
180 views

### How to find the next sequence of integers?

I was thinking of the following problem: List all sequences $a_1, a_2, a_3, a_4, a_5, a_6, a_7$ of positive integers where $1 \le a_1 < a_2 < \ldots < a_7 \le 39$. For any sequence ...
636 views

### Best Algorithm for solving USACO: Photoshoot - Python

I was trying to solve this problem with Python 3.8. I couldn't find a way other than to brute-force calculate all the possible permutations then check which permutation was valid. The program works ...
486 views

### Combinatorics, C++ and optimization

Note: I have a working solution, my question is about optimization and other approaches. Problem Description Hello, I'm re-writing an old program I made that solves nonograms. As part of solving it, I ...
1k views

### Simple generic cartesian product in C++

The idea is to take a sequence of sequences (of the same type) and use tuples of [iterator, current index, sequence size] to keep track of the current state, such ...
• 195
1 vote