Questions tagged [combinatorics]
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.
495
questions
7
votes
5
answers
693
views
String combinations of 0 and 1
I was asked this question in an interview:
Given a string s consisting of 0, 1 and ...
- 501
6
votes
2
answers
3k
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, ...
- 61
4
votes
1
answer
1k
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\...
- 41
4
votes
3
answers
534
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 ...
- 2,043
4
votes
1
answer
3k
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:
...
- 3,993
2
votes
1
answer
67
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 ...
- 595
3
votes
1
answer
1k
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 ...
- 133
5
votes
1
answer
2k
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.
...
- 519
3
votes
0
answers
194
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;...
- 131
3
votes
1
answer
240
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 ...
- 41
7
votes
2
answers
7k
views
Compute all the permutations for a given vector of integers
The task is to compute all the permutations for a given vector of integers (but of course the specific integer type is not relevant for the solution)
The strategy is based on recursion + iterations
...
- 287
1
vote
2
answers
906
views
Leetcode Next Permutation in Python
My solution to Leetcode Next Permutation in Python.
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is ...
- 341
2
votes
2
answers
673
views
Iteratively generating permutations with repetitions
I tried to solve the simple problem of generating all permutations of length n with m distinct elements where repetition is allowed. Doing this recursively took me like 10 minutes:
...
- 474
6
votes
1
answer
567
views
Best way to performance permutations
This has been my white whale for a while, the idea is convert all the symbols to the goal symbol using all the pieces.
I did an algorithm like 5 years ago (now is lost) and reach lvl 48 but got stuck ...
3
votes
2
answers
130
views
Number of possible numbers in roman number string
I just started learning programming a few months ago, and I'm intrigued by Haskell. To learn a bit I tried to adapt some code I have in Java so I can see what are equivalent solutions in Haskell.
The ...
- 215
4
votes
2
answers
956
views
PermCheck Codility
The following code gets 100% on the PermCheck task on Codility. It should be O(N).
The question is:
A non-empty array A consisting of N integers is given.
A permutation is a sequence ...
- 221
5
votes
5
answers
1k
views
Checking if an integer permutation is cyclic in Java
A an integer permutation array[] is said to be cyclic if and only if we can choose an arbitrary element at position i, move it ...
- 28.2k
4
votes
1
answer
919
views
Iterating over combinations
Background
The following describes the real world problem that my code is intended to solve. It is may help you understand what the code is doing and why. I don't think this is strictly necessary in ...
- 209
3
votes
2
answers
1k
views
Grid search parameter combinations in Python
For a computation engineering model, I want to do a grid search for all feasible parameter combinations. Each parameter has a certain possibility range, e.g. (0 … 100) and the parameter combination ...
- 131
2
votes
1
answer
81
views
Worker placement in Orleans board game/combinations
I am trying to program the board game Orleans. I am planning on making a computer player that plays randomly at first. The part of the game that I'm struggling to code elegantly at the moment has to ...
- 123
2
votes
3
answers
996
views
Generate all possible permutations of a string in C++
This is my version of the possible permutations of a string challenge. Please give me feedback or criticism. There are two vectors here: positions and ...
- 231
1
vote
1
answer
62
views
Find the combination of matches which are closest to each other
Problem - Given three sorted arrays find combinations which are closest to each other.
example -
...
- 385
2
votes
3
answers
145
views
Counting paths between 3 cities in C++
The task is to make a program that prints out how many possible paths a driver can use to visit three cities so that he visits each city exactly n times. The program must be executed within 1 minute ...
- 23
3
votes
2
answers
1k
views
Print out all possible letter combinations a given phone number can represent
I am working on a problem in which given a 7 digit telephone number, we need to print out all possible combinations of letters that each number could represent.
I came up with below code and I was ...
- 319
6
votes
1
answer
91
views
General nested for
I needed a general-purpose function that accepts some sequence_container<sequence_container<T>> and iterates all permutations of the inner container. To ...
- 183
1
vote
1
answer
208
views
Python finding next word permutation with function generator
Learning how to use function generators in Python I practiced with the following code that finds the next permutation of a word and then uses this new word as input for the next one until there are no ...
- 801
5
votes
2
answers
1k
views
Finding all possible letter combinations from an inputted phone number
Prompt:
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 (just like on the ...
- 175
10
votes
2
answers
4k
views
Generating the powerset in C
I am solving another problem in leetcode.
Given a set, generate all the subsets of the set.
Input: [1,2,3]
Output: ...
- 313
2
votes
2
answers
997
views
Generating all permutations of 1 digit, 2 equal letters and 2 different letters efficiently
I created a function that generates all the combinations of 1 digit, 2 equal letters and 2 different letters.
I reduced the numbers and letters to make it more easy to calculate:
...
- 237
5
votes
2
answers
520
views
Sequence-based enumeration of permutations with Heap's algorithm
Heap's algorithm
is an algorithm to generate all permutations of a given array. It
... generates each permutation from the previous one by interchanging a single pair of elements; the other n−2 ...
- 23.2k
5
votes
3
answers
2k
views
Disjoint cycles of a permutation
Given an element of the permutation group, expressed in Cauchy notation, it is often useful to have it expressed in disjoint cycles (for example to apply the permutation to the keys of a dictionary).
...
- 199
2
votes
2
answers
125
views
Forming all multiples of 3 using the given digits
I'm working on this kata from Codewars. The task is:
Given a certain number, how many multiples of three could you obtain with its digits?
Supose that you have the number 362. The numbers that can be ...
- 171
0
votes
2
answers
901
views
Lattice path from Project Euler with Python solution
I was trying to solve this problem called lattice path from Project Euler:
Count the number of unique paths to travel from the top left to the bottom right of a lattice of squares.
How many such ...
- 2,469
4
votes
1
answer
4k
views
Recursive implementation of power set in Python
I was doing a recursion problem called power set, and would like to get code review. Here's the problem.
...
- 2,469
4
votes
1
answer
4k
views
n choose k combination in JavaScript
I was asked to solve a problem for \$\binom{n}{k}\$. I did the following implementation and am wondering if there's any feedback.
Input:
n = Integer
...
- 2,469
10
votes
3
answers
706
views
Master Locksmith
Description
Master Locksmith has just finished the work of his life: a combination
lock so big and complex that no one will ever open it without knowing
the right combination. He's done testing ...
- 11.5k
7
votes
2
answers
2k
views
Generate Letter Combinations of a Phone Number
The task: Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
and my solution:
...
- 779
2
votes
1
answer
72
views
Fitter Nearest-Neighbor function with three nested loops
Background Problem
Consider a set of students that we want to place into Ng groups each of which contains Ns students. Let's ...
- 121
8
votes
4
answers
2k
views
Project Euler #15: counting paths through a 20 × 20 grid
I've recently solved Project Euler's 15th problem stating:
Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom ...
- 83
12
votes
1
answer
3k
views
Generalized Cartesian Product
Much to my chagrin, neither STL nor Boost has a cartesian product. Namely, given as arguments one or more iterables, create an iterator producing std::tuples of ...
- 2,894
2
votes
1
answer
91
views
Total of maximum values in all subarrays
This is the crux of a problem found on one of those code challenge sites.
I'm fairly new to programming and this was a difficult challenge. I've attempted to solve this with stacks and calculating ...
- 373
3
votes
2
answers
1k
views
Generate all combinations of length N through M
I've started learning programming and as matter of practice I've decided to make a program that will output all possible string combinations and put them in a file.
I've manged to do that and it works ...
- 33
7
votes
3
answers
3k
views
Calculator of combinations without repetition
I am interested to find an absolute value (not an approximation) of "combination without repetition" for given \$n\$ and \$k\$, or \$\binom{n}{k}\$.
The brute force solution would look like this
<...
- 912
0
votes
2
answers
99
views
Count number of cycles in permutation
Write a function that a receives file name and an integer N as arguments, that represent a binary file which contains N integers,...
- 175
3
votes
1
answer
592
views
Bovine Shuffle using a queue (USACO Dec 2017 Silver)
I am working on the "Bovine Shuffle" problem from the December 2017 USA Computing Olympiad, and have got it to work for every test case beside two. When I run these two cases on my own computer, they ...
- 73
5
votes
1
answer
830
views
Splitting URLs into hierarchy-level directories
The goal is to split a URL like http://q.com/a/b/c to:
['http://q.com/a', 'http://q.com/a/b', 'http://q.com/a/b/c']
My code:
...
3
votes
1
answer
142
views
Mutative Heap's algorithm (permutations generator) in Clojure
For a side project I'm working on, I need to be able to generate permutations. Instead of relying on an existing library like math.combinatorics, I decided to write ...
- 16.3k
7
votes
1
answer
319
views
Custom container for iterating over combinations of elements from multiple sets
Motivated by some SO quesitons [1, 2] I made an attempt at implementing a custom container with a bi-directional custom iterator for iterating over all combinations of elements from multiple sets.
I ...
- 201
16
votes
3
answers
35k
views
Get all combinations of selecting k elements from an n-sized array
Was asked this today in an interview. Didn't see it before, and spent quite a lot of time getting it to work (tricky with all the recursion).
The goal was to find all possible combinations of ...
- 637
3
votes
2
answers
2k
views
Maximum sub-array of non-negative numbers
This is the "Maximum sub-array" problem from CodeChef:
Find out the maximum sub-array of non negative numbers from an
array.
The sub-array should be continuous. That is, a sub-array
...
- 1,741