Questions tagged [combinatorics]

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

Filter by
Sorted by
Tagged with
67
votes
9answers
101k views

Generating all combinations of an array

I'm generating all combinations of an array, so for instance, ["a", "b", "c", "d"] will generate: ...
50
votes
3answers
3k views

Analyzing Minesweeper Probabilities

Calculating probabilities in Minesweeper might sound like an easy task, but I've seen so many probability calculators that's either incorrect, horribly slow, or with ugly code (or all of them) so I ...
40
votes
1answer
2k views

Finding minimum scalar product using ST Monad

Inspired by a Stack Overflow question, I decided to practice my Haskell by taking a crack at the Google Code Jam's Minimum Scalar Product problem: Given two vectors \$\mathbf{v_1}=(x_1,x_2,\ldots,...
31
votes
5answers
46k 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 ...
31
votes
3answers
883 views

Advanced and Detailed Minesweeper Probabilities

In an earlier question, I showed my code for calculating the mine probability for each and every field in a Minesweeper board. But it doesn't stop there. In that very same Minesweeper Analyze project, ...
28
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: ...
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 ...
22
votes
7answers
6k views

Solution for kth row of Pascal's triangle for a job interview

Question: Given an index \$k\$, return the \$k^{th}\$ row of the Pascal's triangle. For example, given \$k = 3\$, return \$[1,3,3,1]\$. Bonus points for using \$O(k)\$ space. Can it be ...
19
votes
2answers
1k views

Calculate all possible distributions of n objects to k containers

Let's say I have \$5\$ apples, thus \$n = 5\$. I have three bags (\$k = 3\$), each having the capacities of \$4\$, \$4\$ and \$2\$: $$c = { \{4, 4, 2 \}}$$ I'd like to calculate the number of ways ...
18
votes
4answers
3k views

Printing all possible sums of two n-sided dice rolls

For my CS class, we were tasked with writing a program that calculates all the possible results from rolling two n-sided dice. For example, the input of 4 would ...
18
votes
4answers
4k views

Count number of ways to paint a fence with N posts using K colors

A friend sent me this question, and I'd love somebody to review this and give his opinion. Write an algorithm that counts the number of ways you can paint a fence with N posts using K colors such ...
17
votes
6answers
30k views

Generate all possible combinations of letters in a word

This is a JavaScript function that returns ALL the possible combinations of whatever word the user enters. I am looking to clean this code up a bit...any and all suggestions are welcome! ...
17
votes
3answers
13k views

Finding all k-subset partitions

The following code generates all \$k\$-subsets of a given array. A \$k\$-subset of set \$X\$ is a partition of all the elements in \$X\$ into \$k\$ non-empty subsets. Thus, for ...
16
votes
2answers
332 views

Minimising the triangle

A triangle needs a good foundation. Every row in the triangle is derived from the sum of the two values below it. However, there can be no repeated values, if a value shows up more than once the ...
16
votes
1answer
172 views

Minesweeper analyze goes to N-Queensland

As @rolfl recently solved the N-Queens problem, I figured that it was time also for me to solve it. My approach is significantly different from @rolfl's. I quickly realized that the N-Queens problem ...
15
votes
5answers
37k views

Brute force password cracker

I wrote this script for a proof of concept JavaScript password cracker: ...
15
votes
1answer
318 views

Permuting a typelist

Given a typelist, return a typelist of all the permutations of it. For example: ...
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? ...
14
votes
2answers
1k views

TopCoder problem “Lottery” - SRM 144 (Division I Level Two)

The problem statement Summary: The rules of a lottery are defined by two integers (choices and blanks) and two boolean variables (sorted and unique). choices represents the highest valid number ...
14
votes
2answers
4k views

Generating Cartesian product of strings in R

Sometimes I need to create character vectors like this one: ...
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 ...
13
votes
3answers
11k 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 ...
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 ...
12
votes
3answers
11k views

Counting permutations without repetitions for a number or a string

Can I make the following code faster with minor modifications? It times out on CodeWars website. ...
12
votes
3answers
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 ...
12
votes
3answers
6k views

Random permutation of int[] and ArrayList<Integer>

I wrote a simple program using int[] and ArrayList<Integer> which aims to get a random permutation output between 1 to 10, ...
12
votes
2answers
592 views

Finding a word within a pre-defined set using a search string with wildcards

The other day I was intrigued by this question (originally from here): Write a program that answers YES/NO search queries containing * placeholders. Example: if the data you have is (hazem, ahmed,...
12
votes
1answer
292 views

Counting paths in an n-dimensional grid that stay within the boundaries

Problem Statement You are situated in an N dimensional grid at position (x1, x2, …, xN). The dimensions of the grid are (D1, D2, …, DN). In one step, you can walk one step ahead or behind in ...
11
votes
6answers
2k views

HackerRank: Electronics Shop

Challenge from Hacker Rank - Monica wants to buy a keyboard and a USB drive from her favorite electronics store. The store has several models of each. Monica wants to spend as much as possible for ...
11
votes
5answers
682 views

isPermutation method

I wrote an isPermute method. Can I get some tips and advice on better coding style? ...
11
votes
3answers
8k views

Pairwise combinations of an array in Javascript

I wrote a Javascript function that seems to successfully generate the unique pairwise combinations of a list: ...
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 ...
11
votes
3answers
365 views

Print sums of all subsets

Print sums of all subsets of a given set Problem summary : Print all subset sums of a given set of integers My approach is to store previous results and use them to calculate new (similar idea as ...
10
votes
2answers
357 views

Approximate (250 over 100) permutation best fitting certain criteria

Given a list of 250 words of 4 letters each, what is the fastest way, in Python, to find a subsample of 100 words (drawn without replacement) so that the distribution of letters across the whole ...
10
votes
3answers
670 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 ...
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. ...
10
votes
1answer
900 views

Programming Challenge from Kattis: Apparatus

I am trying to solve apparatus problem, paraphrased below. There is an apparatus with n on/off switches with a one-to-one correspondence to n lights (but with an unknown permutation). We have ...
10
votes
2answers
26k views

Recursive function that generates the permutations of a string

I am looking for a review of my recursive function that generates the permutations of a string. Are there better ways to do this? ...
10
votes
2answers
460 views

A Specific Combination

This code is going to be included in my Minesweeper Probabilities project. (so far it only exists on the develop-branch) The purpose is to return a specific combination, let's say for example that ...
10
votes
1answer
318 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 ...
10
votes
2answers
598 views

Finding all contiguous sublists such that each member appears an even number of times

The program needs to find all contiguous sublists of numbers where the number of occurrences of every member in the contiguous sublist is divisible by 2. The first line of input is N (the number of ...
10
votes
2answers
395 views

You need to diversify your strings

Challenge: Write a program which prints all the permutations of a string in alphabetical order. Specifications: Your program should accept a file as its first argument. The file contains ...
10
votes
1answer
191 views

Counting unordered factorizations with distinct parts

Trying to solve this combinatorics problem, I wrote some functions to count the number of unordered distinct factorizations of an integer n into ...
10
votes
2answers
7k views

Print all permutations with repetition of characters

Given a string of length n, print all permutation of the given string. Repetition of characters is allowed. Print these permutations in lexicographically sorted order Examples: Input: AB ...
9
votes
3answers
2k views

Genetic algorithm for solving a puzzle

Edit. Version 2. I am working on a genetic algorithm in order to solve a little "puzzle." Given a text file with N rows with 4 int each, the idea is to ...
9
votes
2answers
2k views

Binomial coefficient

I wrote a C++ function to calculate the binomial coefficient, trying to avoid overflows as much as possible. ...
9
votes
2answers
874 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: ...
9
votes
2answers
671 views

Optimizing String combinations in Java

I need to obtain all combinations of a String of length k from the given elements. For example, for ...
8
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: ...
8
votes
4answers
1k 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 ...