Questions tagged [combinatorics]
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.
461
questions
2
votes
1answer
93 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 ...
2
votes
0answers
30 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 ...
1
vote
0answers
33 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 ...
3
votes
1answer
48 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 ...
3
votes
1answer
95 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'...
0
votes
2answers
60 views
4
votes
1answer
164 views
Rust implementation of next-permutation
I am translating this next permutation algorithm in C++:
...
0
votes
2answers
111 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 ...
0
votes
1answer
51 views
Fast bruth force numpy array combination
I want to extract combinations of numpy arrays in that way:
...
1
vote
2answers
183 views
Find All Permutations of String in Scala
I created the following function, permutations, to produce all permutations of a List[A].
Example:
...
0
votes
2answers
71 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 ...
-1
votes
1answer
146 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
votes
1answer
63 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
...
2
votes
1answer
42 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).
...
0
votes
3answers
45 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 ...
1
vote
0answers
26 views
3
votes
2answers
103 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
votes
1answer
41 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 ...
1
vote
1answer
108 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 ...
7
votes
2answers
295 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 ...
7
votes
1answer
406 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 ...
6
votes
1answer
287 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 ...
1
vote
2answers
85 views
Combinatorics challenge solved it Python
The easiest way to explain this problem is to show these two test cases:
...
5
votes
1answer
147 views
Permutations in C
I searched on the internet for an algorithm for permutations in C and I found the following function:
...
8
votes
2answers
153 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 ...
4
votes
1answer
57 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, ...
2
votes
1answer
148 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 ...
2
votes
1answer
48 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:
...
2
votes
1answer
41 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.
...
2
votes
2answers
106 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 ...
2
votes
1answer
31 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.
...
2
votes
1answer
65 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 ...
3
votes
1answer
80 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 ...
7
votes
3answers
224 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
4answers
236 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 ...
3
votes
3answers
93 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 ...
2
votes
1answer
50 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,...
2
votes
0answers
63 views
Find only one subset sum with a specified value in python for large sets
how can I optimize my code for a large set (10000 elements)?
...
8
votes
2answers
3k views
Permutations with replacement in Python
Many a times, I've had the need to use a permutations with replacement function.
So, I've written a function to do just that:
...
5
votes
1answer
187 views
Performance of mask (1,2,4,8,16) convertor in python
My mask translator is performing poorly in scenario where I have 30 masks and 10,000 ownerships. This is a bit field and similar to bit masks such as enum.IntFlag.
...
4
votes
1answer
65 views
Outputting flavor text depending on inputted strings
I have this program that takes two strings from the user, stores them in mixArray, then "mixes" them with mixItUp() and outputs ...
5
votes
1answer
74 views
Minimum amount of spaces inserted in a given string, such that it gets composed only of elements from a given list
The Challenge
Given a big string and a list of smaller strings, find the minimum amount of spaces that must be inserted between characters of the string in such way that it becomes composed only of ...
5
votes
1answer
103 views
Calculating every possible answer given a set of formulas
Problem
Given a set of formulas (AKA "Rules"), get a list containing every possible answer that does not break any formula.
Formula variables can have a maximum equal to the number of characters. ...
1
vote
2answers
191 views
MaxProductOfThree in C#
This is my solution for the MaxProductOfThree from codility, it scores 100%, but I'm not a fan of the if if if structure it has going on.
Task description
...
7
votes
2answers
384 views
Letter Combinations of a phone number using a Dictionary
Problem statement (online source)
Given a digit string, return all possible letter combinations that the
number could represent.
A mapping of digit to letters (just like on the telephone ...
11
votes
1answer
117 views
Recursive code to generate a parametric sweep of input values
I generate a set of data based off every combination of inputs. The source range that's inputs requires headers to identify the parameters. In its present state I'm not content as it's not as ...
10
votes
2answers
1k views
Earliest time frog can jump to the other side of a river in C#
I'm new to C#, I programmed a little in Java in the past. I had the two previous exercises reviewed here (permCheck, cyclicRotation, with a 100% score, just like this one), and I'm applying what the ...
6
votes
2answers
716 views
Codility's Permutation Check in C#
I've made a few things in Java, and now I'm learning C#.
The code passes the tests with 100% final score. I want to know what things can be improved in my code.
Task description
A non-empty ...
4
votes
2answers
274 views
Go function to generate permutations of a given integer array
I'm writing a function to generate a permutation of given []int:
...
2
votes
2answers
271 views
Counting block combinations I: Project Euler 114
Problem statement (For more detailed description (including pictures), please, visit the link):
A row measuring seven units in length has red blocks with a minimum
length of three units placed on ...
