Questions tagged [combinatorics]
Deals with combinations of entities belonging to a finite set in accordance with certain constraints.
2,331
questions
1
vote
1
answer
66
views
How to create N subsets with x0,..,xn elements, without replacement, so that each subset has the mean of superset?
I'm looking for advice what to google/efficient ways how to sample without replacement a superset containing M elements into N subsets with x0,...,xn elements, where the sum of all elements of subsets ...
0
votes
2
answers
80
views
Selecting permutationally-unique elements of a symmetric tensor
I have a code which creates a numpy array A of shape (m, m, ..., m) where there are n copies of m. By construction, this array is a symmetric tensor (in the mathematical sense), meaning that A[i, j, .....
2
votes
0
answers
38
views
Generating the dual of a non-crossing partition
Consider the set of numbers S = [1, 2, ..., n]. A partition divides S into blocks. These blocks are non-crossing if there do not exist elements a < b < c < d with a and c in the same block, ...
0
votes
2
answers
88
views
Eliminating Some Combinations From a List of Lists in Python
The code below gives all possible combinations of 6 numbers from 1 to 52. It gives these combinations in a list of lists. However I want to eliminate some of these combinations.
The combinations I ...
-1
votes
7
answers
319
views
Counting the Number of Combinations that Match a Certain Condition
Here is my problem:
There are 5 candies (1,2,3,4,5) - each candy has the same "value" associated with its number (i.e. candy_1 has value=1, candy_2 has value=2, etc.).
In the future, I ...
-1
votes
0
answers
25
views
Does anyone know a fast way to compute if C(n,k) is divisible by n when k is large
Given $$n,k$$ two large natural numbers and 1<k<n, the formula for calculating n choose k is: C(n,k) = n! / ((n-k)! *(k)!)
For a given n, iterating over k from 1 to n, how can you find one C(n,k)...
1
vote
1
answer
37
views
all possible distinct non decreasing sequences(combinations) of numbers to reach the given sum with quick performance
I need to count all possible combinations of numbers to reach the given sum.
They should be non decreasing(every next number should be greater or equal to previous one).
Here is JavaScript code with ...
1
vote
1
answer
24
views
Combinatorial Row-Wise multiplication of two DataFrames in Python
Suppose I have two dataframes A and B:
A and B can be represented as numpy arrays, both of shape (N,M) i.e. N rows, M columns.
What is the fastest way to combinatorially sum-product every row of A ...
0
votes
2
answers
38
views
Applying graph data structure to recipes in a game about combining elements
I am designing a game where the player combines two ingredients to create a new element, which can then be used as an ingredient to create even more ingredients. It really seems that a graph structure ...
3
votes
2
answers
127
views
Efficient computation of the set of surjective functions
A function f : X -> Y is surjective when every element of Y has at least one preimage in X. When X = {0,...,m-1} and Y = {0,...,n-1} are two finite sets, then f corresponds to an m-tuple of numbers ...
3
votes
1
answer
241
views
Placing 1 in n x n board of zeroes, such that all rows and all columns have same parity
I am working on the following task:
Given a 𝑛 x 𝑛 board, and 𝑚 buttons on it, press at least one button in such a way that the count of the pressed buttons in each row and column is of the same ...
-1
votes
1
answer
101
views
How to find all partitions of k positive numbers that sum to n with all permutations
For k=4 and n=6, we have
1 + 1 + 1 + 3 = 6
1 + 1 + 2 + 2 = 6
which can be obtained from the Triangle of partition numbers.
But for 1 + 1 + 1 + 3 we can have 3 more permutations (4 in total) as ...
1
vote
4
answers
104
views
Algorithm to repeatedly pseudorandomly select from a set, without frequent repeats
I have an array of things (conceptually a set, but let's implement as an array), say [A, B, C, D, E, F].
I need an algorithm that can pseudo-randomly pick an item from the array such that no item will ...
1
vote
1
answer
74
views
Combinatorics variations, not combinations
I have 3x3 matrix, and its elements can have values -1, 0 or 1. I want to get all the possible variations, so the total number of results (all 3x3 matrices) should be 3^(3*3)=19683.
Example result: [[...
-1
votes
2
answers
63
views
Random sampling of n lists of m elements in python
I wrote this code which creates all combinations of n lists of m elements in python, samples a given number of unique combinations (max possible or 1000) and outputs it in excel. It basically works, ...
0
votes
0
answers
128
views
Find n indices such that their sum is equal to k, and the sum of the elements at these indices is minimal
You are given n arrays. Each consists of non-negative integers in ascending order. You need to find n indices such that their sum is equal to k, and the sum of the elements in these arrays at the ...
2
votes
3
answers
95
views
All permutations with replacement in Julia
Suppose there are only 3 students. Let R and G be the colors of uniforms a student can have. Let S be the set of colors(permutations) that students wear in a particular day. How can I generate the ...
0
votes
1
answer
38
views
Shuffling a vector in Matlab with constraints (a specific number of 2-back repetitions)
I'm setting up a Matlab program where people will see a series of 15 words (e.g., 'dog', 'cat', 'fish', 'goat', etc.). One word will be presented per trial, and the full series of words will repeat 40 ...
0
votes
2
answers
223
views
Calculating the Number of Ways to Prepare Cereal Bowls for N People with Milk First (Algorithm Request)
I was given the following:
Rigel is a cereal lover and a massive philanthropist. Every day he has N numbers of people that
he needs to feed. As a cereal lover, He wants to spread his love for cereal ...
0
votes
0
answers
98
views
Find all possible complementary combinations of subgraphs within a graph
Suppose I have a graph, in my case I have created it using networkx as followed:
import networkx as nx
Graph = nx.Graph()
nodes = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
Graph.add_nodes_from(nodes)
...
0
votes
1
answer
52
views
Solved Now: Limiting Permutations Python Solution
The solution was made by commenters: saving the post incase it helps anyone else out.
I am currently attempting to write a python script to fill a useable matrix that would include all possible ...
2
votes
1
answer
140
views
The multiplicative formula for calculating the Binomial Coefficient in Java for large n and k values modulo 10^9 + 7 outputs incorrect value
I have an assignment that asks to create a program that can calculate the binomial coefficient given any n, k such that 1<=k<=n<=2000. I am able to accomplish this for small n, k, but for ...
0
votes
2
answers
75
views
Computing combinations of variables
I am computing combinations of variables in Stata and I have four poverty variables below:
improved_toilet 0 "No" 1"Yes" // 1 means household lacks toilet,0 means no lack
...
2
votes
1
answer
122
views
Given a string s and an integer i, create all contiguous substrings of s, sort & then concatenate them, and find the letter at index i efficiently
For a given string say dbac, the possible substrings are [d,db,dba,dbac,b,ba,bac,a,ac,c] . Sort them and concatenate to a string: aacbbabaccddbdbadbac. Find the character at a given index. In this ...
0
votes
2
answers
111
views
Cartesian product without commutative tuples
N iterators are given. Task is to get the cartesian product of those iterators (in the form of a collection of tuples each N elements wide) while also discarding tuples that can be derived from other ...
1
vote
1
answer
73
views
Number of ways to color houses with no 2 equal colors next to each other and symmetry constraint
There are n houses along the street, and we need to color every with one of 3 colors but there are 2 constraints:
Adjacent houses need to have different colors
Symmetric houses cannot have the same ...
7
votes
3
answers
182
views
Efficiently enumerating multinomials with constant sum - R
Let's say I have an N-side dice with non-uniform probabilities for each side and I throw it M times. Now instead of observing the individual outcomes, we only observe the sum.
I have to code the ...
1
vote
2
answers
47
views
Iterating over the cartesian product of a list of lists
The problem is a generalization of the folling simple problem:
Given 3 lists of elements, I can loop over the pairings between all 3 lists by folling pseudocode:
foreach( element1 in list1 )
...
4
votes
4
answers
161
views
Generate permutations without duplicated elements in both rows and colums
I have 4 teams (A-D) and 4 games (1-4).
GOAL: I want to generate a dataframe (4,4) :
that has 4 rows for 4 rounds
that has 4 columns for 4 games
I want to attribute a different team to each column/...
1
vote
0
answers
41
views
Modular Mixed-Radix Gray Code Generation with Hamming-weight restriction
For a project I need to enumerate all vectors of F_q^n (the vector space of dimension n over the finite field with q elements, where q is a prime number) in a special way.
I need to enumerate them in ...
0
votes
1
answer
91
views
How to efficiently generate all interleavings of lists in Haskell?
What's the most efficient way to generate all lists obtained by interleaving the elements of a given list of lists in Haskell?
https://stackoverflow.com/a/41929156 proposes the following code:
...
0
votes
1
answer
82
views
Distributing Bath money over n people
I found the following problem online and was intrigued to solve this in Haskell.
Given money X Baht and N people where we will distribute the money as
follows... 1st turn: Give the first person 1 ...
0
votes
0
answers
22
views
combinatorics problem-number of game outcomes
There are m concentric circles, and n straight lines through the center point, intersecting each concentric circle at 2n points. Let the outermost two adjacent intersections be A and B. Alice and Bob ...
4
votes
2
answers
314
views
Solving a Modified Subset Sum - Search Algorithms
I have a problem which is similar to a subset sum but with a few modifications:
Subset Sum:
Find all ways the following list can sum to 16:
[2,9,40,2,404,12....]
My Problem:
Find all ways you can ...
0
votes
0
answers
88
views
Distribute people evenly among groups and tasks (Social Golfer Problem)
I need to write a program that sorts people into groups.
To give a little context:
The aim of the program is to create an equitable distribution of tasks and people for a school trip. Every day the ...
2
votes
2
answers
201
views
Determine the number of ordered pairs of prime numbers (p, q) such that N = p^2+q^3 is such that each digit from 0 to 9 appears exactly once
I have to write a program such that can determine the number of ordered pairs of prime numbers (p, q) such that when N = p^2+q^3 is written in decimal, each digit from 0 to 9 appears exactly once (...
0
votes
0
answers
13
views
Find all connected subgraphs of a specified size, not just induced subgraphs, using networkx
The subgraph method offered by python's networkx generates induced (full) subgraph given a subset of vertices. I have been unsuccessful in finding a method for delivering all subgraphs (yes, there ...
0
votes
2
answers
60
views
Valid Comparisons of Multiple Grouping Variables
TL;DR: I am looking for a more generalized solution for a combination problem which I partly solved with my not so good coding skills.
Brief Description
Imagine you have a dataset with some ...
1
vote
1
answer
54
views
Find a requested permutation given an index number
I have a list like this: a,b,c,d,e,f,g. And I want to calculate the permutation number 57 in a list of two elements ( in this case is f,g ). But I do not want to permute the list 57 times, I want a ...
3
votes
2
answers
305
views
Scheduling a set of matchups so each participant's matchups aren't too close together
Main goal:
To create a JavaScript function that will help each fighter to have a better sequence of fight. Some of the fighters have seven entries in the whole event. In the fighter1 and fighter2 ...
-3
votes
2
answers
146
views
How do I return a list of all combinations of column names in SQL, when the output for each of those column names equates to 1 (TRUE)?
For example, here's what a sample dataset looks like in which ID, A, B, C are my column names:
ID A B C
L1 1 0 1
L2 1 1 1
L3 0 0 1
Here's what I would like the output to show, ...
0
votes
2
answers
90
views
Variations with repetition of r integers in {0...k} that sum to u
Given a set of integers x = {0...k}, I need to find the most efficient algorithm to generate all variations with repetition of r integers x that sum to u.
I thought to
from itertools import product
...
3
votes
0
answers
71
views
How to generate a given number of triplets from a set of items while balancing number of pairs and items in triplets?
We’re trying to design an experiment where subjects choose the odd-one-out among triplets of 60 trait words (trait1, trait2, trait3). At some point, we will probably want to down sample all 34,200 ...
1
vote
1
answer
36
views
GNU-parallel combinatorics, as command-inputs, without printing to terminal
I have two groups of numbers that I would like to create commands from; {37..43} and {37..43}. I would like the commands to take in a number from group_1 and group_2 such that the number from group_2 ...
1
vote
0
answers
66
views
How to find disjoint paths between a set of source and target cells in matrix?
I have a matrix with a set of colored nodes. Each node has is a member of a pair of the same color. The goal is to connect each node with its pair so that all the paths do not intersect. Only ...
1
vote
2
answers
99
views
Given an m * n grid, each edge must be colored. However, there are constraints
Given an m * n grid, each edge must be colored. However, there are 2 constraints:
Entire grid must use only 3 unique colors
Each square in the grid must be colored using exactly 2 colors (2 edges per ...
0
votes
0
answers
94
views
Combinatorics: Efficiently Solving with Pulp - Large Dataset Issues
I have the below pulp implementation that assigns the best product (a or b) to each factory in data (1,2,3,4 or 5) with no issue, however after around 50 factories pulp seems unable to complete the ...
0
votes
1
answer
38
views
General Algorithm to optimize order of events while requiring the minimum number of changes
I am trying to optimize the order of wedding photos with the family and others that need to be included. in order to keep the chaos and people wrangling to a minimum I am trying to optimize the order ...
0
votes
1
answer
84
views
How to find the minimal amount of ordered pairs for specific counts of elements?
I have around 350 sets of ordered pairs (representing firms). All firms have properties, which I can represent numerically as (x;y), where x is a natural number between 1 and 5 and y is between 6 and ...
0
votes
2
answers
120
views
Scipy Optimize Minimize For Combinatorics - Integer only solutions
I have the below code that tries to assign the best product (a or b) to each factory (1,2,3,4 or 5).
How do I set constraints/bounds so that it only uses the integer values 0 or 1?
e.g I have set x0 = ...