Questions tagged [combinatorics]
Combinatorics is the branch of computer science and math that focuses on the enumerable arrangements of a finite set. This includes permutations, combinations, and partitions.
41 questions
1
vote
1
answer
220
views
How do I narrow down a search space if symmetries are equivalent?
I have an algorithm that runs a search through every combination of a 5x5 grid where each cell can have 3 values, looking to see which combinations meet certain conditions. This gives 3^25 naive ...
- 465
2
votes
3
answers
220
views
Eliminating combinations based on user input
I am stuck with this particular problem. To give context to the problem, I am developing a mobile app which helps with loading dangerous goods onto a truck. Ignore the size and weight of the dangerous ...
- 29
1
vote
1
answer
87
views
Algorithm for multi-dimensional maximisation
I would like to devise an algorithm that given:
An array of dishes with macronutrient information (proteins, fats and carbohydrates, in grams), constrained to a maximum of around 200 items.
A desired ...
- 119
1
vote
4
answers
246
views
How to find all combinations of all items in a set? [closed]
Let's say, there's a Product data-model. Product has the attribute - colour, which can, in this case, be red, black, yellow, white, orange. And which in total amounts to 5 different Products.
Now I ...
- 21
1
vote
4
answers
319
views
Software-design for algorithm engineering
I'm currently working on an program that solves a graph optimization problem.
I know the "standard" software-design principles like information hiding, modularization, etc. What I'm ...
- 151
-4
votes
4
answers
3k
views
Time efficient way to count pairs in an array whose sum is divisible by a specific number?
Given an array of integers, we want to find how many explicit pairs can be made such that their sum is divisible by 60. The pairs are not necessarily non-unique.
For example, let's say the input into ...
- 1,389
1
vote
2
answers
289
views
How to model combinatorial information in RDBMS
I need to model the persistence of combinatorial information. For example, suppose that the combination of 3 attributes (A, B, and C) are used to reference a given product. Besides that, supposed that ...
2
votes
2
answers
537
views
How to generate "meaningful combinations" from the set of characters?
There is a set of feasible characters, say ABCDEF. Combining some of them, I can generate some "meaningful" combinations, say CAFE. I want to gather all of them.
To do that, I can just "walk through" ...
- 149
-1
votes
3
answers
612
views
Birthday Paradox, Analytical and Monte Carlo solutions give two systemically slightly different results [closed]
I was doing a Monte Carlo implementation of the Birthday Paradox in Python and I wanted to check if the results where the same as in the analytical implementation of the same problem (As they should ...
4
votes
1
answer
480
views
Generating all possible permutations in the fox, goose and beans problem
I have learned graph theory, and am using it to solve the classic Fox, goose and bag of beans puzzle. If we consider that there are three locations for each of the fox (X), goose (G), farmer (F) and ...
- 205
2
votes
2
answers
369
views
Designing a builder as a compile-time state machine
I'm working on a text GUI library which comes with builders for UI components (Buttons, Panels, etc). I have a base class for these builders which I'd like to redesign so that meaningless component ...
- 1,190
0
votes
1
answer
161
views
Generating combinations without getting stuck in recursive calls
This question is about figuring the design of a recursive function that changes the state of a group of elements by processing one of them at a time, with the goal of reaching a desired state.
The ...
- 2,266
2
votes
1
answer
401
views
Calendar scheduling: home field constraints
I am working on a round-robin scheduling algorithm for sports.
The goal of the algorithm is to schedule all given games across different weeks, in the given fields and given game times. These are ...
- 2,266
2
votes
1
answer
272
views
Calendar scheduling: wait time between games
I am working on a sports scheduling algorithm with several different constraints, one (two) of them being a minimum and/or maximum wait time between games. Of the same team, that is.
So if Team Blue ...
- 2,266
1
vote
2
answers
195
views
Determining resource exhaustion beforehand
I guess this is a problem solving question but I am out of ideas, don't really know where else I can resort for help, and I need to solve this problem.
Essentially we have a set of consumers and a ...
- 2,266
-6
votes
1
answer
105
views
Set of items closest to the mean? [closed]
Given a set of N objects with assigned weights, how would we find the set of K objects that is closest to the average? The average being sum(weights) / N.
Also, how could we compute the next set ...
- 99
-1
votes
1
answer
135
views
How to calculate binomial coefficient C(n, r) modulo some prime power?
How to calculate C(n, r) modulo m, m is of the form p^a, where p is prime.
Here C(n, r) means n choose r. The range of n and r is large (of the order of 10^18) so it cannot be solved by calculating ...
- 1
0
votes
2
answers
333
views
Permutations for time in JSON
Let's say that I have a JSON file like at example below.
How would I go about finding all possible values of item combination time sums that exist between let's say 00:03:04 to 00:25:55 without ...
- 43
1
vote
1
answer
317
views
How to build an optimal tree given items costs and edge costs?
Given:
a list of 'leaves' that each have a cost,
the cost of creating an 'edge'
The constraint that a constructed tree node can at most have two children.
We now want to find the tree with the lowest ...
- 4,947
6
votes
2
answers
5k
views
Scheduling: balanced home/away round-robin tournament algorithm
I am trying to achieve a round-robin algorithm for sports scheduling that also guarantees a fair or balanced home/away rotation.
I based my algorithm on the round-robin scheduling algorithm:
def ...
- 2,266
4
votes
1
answer
353
views
Spreading objects in bags and bags' compartments
We have 10 bags. Each bag has 5 compartments numbered from 1 to 5. We have 100 objects to fill all the compartments and bags.
Compartment number x in a bag is identical to compartment of the same ...
- 177
2
votes
1
answer
622
views
Duval's algorithm, Lyndon words and de Bruijn sequence
First, I am not a programmer (yet) and I can only understand basic algorithms written in pseudocode (+Dijkstra, which is a little harder than others, for me). I have been trough logic, set theory, ...
- 21
0
votes
2
answers
1k
views
How do I write an algorithm to solve a set of 3 symbolic equations
Replace each symbol (letter) with a number so that the equations hold across all 3 equations. Solution should be able to solve the general case of any 3 equations. Can assume 2 terms summed to an ...
- 679
0
votes
1
answer
88
views
Why isn't this combinatorial solution equivalent to the recursive solution for finding the number of "paths"?
Here's the problem:
Given an m x n array, get the number of different paths from the top left corner to the bottom right corner, if you can only move down, right, and diagonally down & right.
...
- 105
9
votes
3
answers
431
views
Picking the most calorie-even arrangement of meals
Suppose I eat five meals a day, and since there are seven days in a week, I have recipes for seven of each meal, for 35 recipes in total. Each recipe has a calorie count. Each day must contain one ...
- 99
0
votes
1
answer
258
views
Validating combinations based on rule sets (or similar mechanism)
Let's say I've got many functions and each function accepts an unordered list (order does not matter). For each function I want to see if this list is valid based on certain rules (a knowledgebase ...
- 11
-1
votes
1
answer
173
views
Combinations of a password
I am trying to encrypt a password for my school project. Here is the process:
Let's assume that I have a string p (n characters long) which contains the password.
The program reverses the string and ...
- 21
1
vote
0
answers
480
views
Why does the last phase of Irving's Stable Roommates Matching work
Pertaining to the Stable Roommates Problem and the algorithm developed by Robert W. Irving.
There are two (sometimes broken into three) phases in which we may come to a stable pairing of everyone in ...
- 119
0
votes
1
answer
1k
views
The maximum number of induced cycle in a simple directed graph
Given a simple directed graph G=(V,E) an induced cycle is a cycle where no two vertices of the cycle have an edge that is not in the cycle.
(Chordless cycles are induced cycles with at lease 4 ...
- 101
1
vote
2
answers
2k
views
Algorithm to create all unique sets of the alphabet using arbitrary group sizes
I'm looking for an algorithm to help me out with a combination of combinations problem.
I have generated two lists of combinations of letters: (26 choose 6) & (26 choose 5)
My goal is to be able ...
- 121
0
votes
1
answer
184
views
Mapping match-up combinations into an integer
First of all, I want to say I wasn't sure if I should post this here or in math.stackexchange but I think the question is too programming-related to belong to the latter community. Definetly not a SO ...
- 2,266
4
votes
3
answers
186
views
Restricted randomization of a binary vector
Suppose I have a binary vector of sample size N with each of the two possible values (e.g., 0 and 1 occurring equally often).
For example, if N=10, the binary vector is: 0 0 0 0 0 1 1 1 1 1
Suppose ...
- 51
0
votes
0
answers
66
views
What algorithm to use to count realization of high combinatorics setup?
I'll use the MobA games to illustrate what I'm asking since it's easier to explain even tho I want to apply that algorithm to time series.
In a MobA game you have more than 100 characters and every ...
- 101
12
votes
1
answer
2k
views
Fast indexing of k-combinations
I'm revisiting an old problem that I was working on some time ago.
A typical scenario is "3 bits are set within an 8 bit integer", i.e. 00000111.
All unique combinations with 3 set bits can easily ...
- 785
3
votes
1
answer
6k
views
Algorithm to compute k-permutation without repeating and no duplicates
I have a set of integers, for example 1..20 and I want to get all possible combinations of that set drawing 5 numbers.
So each combination has 5 numbers from that set of integers. But I don't want ...
- 133
1
vote
2
answers
850
views
Given an array of n bits, how to generate every permutation with i 1's and n-i 0's?
It's simple enough to brute force a collection of strings and then filter for every occurrence with the required count of 1's.
As n increases the number of possible permutations becomes very large, ...
- 11
0
votes
0
answers
363
views
Domain analysis for discrete values - ON and OFF points in these cases
Following my previous question (with great answer from Bart van Ingen Schenau), I noticed a discrepancy I could not wrap my head around:
Bart mentioned that:
The point ON the boundary is by
...
- 533
2
votes
3
answers
2k
views
Domain analysis - why OFF points are inside of the domain when the border is open
I have asked on a few other sites, no response but it must be something silly as many authors mention in their books.
Here is the best text I found:
My ultimate question is:
Why the OFF point lies ...
- 533
7
votes
3
answers
9k
views
Number of strings containing a specific substring
I've seen numerous questions (and answers) concerning the number of binary strings (e.g "10010" containing some binary substring (e.g "00"). I'd like to know if there is a way to generalize this:
...
- 79
0
votes
1
answer
829
views
Number of sequences when no adjacent items can be the same
I came across this one problem,
There is a particular sequence only uses the numbers 1, 2, 3, 4 and no two adjacent numbers are the same.
Write a program that given n1 1s, n2 2s, n3 3s, n4 4s will ...
- 3
0
votes
1
answer
3k
views
How do I create every permutation [closed]
I have a list of letters, this is just an example list:
['a','b','c','d','e']
How do I compute every combination of the list? The letters cannot repeat, for example.
a,b,c,d,e
a,c,b,d,e
a,c,d,b,e
a,...
- 19