Questions tagged [combinatorics]
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.
474
questions
3
votes
2
answers
60
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.
...
- 61
0
votes
1
answer
64
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
0
answers
15
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 ...
- 299
5
votes
2
answers
682
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
5
votes
2
answers
185
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
5
votes
1
answer
171
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 ...
- 53
0
votes
0
answers
73
views
1
vote
1
answer
108
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
1
answer
97
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
1
answer
58
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 ...
2
votes
1
answer
71
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.
...
- 121
1
vote
0
answers
21
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,302
3
votes
1
answer
315
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']):
...
- 133
0
votes
1
answer
48
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
2
votes
1
answer
121
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 ...
- 123
2
votes
0
answers
31
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 ...
- 121
3
votes
3
answers
326
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 ...
- 131
3
votes
1
answer
61
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
4
votes
1
answer
118
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
0
votes
2
answers
66
views
4
votes
1
answer
323
views
Rust implementation of next-permutation
I am translating this next permutation algorithm in C++:
...
2
votes
2
answers
635
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
1
answer
169
views
Fast brute force numpy array combination
I want to extract the combinations of numpy arrays in this way:
...
- 265
1
vote
2
answers
664
views
Find All Permutations of String in Scala
I created the following function, permutations, to produce all permutations of a List[A].
Example:
...
- 3,173
0
votes
2
answers
98
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
-1
votes
1
answer
365
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:
...
- 2,976
2
votes
1
answer
67
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
...
- 21
2
votes
1
answer
49
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
0
votes
3
answers
61
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 ...
josh-frank
3
votes
2
answers
207
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 ...
- 1,998
1
vote
1
answer
42
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
2
votes
1
answer
118
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 ...
- 21
7
votes
2
answers
470
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 ...
6
votes
1
answer
445
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 ...
- 161
6
votes
1
answer
890
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
2
answers
121
views
Combinatorics challenge solved it Python
The easiest way to explain this problem is to show these two test cases:
...
- 809
5
votes
1
answer
180
views
Permutations in C
I searched on the internet for an algorithm for permutations in C and I found the following function:
...
- 469
8
votes
2
answers
221
views
Method to generate a List<string> containing permutation of an input string
I'm working to understand Big O notation. As such I'm going through examples and the algorithm below generates the permutations for a given input string which contains only distinct characters. IE no ...
- 3,477
4
votes
1
answer
69
views
Filter out unwanted substrings while generating all possible relevant substrings
Write a Program that determines where to add periods to a decimal string so that
the resulting string is a valid IP address. There may be more than one valid IP address
corresponding to a string, ...
- 173
1
vote
1
answer
155
views
Generating all variations of M*N matrix containing boolean values
I've implemented an algorithm that generates all variations of a matrix of size \$M*N\$. My approach is that I see a matrix as a list where the position of elements can be calculated from the position ...
- 374
2
votes
1
answer
134
views
Time and Space Complexity of Leetcode Problem #31. Next Permutation
The question is as follows: Given a collection of distinct integers, return all possible permutations. Example:
...
- 21
2
votes
1
answer
45
views
Printing all permutations of digits of a number
So, a long time ago, I've made a program that prints all the permutations of digits of a number in AEC. Now I have refactored it a bit, and I would be interested in what you think about it.
...
- 385
2
votes
2
answers
111
views
Performance is too low, online compiler wants a faster way to find all possible combinations of k numbers out of 1...n
I have to find a method (using backtracking) to list all possible combinations, in lexicographical order,of k numbers out of the interval [1,n].. duplicates are not allowed. i.e: input: 5 3output:1 2 ...
- 83
2
votes
1
answer
34
views
An r-length permuter in c++
In relation to the question I asked here, I myself came up with an answer. I would like constructive criticism and tips to improve it to make it efficient like the other answers that have been posted.
...
- 342
2
votes
1
answer
79
views
Finding Possible Strings from Series of Numbers
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters is done just like they are arranged on a ...
- 171
3
votes
1
answer
82
views
Finding permutations efficiently
I have the following:
A set of K time-series in a numpy array with dimensions T x K.
A set of ...
- 197
7
votes
3
answers
227
views
Refactor the code which performs "cross-product", "reduce", "product of list" and "sum of list"
I have come up with a sequence of steps to find the maximum product of y positive numbers which add up to x. But the program is ...
5
votes
4
answers
348
views
Check whether a permutation with one fixed point can be rotated into one with two fixed points
A friend gave me the following riddle:
Given n people with n distinct names, you place n names tags on a round table with n seats. If the n people now sit at those seats randomly such that exactly ...
- 103
3
votes
3
answers
104
views
BFF Word Finder
Inspired by this question on Puzzling.StackExchange, I've decided to write a small python script that determines if a word is a BFF Word. Below are the parameters, solved by Puzzling user Stiv, also ...
- 9,466
2
votes
1
answer
52
views
Count number of ways that sequences contain at least one of the given subsequences
Peter loves dices and some special numbers. Therefore he thrown dice n times and concatenate the numbers. Compute the probability that if he throws 6 to 27 seven times dice and concatenate the numbers,...
- 21