Questions tagged [combinatorics]
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.
467
questions
0
votes
1answer
45 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 ...
-1
votes
0answers
23 views
Size Constrained Integer Partitions of a Given Number [closed]
As a smaller part of a programming challenge, I am writing a function in Python that takes two parameters, a given number and a size constraint. The function yields a generator that produces the ...
2
votes
1answer
43 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.
...
1
vote
0answers
12 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
votes
1answer
172 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']):
...
0
votes
1answer
45 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 ...
2
votes
1answer
108 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 ...
3
votes
3answers
227 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
52 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 ...
4
votes
1answer
111 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
61 views
4
votes
1answer
217 views
Rust implementation of next-permutation
I am translating this next permutation algorithm in C++:
...
2
votes
2answers
349 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
85 views
Fast bruth force numpy array combination
I want to extract combinations of numpy arrays in that way:
...
1
vote
2answers
353 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
78 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
217 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
66 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
45 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
52 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
28 views
3
votes
2answers
164 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
vote
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 ...
2
votes
1answer
114 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
344 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
1answer
429 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
530 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
104 views
Combinatorics challenge solved it Python
The easiest way to explain this problem is to show these two test cases:
...
5
votes
1answer
161 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
188 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
65 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
151 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
87 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
42 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
32 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
72 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
226 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
272 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
100 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
70 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)?
...
7
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
207 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
70 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
96 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
105 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
215 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
...
