Questions tagged [combinatorics]

Deals with combinations of entities belonging to a finite set in accordance with certain constraints.

Filter by
Sorted by
Tagged with
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 ...
barrelquentin997's user avatar
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, .....
Jingyang Wang's user avatar
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, ...
123prior's user avatar
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 ...
Thando 's user avatar
-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 ...
stats_noob's user avatar
  • 5,347
-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)...
Robert Puscasu's user avatar
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 ...
valerii15298's user avatar
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 ...
user1373317's user avatar
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 ...
bit_n's user avatar
  • 31
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 ...
Script Raccoon's user avatar
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 ...
user8593752's user avatar
-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 ...
zdm's user avatar
  • 511
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 ...
Steve Bennett's user avatar
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: [[...
Helena Vidakovic's user avatar
-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, ...
Bastian Borum Andersen's user avatar
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 ...
qpexxtt's user avatar
  • 11
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 ...
Vinod's user avatar
  • 4,208
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 ...
caunuk's user avatar
  • 1
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 ...
Jason Christian's user avatar
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) ...
Nicolás Rivera's user avatar
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 ...
physicsfrog2's user avatar
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 ...
Eragonrider's user avatar
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 ...
codinguniverse's user avatar
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 ...
Dave's user avatar
  • 8,069
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 ...
Fyodor Rogov's user avatar
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 ...
duckrabbit's user avatar
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 ...
Dries's user avatar
  • 522
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 ) ...
Daniel Bauer's user avatar
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/...
Hal's user avatar
  • 49
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 ...
PingFloyd's user avatar
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: ...
psquid's user avatar
  • 759
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 ...
willeM_ Van Onsem's user avatar
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 ...
Steven_Huang's user avatar
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 ...
Solaxun's user avatar
  • 2,712
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 ...
Meister der Magie's user avatar
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 (...
H4z3's user avatar
  • 129
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 ...
Justin Greenough's user avatar
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 ...
TMC's user avatar
  • 75
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 ...
V.Petretto's user avatar
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 ...
Dark's user avatar
  • 120
-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, ...
Chotu's user avatar
  • 27
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 ...
Max Pierini's user avatar
  • 2,097
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 ...
figgy's user avatar
  • 31
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 ...
KashmirWalla's user avatar
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 ...
Sujith Srivardhan Arram's user avatar
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 ...
SomeGuy30145's user avatar
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 ...
SteamyTowel's user avatar
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 ...
timmtamsar's user avatar
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 = ...
SomeGuy30145's user avatar

1
2 3 4 5
47