# Questions tagged [combinatorics]

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

422 questions
Filter by
Sorted by
Tagged with
97 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 ...
442 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 ...
2k 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: ...
553 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: ...
298 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 ...
524 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). ...
72 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 ...
262 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 ...
2k 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. ...
1k 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 ...
676 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 ...
1k 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: ...
62 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 ...
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 ...
1k 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 ...
62 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 ...
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 ...
1k 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 <...
56 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,...
284 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 ...
470 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: ...
59 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 ...
118 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 ...
16k 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 ...
1k 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 ...
81 views

### python magic square finder for arbitrary numbers

I wrote this code to get all possible magic squares that can be made with a list you put in. The only contraints are that the count of numbers is a square and that each number is unique. It even works ...
519 views

### Python solution to Code Jam's 'Rounding Error'

The "Rounding Error" problem of Round 1B of Google Code Jam 2018 is as follows: Problem To finally settle the age-old question of which programming language is the best, you are asking a total ...
60 views

### Algorithmic complexity of this algorithm to find all ordered permutations of length X

I have written a recursive function to generate the list of all ordered permutations of length X for a list of chars. For instance: ['a', 'b', 'c', 'd'] with X=2 will give [['a', 'a'], ['a', 'b'], ['...
122 views

I am new to functional programming. Just now I solved my first "real world" task using Haskell and now I'm wondering whether I got it "right" and what can be improved. The problem arises from tensor ...
2k views

### Determine if one string is a permutation of the another

Can anyone give me some feedback if I'm using std::unordered_multimap optimally? I don't know the ins-and-outs of the ...
389 views

### A little next combination program in C++

An implementation of next combination function at Discrete Mathematics and Its Applications, Rosen p.438. How it works: Input: The size n of a integer set {1, 2, ..., n}, which is where you choose ...
1k views

### Permutations with a sum constraint

I have made the following function that gives the combinations permuted of n elements with a constrain/rule. This consist on creating a dataframe with all combination of numbers from 0 to n that sums ...
521 views

### Python calculate arrangements of sequence

I have just started thinking about probabilities. A Problem that come up was how to calculate all the potential arrangements for a given sequence. By arrangement I mean unique permutation. I ...
201 views

### “Tara's Beautiful Permutations” challenge

I'm practising my coding skills using Python to answer medium to difficult problems on sites like HackerRank. Here is the challenge. Given an array of integers, where each number can appear at most ...
102 views

### Implementation of Permutation Algorithm B from Topor, 1982

This is Algorithm B from Functional Programs for Generating Permutations (Topor, 1982). We have implemented Algorithm B in an F# recursive module as follows. ...
229 views

### Permutation of a given set

A simple aspect of brute forcing certain problems is that you may have to do a large numbers of tasks in large numbers of possible orders, as such an algorithm for calculating all these possible ...
5k views

### A beautiful and easy way of permutation with recursion

I want to share a better version of permutation with you. Yesterday, when I was reading Horowitz's Fundamentals of Data Structures In C++, and I noticed that the result of the code, at page 32, in ...
105 views

### Use of concurrency to generate combinations

I have the following package to generate combinations from a slice of bytes: ...
233 views

### Calculate permutation from Factorial representation of the K-th iteration of the N-th permutation

As a follow of a post I made on the Mathematics Stack Exchange I wrote out a simple program that computes the K-th permutation from 0 to N-1 where the number of permutations is ...
190 views

### Counting the number of domino tilings for a rectangular grid

A domino tiling of a grid is a tiling of the grid using domino pieces. Below is a C++ program to count the number of possible tilings of a grid of a given size. The program constructs the board row ...
74 views

### Iterating through every permutation of every subset [closed]

I have this code which I use to iterate through every permutation of every subset in an array witch holds integers. One big problem is the efficiency of course, another problem is the fact that if I ...
205 views

### Finding the number of ways to partition {1,2, …, N} into p1 and p2 such that sum(p1) == sum(p2)

I am trying to write a space and time efficient algorithm to calculate the number of ways to partition a set of integers {1, 2, ..., N} into two partitions such that the sums of integers in the two ...
324 views

### Implementation of Permutation Algorithm A from Topor, 1982

This is Algorithm A from Functional Programs for Generating Permutations (Topor, 1982). The author states that the algorithm was described in TAoCP Vol 1. We have implemented Algorithm A in F# as ...
3k views

### All combinations of two pairs of elements of an array

Suppose I have an array of objects. Without loss of generality, it could be an array of indices: $$a = (0, 1, 2, ..., n)$$ Now suppose I want to choose two pairs of elements of this array. The order ...
72 views

### Determining if two packs are permutations of each other during compile-time

Often we need to find out if two tuples, or two packs in general, are the same as each other up to permutation. If there are no repeat types, then implementing ...
1k views

### Print all permutations from a given list of strings such that each set of strings is completely unique

Problem : Given a list of strings, some of which may be anagrams amongst themselves, print the permutations which can be so constructed so that each permutation has set of strings which is completely ...
74 views

### Find list of valid continuing positions in a game

My kids got a dice game for Christmas. I'm trying to mathematically analyze it. The first step is to come up with a list of all possible positions. Each player in the game has a certain number of ...
1k views

### Generate next combination in lexicographic order

C++'s standard library has a std::next_permutation algorithm but no next_combination. The reason behind this absence is, I guess,...
I began to program a little while ago and tried to implement my first algorithm: the Steinhaus-Johnson-Trotter algorithm. This algorithm generates a sequence of permutations of $n$ elements such ...