Questions tagged [combinatorics]
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.
438
questions
7
votes
2answers
114 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 ...
3
votes
1answer
51 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, ...
1
vote
1answer
110 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
31 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
38 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
105 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
29 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
61 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 ...
2
votes
0answers
42 views
Capacitated Vehicle Routing Problem with Time Windows [C++]
Summary: This code, although admittedly it's not the most optimal both in terms of performance and solution efficiency (for this task, genetic algorithms and certain rating heuristics are more ...
3
votes
1answer
71 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
215 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
152 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
84 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
45 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
29 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)?
...
3
votes
2answers
508 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
159 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
64 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
55 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
100 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
104 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
184 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
115 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 ...
9
votes
1answer
671 views
Earliest time frog can jump to the other side of a river in C#. Codility's task
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
347 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
107 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
165 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 ...
4
votes
1answer
156 views
Counting Bouncy Numbers: Project Euler #113
Problem statement:
Working from left-to-right if no digit is exceeded by the digit to its
left it is called an increasing number; for example, 134468.
Similarly if no digit is exceeded by ...
2
votes
3answers
95 views
Mapping words to letters which contains
Given sentence for example: ala ma kota, kot koduje w Javie kota I should to every letter occurring in the sentence I should map every string that this letter ...
2
votes
3answers
114 views
Counting numbers that are divisible by 3 and can be produced from the digits of a given number
I'm trying to solve this problem from codewars.
Problem
Given a certain number, how many multiples of three could you obtain with its digits? Suppose that you have the number ...
6
votes
4answers
2k views
LINQ for generating all possible permutations
Permutate() is supposed to generate all possible permutations of the source sequence:
...
3
votes
2answers
74 views
Fixed Content Necklace Generator
I wrote a class that generates combinatorial necklaces with fixed content as per Sawada: A fast algorithm to generate necklaces with fixed content. The class is instantiated with an input list that ...
11
votes
3answers
443 views
Print sums of all subsets
Print sums of all subsets of a given set
Problem summary : Print all subset sums of a given set of integers
My approach is to store previous results and use them to calculate new (similar idea as ...
3
votes
2answers
155 views
Challenge: phone keypad to letters - return all possible strings
The challenge:
Given a mapping of digits to letters (as in a phone number), and a digit string, return all possible letters the number could represent. You can assume each valid number in the ...
2
votes
2answers
153 views
Project Euler # 24 Lexicographic permutations in Python
A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of
the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we ...
4
votes
2answers
299 views
Letter case permutation
The question can be found here https://leetcode.com/problems/letter-case-permutation
Given a string S, we can transform every letter individually to be
lowercase or uppercase to create another ...
2
votes
2answers
345 views
Staircase challenge - Python
Your task is to print all unique ways to climb a staircase of length n where, from each step, you can take steps of size x where ...
6
votes
1answer
111 views
A straightforward method for computing the Binomial probability mass function
I've been writing up code to test an alternate way of calculating the Binomial probability mass function. The Binomial random variable is the number of heads out of N coin tosses with coins that have ...
4
votes
2answers
83 views
Array of all permutations in C
Is this a good compromise between readability and verbosity? Are there any bugs, additional error checking, or extraneous code as well?
...
11
votes
6answers
3k views
HackerRank: Electronics Shop
Challenge from Hacker Rank -
Monica wants to buy a keyboard and a USB drive from her favorite electronics store. The store has several models of each. Monica wants to spend as much as possible for ...
7
votes
5answers
211 views
String combinations of 0 and 1
I was asked this question in an interview:
Given a string s consisting of 0, 1 and ...
6
votes
2answers
661 views
Sums of all sublists
The parts_sums function in the code takes a list as parameter and then returns sum of all sub-lists present in the list. e.g.
if, ...
4
votes
1answer
222 views
Pick the best combination of n choose k models
Algorithm
Let \$M_0\$ denote the null model which contains no predictors. This model simply predicts the sample mean of each observation.
For \$k=1,2,\ldots,n\$:
Fit all \$n \choose k\...
4
votes
3answers
441 views
Generate parentheses solution
I have coded a solution to build all valid permutations of parentheses.
My code is below.
I have a question on my code based on a comment by my PEP8 checker. It said that there was no need to ...
4
votes
1answer
243 views
Generate all possible combination of n-pair parentheses
The task is taken from LeetCode
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
...
2
votes
1answer
53 views
Computing the cost for creating a perfect square (with N = 3)
You are given a square matrix \$A \in \mathbb{ N}^{n,n}\$, this number contains integers from \$1\$ to \$n^2\$. The task is to compute the minimal cost, to change this square into a perfect square. A ...
3
votes
1answer
242 views
Swift function to find a specific set of combinations of 3 digits within a larger integer array
I asked this question on Stack Overflow and was directed here. I'm working on a function that will help me quickly find all the upper structure triads (3-note chord) that I can add to a 4-note 7th ...
4
votes
1answer
555 views
Project Euler 76: Counting summations
Project Euler Problem 76 asks:
How many different ways can one hundred be written as a sum of at least two positive integers?
My code is correct but just works slowly.
...
2
votes
0answers
45 views
Interleave two lists, preserving the order of elements in their original list
I need to write an OCaml program that return all possible zip of two lists together while preserving the order of the element in each list. For example, if we zip the lists [1;2] and [3;4], we get [[1;...
3
votes
1answer
85 views
Iterative version of a permutations algorithm
For learning purposes, I've written an iterative version of a recursive algorithm for generating the set of permutations for a given set of unique integers.
Can I make any improvements to increase ...
