Questions tagged [combinatorics]

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

54 questions
Filter by
Sorted by
Tagged with
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 ...
52k 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 ...
954 views

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, ...
81k 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 ...
353 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 ...
501 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 ...
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 ...
343 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 ...
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 ...
762 views

Java application for finding permutations efficiently

I am an eighth grader with a school project of creating and application in Java that returns the total permutations of two given numbers. It needs to be light and efficient, for later deployment on a ...
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 ...
368 views

Codility's Permutation Check in C#

I've made a few things in Java, and now I'm learning C#. The code passes the tests with 100% final score. I want to know what things can be improved in my code. Task description A non-empty ...
162 views

Stable reversed Tartaglia's triangles

Inspired by Minimising the triangle I am writing a fully tested program to solve the following problem: A triangle needs a good foundation. Every row in the triangle is derived from the sum of the ...
593 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,...
2k views

An iterator returning all possible permutations of a list in Java

I have this class that iterates over all permutations of an input list: PermutationIterable.java: ...
531 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 ...
262 views

Counting ways to fit bottles in crates

I'm calculating how many possibilities there are to fit $n$ identical bottles inside $k$ crates of various capacities. n = Number of bottles k = Number of crates K = List of the number of bottles ...
472 views

3D bin packing in Java

I made some changes to the first code here I wrote and I want to know which one is more correct logically (before the changes or after the changes). It's really hard to manually test these kind of ...
125k views

Generating all combinations of an array

I'm generating all combinations of an array, so for instance, ["a", "b", "c", "d"] will generate: ...
34k 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! ...
31k views

Permutations of a list of numbers

I have written a program to find all the possible permutations of a given list of items. This precisely means that my program prints all possible P(n,r) values for r=0 to n. ...
15k 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 ...
14k 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. ...
1k views

An iterator returning all possible partitions of a list in Java

Given a list of $n$ objects and an integer $k \in \{ 1, 2, \dots, n \}$, this iterator generates all possible ways of partitioning the elements in the list into exactly $k$ disjoint, non-empty ...
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 ...
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 ...
743 views

I'm new to C#, I programmed a little in java in the past.I had the two previous exercises reviewed here (permCheck, cyclicRotation, with a 100% score, just like this one), and I'm applying what the ...
1k views

Simplified Bin Packing using JavaScript

This code determines the maximum number of boxes (one size) that can fit into the back of a truck, checking all possible orientations to ensure maximum Bin Packing excitement. This is (hopefully) the ...
2k views

Generate next combination in lexicographic order

C++'s standard library has a std::next_permutation algorithm but no next_combination. The reason behind this absence is, I guess,...
104 views

Improving Speeds of Tokenisation of large word list for distinct combinations

I'm having trouble with a current algorithm I'm writing that takes a corpa, a list of characters in sets (1 one or larger) with a frequency number attached to it. Against another list of character ...
5k views

Finding combinations of 3 numbers

What this code tries to do is find possible combinations of three numbers. For example, let's say I have the following numbers: 1, 2, 3, 4, 5, 6, 7 Some ...
3k views

Subset sum problem implementation

Here is a recursive implementation of the Subset sum problem: ...
457 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 ...
1k views

Compute all the permutations for a given vector of integers

The task is to compute all the permutations for a given vector of integers (but of course the specific integer type is not relevant for the solution) The strategy is based on recursion + iterations ...
7k views

Brute-force string generator

I have created a brute-force algorithm class in C# and I was wondering if I could speed up the process of creating a new string. There are two methods inside the class: one returns the brute-force ...
2k views

Finding the given word from jumbled letters

I have tried to write JavaScript code to check whether I can form a word from the given string (jumbled): ...
551 views

Korean word segmentation using frequency heuristic

This a continuation of a previous question. I want to thank Joe Wallis for his help with increasing the readability of my code. Although the changes made by Joe Wallis did increase the speed of the ...
2k views

Consecutive Primes challenge at CodeEval.com and memory allocation issue

I finally solved this challenge with using recursion and figured out why the automatic scorer wasn't passing my previous solutions. I was using NSMutableArray to ...
3k views

Generating character permutations

I want to generate a 'dictionary' containing all 8 character permutations of upper-case letters such that the output file looks like: ...
3k views

Combination generator in Java - 2nd iteration

I have refactored the previous combination generator, and now it is an iterator returning combinations as lists. It hides larger constant factors as the previous version, yet it is really easy to use: ...
7k views

Staircase problem solved using recursion

Problem Question taken from here. I want to go up a flight of stairs that has n steps. I can either take 1 or 2 steps each time. How many different ways can I go up this flight of stairs? Write a ...
783 views

Finding the smallest cube for which exactly five permutations of its digits are cube

(Project Euler #62) The digits of the cube, 41063625 (3453), can be permuted to produce two other cubes: 56623104 (3843) and 66430125 (4053). In fact, 41063625 is the smallest cube which ...
1k views

Combination generator in Java

(See the next iteration.) Given a positive $N$, the following class generates all possible non-empty sets $A \in \mathcal{P}(\{0, 1, \dots, N - 1\})$ in lexicographic order. Also, it provides a ...
184 views

Check is_permutation on a pair of same sized arrays - follow-up

After considering the suggestions of my previous question, Check whether given a pair of arrays are permutation of each other, I changed the code. Resolved the bug reported earlier In place of ...
345 views

Sequence-based enumeration of permutations with Heap's algorithm

Heap's algorithm is an algorithm to generate all permutations of a given array. It ... generates each permutation from the previous one by interchanging a single pair of elements; the other nā2 ...
6k views

Generating all subsets of a given set

I am learning Java Collections Framework. Can someone look at this code for generating all subsets of a given set and tell me any issues with it. ...
3k views

Permutation and combination calculator

I wanted to make something for the Community Challenge, so I made a simple permutation and combination calculator. I'd like input on: The overall design - any suboptimal choices that could be ...
2k views

3D bin packing algorithm using Java?

I wrote a 3D bin packing algorithm but I am still not sure if it is correct or not. I did not follow any code or pseudo-code that's why I would like to know if it is an efficient algorithm for the 3D ...
Does this implementation guarantee execution of $O(n)$ time? What is the additional space utilization for this implementation by excluding the original array size? Is it $O(1)$? ...