Questions tagged [combinatorics]

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

Filter by
Sorted by
Tagged with
3
votes
3answers
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 ...
7
votes
1answer
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? ...
6
votes
3answers
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 ...
8
votes
1answer
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 <...
10
votes
2answers
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. ...
0
votes
1answer
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 ...
13
votes
1answer
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 ...
8
votes
2answers
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 ...
4
votes
3answers
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 ...
5
votes
1answer
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: ...
3
votes
3answers
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 ...
6
votes
3answers
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 ...
5
votes
2answers
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. ...
3
votes
1answer
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++: ...
11
votes
3answers
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 ...
32
votes
5answers
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 ...
1
vote
1answer
6k views

Fastest way for working with itertools.combinations

I need to speed up the function below: ...
2
votes
1answer
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 <...
3
votes
2answers
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 ...
2
votes
2answers
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, ...
6
votes
2answers
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 ...
5
votes
5answers
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,...
6
votes
2answers
275 views

Integer Partition

The aim is to enumerate all possible sets of whole numbers whose sum is a given integer. ...
3
votes
1answer
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 ...
26
votes
7answers
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 ...
29
votes
3answers
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: ...
1
vote
1answer
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 ...
6
votes
2answers
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-...
3
votes
2answers
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 ...
-3
votes
1answer
169 views

Distinct triple sums

Here is my code. It works fine but I need to make the code more efficient. ...
4
votes
1answer
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: ...
3
votes
1answer
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. ...
6
votes
2answers
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 ...
3
votes
0answers
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 ...
2
votes
1answer
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? ...
3
votes
2answers
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 ...
3
votes
2answers
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#. ...
4
votes
3answers
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: ...
2
votes
1answer
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. ...
7
votes
4answers
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. ...
1
vote
1answer
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, ...
2
votes
2answers
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 ...
2
votes
1answer
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. ...
5
votes
2answers
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: ...
3
votes
1answer
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 ...
14
votes
4answers
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? ...
3
votes
2answers
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 ...
6
votes
2answers
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? ...
2
votes
2answers
2k views

Print all interleavings of two given strings

Given two strings str1 and str2, write a function that prints all interleavings of the given two strings. You may assume that all characters in both strings are different Example: ...
2
votes
1answer
158 views

Counting the ways to pick increasing sequences from sorted arrays

Preamble I am trying to learn JavaScript by writing code and looking up documentation, one problem at a time. I am already familiar with several "dynamic" languages, so I'm hoping to be productive ...