Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Questions tagged [combinatorics]

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

418 questions
Filter by
Sorted by
Tagged with
6k views

### Computing the powerset of a list

I've written the following code for computing the powerset of a list (we consider the list has all distinct elements, although it doesn't really matter). Can this function be further optimized? <...
4k views

### Compute power set of a given set in Python

Problem: Given a set (let's say of integers), return the list of all of its subsets also known as the power set. It looks to be working, but I would like feedback on the algorithm and Python ...
3k views

### Generating Permutations in Python

To brush up my Python knowledge I an algorithm to generate permutations in lexicographic order. I ended up with the following code: ...
251 views

### Counting subsets with sum not exceeding some limit

I am facing a variation of a subset sum problem. I have to count the number of subsets with sum less than or equal to some integer(limit). I think the optimal solution for this problem would be the ...
456 views

### C++ permutation generator

I wrote this code to help with programming challenges. A lot of problems can be solved by complete search so I wrote this function that I can copy/paste between problems to generate permutations ...
104 views

### Counting the maximum number of four-in-a-row wins

It all started during a "fourInARow" game... A friend of mine asked: "If you drop in all 42 stones, what will the number of "four in a row"s be with the optimal configuration?" I thought it should be ...
4k views

### Generating all possible combinations of a string using iteration

I am generating all possible combinations from a string concatenated. I have a $O(n*2^n)$ solution. ...
162 views

### Find frequency of combinations in large data set

My concern is performance of the code. It takes way longer than I would like. I would be willing to give up some memory for higher performance. I have JTable with serial numbers in column1 and ...
64 views

### Find all combinations of a number sequence which is first increasing then decreasing

Given an integer N(Natural Number), A program/Algorithm to find the remainder of arrangements that can be obtained by rearranging the numbers 1, 2, ...., N. Input Format: One line containing ...
3k views

752 views

### Permutations in Python

Question 2 of Homework 11 from Berkeley's CS6 1A says: Implement permutations, a generator function that takes in a lst and ...
697 views

### Heap's algorithm implementation - permutations

I wrote an implementation of Heap's permutation algorithm in JavaScript (ES2015): ...
2k views

### K-combination recursive algorithm implementation

Tried to implement this solution for finding n choose k. I have used recursion and this is how it goes for k as 4 and n as 6. Zero based The idea is to have array of size k keeping sequence of ...
2k views

### Create all combinations of length N from a given alphabet (2)

I implemented this challenge in Java before but performance was not the best so I decided to implement this in C++ to compare the two. The code works and performance is indeed much better than in the ...
84 views

### Count all possible attendance records with length n, which will be regarded as rewardable

Given a positive integer n, return the number of all possible attendance records with length n, which will be regarded as rewardable. The answer may be very large, return it after $\mod 10^9 + 7$. ...
1k views

### Create all combinations of length N from a given alphabet

I have some (very limited) experience in Java 6 and decided to revisit the language. To do so I wrote a solution for the following challenge: You are given a number N and a string S. Print all of ...
1k views

### Finding the middle permutation

This method finds all permutations of a string and stores them in a sorted array. It then returns the element in the middle of the array. ...
187 views

### Produce the nth lexicographic permutation of a string consisting of letters H and V

I have tried many possible methods here but I am still not able to reduce the time complexity of below algorithm. ...
269 views

### Return all valid expressions with specific target

The problem is stated as: Given a string that contains only digits 0-9 and a target value, return all expressions that are created by adding some binary operators (+, -, or *) between the digits so ...
804 views

### Finding combination of coins that can produce a given sum

This function is checking, whether it has enough money in a list called self.deviceMoney to make change. It works exactly the way I want, but only in case where ...
109 views

### Calculation of lexicographic permutations

Just for fun, I studied the generation of lexicographic permutations and came across the following algorithm which I transcribed into Common Lisp, as good as I can, being a hobbyist: ...
1k views

### Find the total number of ways W, in which a sum S can be reached in N throws of a dice

I was solving this question: Given there is a 6 sided dice. Find the total number of ways W, in which a sum S can be reached in N throws. Example: S = 1, N = 6 => W = 0 S = 6, N = 6 => W ...
405 views

### All possible combinations of colors for Mastermind

Just started out with CIS 194 on Haskell and wonder what the more idiomatic way to solve this problem would have been. This code is supposed to generate all possible combinations of 6 given colors up ...
1k views

### Find distinct combinations of four elements in an array that have a certain sum

The task is: Given an array A of size N, find all combinations of four elements in the array whose sum is equal to a given value K. The specific requirements are: The combinations must be distinct ...
322 views

### Sequence-based enumeration of permutations in lexicographic order

This is follow-up on On Knuth's "Algorithm L" to generate permutations in lexicographic order, where I presented the following method to enumerate all permutations of array elements in ...
2k views

### On Knuth's “Algorithm L” to generate permutations in lexicographic order

I needed a method to generate all permutations of given elements, so I decided to implement "Algorithm L (Lexicographic permutation generation)" from Donald E. Knuth, "GENERATING ALL PERMUTATIONS" in ...
2k views

### All combinations of 2-value variables

Introduction This code was part of one of my projects where it was used to generate boolean input values for truth tables. I have since generalized it for combinations of variables with only 2 values,...
142 views

### 4 distinct integers, whose reciprocals sum up to 1

I wrote the following short python program to solve a math puzzle, which asked for all the 4-tuples of distinct natural numbers whose reciprocals sum up to 1. ...
99 views

### Print out all possible sizes of subsequences of string in C

For example, given a string "abcdefghijk", I want my function to print out: ...
652 views

### Python one-liner to print permutations of a string

I have written a Python one-liner that permutes a given string. I wrote this just for fun using list comprehensions and I would like to get feedback from the community. ...
441 views

### k-combinations in lexicographic order (using given algorithm)

I already solved the problem, but it seems my code is too awkward, and with a different approach there could be a more elegant solution. Notice that the general algorithm is described in the ...
2k views

### Finding integer lengths for a right triangle with a given perimeter

I'm using Python 3 and have written this code to find the right triangle sides when given the perimeter: ...
1k views

### Building a set of all subsets recursively in C++

Here is my recursive implementation of a power set function in C++. One thing that concerns me is that I am iterating over the set of sets while modifying its size. The code nevertheless functions as ...
370 views

### Finding Permutations of Numbers

I'm trying to solve this challenge, which consists of finding the next biggest number formed by the digits of the passed in number. If it is impossible to find a number larger than the passed in ...
204 views

### SPOJ - Alphacode - Exceeds Time Limit

I'm trying to solve Alphacode on SPOJ. The challenge is to count the ways to split a string of up to 5000 digits into a sequence of numbers, each ranging from 1 to 26. It works fine for small ...
91 views

### Expand string patterns in Elisp

I need to expand logical patterns to list of strings. For example I have the following definition: ...
571 views

### Iterative “counting change” implementation in mit-scheme

Here is my iterative implementation of the Counting change example in SICP. Please note that I'm a beginner, which means I only know the basic syntax for the time being. Requirement: How many ...
389 views

### Calculating the count of integer partitions of a number (uses stateful vectors internally)

I've written a Haskell function to count the number of partitions of an integer - it's basically an implementation of the same algorithm as this one, using Euler's Pentagonal Number Theorem: P(n) = ...
124 views

### Equivalents permutations function

My function is supposed to essentially give the cartesian product of all the letters in a string with the caveat that you have to give the permutations of every equivalent of each character in a ...
112 views

### Producing residues of combinatorics on strings

Basically, this code does multiplication of chosen operations. ...
789 views

### Generating all unique permutations of a string

Here is a plan for generating the permutations of S: For each item x in S, recursively generate the sequence of permutations of S - x, and adjoin x to the front of each one. This yields, for each ...
1k views

### All permutations of integer vector

I have spent a decent amount of (waaay too much) time trying to write the below function and get my head around recursion. The aim was to return all permutations of an int vector (assuming no ...
139 views

### Generalizing a choose operation

Consider the following piece of code. ...