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.

Filter by
Sorted by
Tagged with
2
votes
1answer
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? <...
4
votes
1answer
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 ...
7
votes
4answers
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: ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
4
votes
2answers
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 ...
5
votes
3answers
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. ...
1
vote
4answers
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 ...
1
vote
1answer
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 ...
7
votes
3answers
3k views

Finding number of integer partitions

I am trying to find number of integer partitions of given n - number. If I have n == 4, the answer should be 5 because: \$4 = 1+1+1+1\$ \$4 = 2+1+1\$ \$4 = 3+1\$ \$...
-3
votes
1answer
2k views

Counting the number of ways to break an amount into coins

I have an algorithm here that counts the number of ways that n cents can be represented using the following denominations: quarter: 25 cents dime: 10 cents nickel: 5 cents pennies: 1 cent There are ...
3
votes
2answers
438 views

HackerRank challenge to count ways to climb a staircase, solved using Java Fork Join

I'm trying to solve Stair case recursion problem on HackerRank. The problem is to find all possible ways for a child to climb a stair case with height n given that ...
7
votes
2answers
9k views

List all possible permutations from a python dictionary of lists

The following code takes a dictionary of lists (indexed by keyword) and converts it into a list of list of dictionaries that contains all possible permutations of those lists. However, my solution ...
4
votes
1answer
85 views

A clean tacit version of (n choose k) in J

Listing all \$\binom{n}{k}\$ combinations of i is a well-solved problem in J. From that article, there is this implementation: ...
-2
votes
1answer
351 views

“How many numbers exist which are less than or equal to n and are divisible by a, b or c?”

First line contains 't' denoting the number of test cases. Next t lines contain 4 integers denoting n, a, b and c separated by spaces. Sample input: 1 15 2 3 5 Output: 11 Constraints: \$...
3
votes
1answer
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 ...
3
votes
2answers
697 views

Heap's algorithm implementation - permutations

I wrote an implementation of Heap's permutation algorithm in JavaScript (ES2015): ...
4
votes
1answer
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 ...
3
votes
2answers
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 ...
1
vote
1answer
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\$. ...
1
vote
1answer
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 ...
3
votes
1answer
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. ...
0
votes
1answer
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. ...
8
votes
2answers
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 ...
4
votes
0answers
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 ...
5
votes
1answer
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: ...
7
votes
3answers
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 ...
0
votes
3answers
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 ...
4
votes
1answer
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 ...
10
votes
1answer
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 ...
14
votes
3answers
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 ...
3
votes
1answer
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,...
7
votes
2answers
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. ...
1
vote
3answers
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: ...
2
votes
2answers
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. ...
3
votes
1answer
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 ...
3
votes
2answers
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: ...
6
votes
2answers
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 ...
3
votes
2answers
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 ...
1
vote
2answers
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 ...
5
votes
2answers
91 views

Expand string patterns in Elisp

I need to expand logical patterns to list of strings. For example I have the following definition: ...
0
votes
2answers
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 ...
5
votes
2answers
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) = ...
3
votes
2answers
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 ...
1
vote
1answer
112 views

Producing residues of combinatorics on strings

Basically, this code does multiplication of chosen operations. ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
2answers
139 views

Generalizing a choose operation

Consider the following piece of code. ...
0
votes
1answer
821 views

Subset sum simple iterative implementation

Here is the simplest iterative implementation of Subset sum problem that I could come up with1, as a follow up to this recursive implementation of the same problem: ...
3
votes
2answers
3k views

Subset sum problem implementation

Here is a recursive implementation of the Subset sum problem: ...