Questions tagged [combinatorics]

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.

Filter by
Sorted by
Tagged with
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'...
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 ...

1
2 3 4 5
10