# 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
345 views

### Curious fractions in functional Ruby

Problem 33 in Project Euler asks: The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is ...
1k views

### Speeding up subset sum implementation

Important fact: the number of the input is greater than 1. How do I use this fact to speed up this solution? ...
2k views

### Optimizing unique partitions of integers

I am working on a project involving the unique partitioning of integers. I.e. I am looking to have all of the partitions of n = x1 + x2 + x3 + ... + xk, where xi = xj implies i = j. For example, if I ...
88 views

### Compute stats on two class vectors

Below is a full working code example of code which is used to compute stats on two class vectors (partitions). There are two functions: pairwise_indication and <...
4k views

### Printing permutations of a given string

I want some feedback on the program I developed in C for printing the permutations of a given string. ...
635 views

### Finding the number of permutations of an integer array with equaling difference (not in order)

The array size is <= 16. The difference is defined as: diff[i] = array[i+1] - array[i]; I need to find the number of permutations of the original array, which ...
2k views

### Nonogram puzzle solution space

I've written some code to brute-force enumerate the solution space of nonogram puzzles up to a certain size. It does a good job up to the first ~4 billion puzzles, but I run out of disk space to store ...
234 views

### Generate permutations with symbols

Goal: Create a combination of emails based from inputted first name, last name, middle name, and a domain. Add in common separators. Then I'll check which one is correct with the rapportive API. This ...
2k views

### Prints out all ways to multiply smaller integers that equal the original number

Write a program in Java that takes a positive integer and prints out all ways to multiply smaller integers that equal the original number, without repeating sets of factors. In other words, if your ...
207 views

### Project Euler #15 in haskell

I've solved Project Euler #15 in Haskell, but I feel like there might be a better way to express my solution that I'm not seeing. I start out defining my types: ...
10k views

### Permutation of a string eliminating duplicates

This code lists the permutations of the string, and eliminates duplicates if any. I'm looking for code review, best practices, optimizations etc. I'm also verifying complexity: $O(n! * n)$ as time ...
77k views

### Calculate all possible combinations of given characters

I was asked in my textbook Lectures on Discrete Mathematics for Computer Science to construct a program that would take an alphabet ({a,b,c} or any combination of ...
2k views

### Print routes on the stairway when only 1 or 2 steps are possible

Given a staircase with N steps, you can go up with 1 or 2 steps each time. Output all possible ways you go from bottom to top. I'm looking for code review, best practices, optimizations etc. ...
2k views

### Find all permutations of a string in C++

I need a review of the following code for finding all permutations of a string in C++: ...
3k views

### Creating all possible combinations of points

I want to create all possible combinations of points (0,0),(0,1)...(12345,6789) and then all segments from these points. The code I have written is simple and with no optimization. Is there any ...
49k views

### Brute Force Algorithm in C

This is a simple brute force algorithm that I have programmed in C. All the program does is print out every possible combination of the given alphabet for the ...
6k views

### Fastest way for working with itertools.combinations

I need to speed up the function below: ...
91 views

### Produce product of lists

I want to combine elements in different lists. For example, here are 3 lists. list_a : [ 1,2,3 ] list_b : [ 4,5,6 ] list_c : [ 7,8 ] Selecting elements from <...
174 views

### Determine if a word can be constructed from list of subsets - follow-up

I have reworked my code as suggested from my previous question: Determine if a word can be constructed from list of subsets. Please instruct me on the complexity along with a review feedback, as ...
176 views

### Determine if a word can be constructed from list of subsets [closed]

The question is explained well by examples in the comments below. Also I request verifying complexity: O( n * n!), where n is the number of words in the subsets. Review my code for optimizations, ...
516 views

### Integer Partition using an iterator

I tried implementing Integer Partition (enumerating all possible sets of whole numbers whose sum is a given integer). Looking at @rolfl's answer, I reasoned that with a stack data structure, we ...
1k views

### Permutation algorithm

I was asked to write a permutation algorithm to find the permutations of {a,b,c}. Since this is a famous question to which an answer is readily available online, I wanted to do it a little differently,...
275 views

### Integer Partition

The aim is to enumerate all possible sets of whole numbers whose sum is a given integer. ...
112 views

### Better way to create samples

I've done this piece of code for creating all possible samples without repetitions, but I think that it is a so heavy algorithm because every time I call this recursive function I create a new vector ...
7k views

### Finding words of different lengths given six letters

I'm trying to find all the 3, 4, 5, and 6 letter words given 6 letters. I am finding them by comparing every combination of the 6 letters to an ArrayList of words ...
79k views

### Find all subsets of an int array whose sums equal a given target

I am trying to implement a function below: Given a target sum, populate all subsets, whose sum is equal to the target sum, from an int array. For example: ...
94 views

### Increase efficiency of card-ordering program

As mentioned in @rolfl comment. What this program does is that it "resequences the cards using a fixed system and count the number of times the resequencing happens before the output is the same as ...
330 views

### Central Delannoy numbers

I am solving this problem on SPOJ Upper Right King (Hard): There is a king in the lower left corner of the $n \times n$ chess board. The king can move one step right, one step up or one step up-...
310 views

### Max-digits of digit summing

As a challenge I decided to do the following problem: How many different numbers with n digits are there whose digits add up to k? As this is an embarrassingly parallel problem I decided to use a ...
169 views

### Distinct triple sums

Here is my code. It works fine but I need to make the code more efficient. ...
1k views

### Showing all possible permutations from a set

I wrote a small program which shows all possible permutations of choosing m integers from the set ${1, 2, ..., n}$, as follows: ...
1k views

### Python infinite product generator

I have the code below to get an infinite generator of the products of an iterable (e.g. for the iterable "ABC" it should return A, B, C, AA, AB, AC, BA, BB, BC, CA, CB, CC, AAA, AAB, AAC etc. ...
4k views

### Permutation of given string

I am reading a book on DSA, and the author explains how to generate the permutation of strings using recursion. I want to know if there are better ways of doing the same, unless this is the best ...
433 views

### Python knapsack program

I have this data for the knapsack problem: List of product prices = MENU Most popular product count = MOST_POPULAR_COCKTAIL ...
467 views

### Find all row combinations which sum elements equal to any given number

It works fine, but it is slow. Could anybody help make this faster? ...
1k views

### Computing the number of permutations of n consecutive numbers

I'm just starting to learn C++ and have been experimenting with various functions. Here is one that computes the number of permutations of n consecutive numbers as well as all possible permutations ...
356 views

### My implementation of lexicographic permutation in F# is 3x slower than C#

Can someone help me with the following micro optimization for the F# code for lexicographic permutation? I have code in C# which runs for 0.8s. As a learning practice, I translated it into F#. ...
522 views

### Optimizing sum_combination_for(n) code

I'm working on a piece of code for calculating all the possible combinations of numbers that sum to n. For example: ...
1k views

### Generating permutations with repetitions of string

I have written the below code which generates all possible permutations with repetitions of a string. I want to make this program shorter and much faster, but I don't know how to do that. ...
1k views

### Printing all binary strings of length n

I have completed my homework with directions as follows: Declare and implement a class named Binary. This class will have a method named printB(int n) that prints all binary strings of length n. ...
433 views

### Any way to optimize or improve this python combinations/subsets functions?

I believe this is essentially the same method as the itertools.combinations function, but is there any way to make this code more more perfect in terms of speed, ...
2k views

### multi-recursive replacement function

I wrote a function for creating all possible translations of a source string, based on a multiple translation map. It works, but generates a lot of intermediate maps (see line marked with *). Is there ...
332 views

### Discovering words from letters in Clojure (Letterpress Solver)

I created a Letterpress solver that will take a string of letters and return a list of valid words that can be constructer with the provided letters. Not all letters need to be used in each word. ...
226 views

### Finding perimeters of right triangles with integer-length legs, up to a limit

I have a nested for-loop that populates a list with elements: ...
114 views

### Producing all allocations by n items from a list

I have strong feeling that the code below is ugly at least as there are 2 same "cons". I would appreciate if you advise me ways to improve it. The code produces all allocation by n items from list ...
2k views

### Exhaustive search for encryption keys

This does the job, but is not especially elegant. What is the preferred Pythonic idiom to my childish nests? ...
3k views

### Getting all (forward) permutations of a list of strings

I have the following concise-ish (and working) approach to getting all the forward permutations of a list of string. So with the list: w = ["Vehicula", "Sem", "Risus", "Tortor"] the results ...
2k views

### Combinations of list elements

It was written in Emacs Lisp and requires Common Lisp loop facility. Can this code be improved? Did I hit any anti-patterns along the way? ...