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
3
votes
3answers
357 views

Searching a string for any permutation of words

Given a string and an array of words, return all indexes in string for which a concatenation of all words in the array, in any order (so ["eensie", "weensy", "spider"] has six orderings) can be ...
7
votes
1answer
1k views

Recursive program for generating and printing all permutations of the numbers 1, 2, …, n for given integer number n

I've just written code for generating all permutations of the numbers from 1 to n in Java. It seems to work, but I think it's a bit more complex than it needs to be. ...
5
votes
1answer
572 views

Permutation function in C#

One thing lead to another and eventually I wanted to know the "proper" way of writing the permutation generating function in C#. Below is my code for generating permutations. This will go into an ...
11
votes
5answers
682 views

isPermutation method

I wrote an isPermute method. Can I get some tips and advice on better coding style? ...
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 ...
2
votes
3answers
356 views

Finding tuples of numbers subject to constraints

I just watched the video from "Think Like a Programmer, Episode 2: Puzzles & Problems". The problem is: Assign number 1-7 to three departments in a city: Fire, Police, Sanitation. ...
7
votes
1answer
689 views

Finding permutations of a word

This was a basic anagram problem. Take an input word, find all its permutations, then check a dictionary file to see what if any of those are real words. Dictionary file My input data: ...
12
votes
1answer
332 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 ...
10
votes
1answer
927 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 ...
15
votes
1answer
322 views

Permuting a typelist

Given a typelist, return a typelist of all the permutations of it. For example: ...
5
votes
1answer
234 views

`r` permutations of `n`

I have written this snippet to find r-permutations of n, i.e. if I have an array of n=3 {0,1,2}, then r=2 permutations will be {{0, 1}, {0, 2}, {1, 0}, {1, 2}, {2, 0}, {2, 1}}. Can somebody review it ...
7
votes
2answers
2k views

Generate all combinations of certain digits

Related to another answer of mine on Project Euler 35, I found the need to calculate all combinations of certain digits, i.e. 1, 3, 7 and 9, below a given n. I ...
3
votes
2answers
75 views

Find unique variants of a product

I am writing a piece of code that returns all the unique variants that a product is available in for an ecommerce app. For example, a shirt product can be available in different colors, sizes, and ...
1
vote
1answer
78 views

Coins problem in Erlang

How many different ways can 200 be made using any number of coins? The possible denominations are 1, 2, 5, 10, 20, 50, 100, 200. ...
3
votes
2answers
987 views

Generating all permutations of a sequence

...
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 ...
4
votes
1answer
253 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 ...
3
votes
2answers
2k views

Non-Contiguous Substrings

Problem: A non-contiguous substring of string \$s\$ is a sequence of \$k \geq 0\$ characters in \$s\$, in the order in which they occur in \$s\$. For instance, the set of all non-contiguous ...
8
votes
3answers
2k views

Generate all elements of a power set

...
5
votes
2answers
3k views

Find co-occurrence of elements

My input consists of a list of lists (not necessary of the same length), like ...
7
votes
2answers
788 views

Generating 3 combinations in Python

I have been experimenting around with generating all the n-combinations of an array. This code quickly generates all \$\text{k-combinations}\$ of a given array. I am testing my own implementation ...
2
votes
2answers
94 views

Method for finding all classes

This was inspired by a Stack Overflow question about getting all the classes of an application and I took it a little too seriously (or perhaps not seriously enough). It's rather silly to do it this ...
3
votes
0answers
2k views

Brute force shortest path in Java

I had to ask myself a couple years ago: before Edsger Dijkstra invented his famous shortest path algorithm, how brute force approach would seem. Below is my version. It's super slow, but I find it ...
5
votes
2answers
1k views

Make 10 from the numbers 1,1,5 and 8 using the 4 operations, by brute force

I tried to calculate the following problem by brute force using R (under the assumption that a single pair of parenthesis would suffice). Make 10 from the numbers 1, 1, 5, 8. You can use the ...
7
votes
1answer
659 views

Non-recursive permutations and strings generator

Inspired by Sam's question (Brute-force string generator) and rolfl's really short version of the algorithm I started to experiment with a different approach and created one that seems to run a little ...
3
votes
2answers
1k views

N-queens problem in Haskell by bruteforce

I wrote a Haskell program to solve the N-queens problem by bruteforce. It works and I find it reasonably readable But it is pretty slow: 5 seconds for one solution of 8 queens. 1 minute for one ...
6
votes
2answers
6k 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 ...
8
votes
1answer
798 views

Recursive search for combinations of words that have a specified MD5 hash

This code solves a challenge problem that a local company is hosting to attract/screen applicants. The link to the challenge is here. In brief, we are given a wordlist containing approximately 100,...
6
votes
1answer
4k views

Permutation algorithm of N unique elements with low memory footprint

I actually had a real life need (outside work, no less) to come up with every single permutation of N elements (the N in my case being 12, so a total of ...
4
votes
1answer
281 views

2D Fenwick-tree with combinatorics and modular arithmetic

This is a contest problem; Description: In the winter, children started to build snowmen. The snowmen were becoming adorable, except for a detail: none of them had a nose. The king, touched, ...
6
votes
2answers
2k views

Displaying all permutations of a string

I am using this code to display all the permutations of a given input string. Any advice/solution will be very helpful. ...
2
votes
1answer
717 views

Generate all possible permutations from a string with character repetitions

I want to know if my code is good, with reasonable efficiency, and if it is possible to improve my code and how. What would you suggest? ...
-2
votes
1answer
291 views

“Finding possible candy permutations” HackerEarth challenge

Problem Statement Shil, Aditya and Utkarsh go to a candy shop. There are N candies present in the shop, which are indexed from 1 to N. All three of them select one candy to eat. However, ...
0
votes
1answer
1k views

Print the lexicographically smallest permutation that satisfies the given formation

Problem Statement: A DOTA game has N heroes, each with a distinct rank from [1..N]. In DOTA every formation is characterized as a permutation [1...N] of ranks of players. A formation is Imba ...
4
votes
2answers
654 views

Heap's algorithm - integer permutation

Integer permutation using Heap's algorithm: ...
6
votes
1answer
2k views

Permutations of a list in Haskell

I have this piece of code which given a list returns another list which combines every element with every other element (without repetitions) using a given function as a combiner. I came up with three ...
10
votes
2answers
397 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 ...
6
votes
1answer
85 views

Sentence maker with thesaurus

I'm teaching myself Ruby by rewriting PHP solutions, such as this one. The program should match words in a sentence with a dictionary of synonyms and then make combinations with them. ...
6
votes
1answer
481 views

Print permutations in an iterative way

I've written the following code to print all the permutations of a list. For example: \$[1, 2, 3]\$ has these permutations: \$[1,2,3]\$, \$[1,3,2]\$, \$[2,1,3]\$, \$[2,3,1]\$, \$[3,1,2]\$, and \$[3,...
7
votes
2answers
2k views

Summing all numbers that can be formed from a list of integers

Following a challenge on HackerRank, I want to find the sum of all numbers that have no more than x 4's, y 5's, and ...
4
votes
4answers
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 ...
5
votes
2answers
254 views

Applicative permutation to generate knight moves

I want to understand Haskell better by trying to stretch possibilities of Functor, Applicative, and Monad as much as possible and study how they behave. So in Learn You a Haskell there's an exercise ...
2
votes
1answer
873 views

Insect combinatorics challenge

Below is the problem taken from Berkeley's Cs61A page here Question 9: Insect Combinatorics* Consider an insect in an M by N grid. The insect starts at the bottom left corner, (0, 0), and ...
5
votes
2answers
497 views

Linear cryptanalysis of a substitution permutation network

I was translating a script I had that would automate linear cryptanalysis of SP networks from Python to C++. For those who aren't familiar with cryptography, linear cryptanalysis involves finding ...
3
votes
1answer
158 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 ...
2
votes
2answers
763 views

Count the number of combinations with gap-restriction for every pair of values

A lottery draw consists of choosing 6 different values from 1 to 50. I want to calculate the number of combinations with gaps of at least 3 between every pair of values. I have used the following ...
5
votes
2answers
7k views

Minimum number of coins to make change

I am new to programming and I am taking CS50 2014 online through iTunes University. This is the change-making problem in Problem Set 1: Write a program that first asks the user how much change is ...
1
vote
1answer
105 views

Printing all factorizations of a number

For example, if we have 120, the answer should contain (2,2,2,3,5),(2,60),(4,30),... Here is my not-so-good attempt ...
10
votes
1answer
193 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 ...
2
votes
1answer
140 views

Project Euler #70: Time Efficiency Improvement

The problem was to find which \$n\$ for which \$\varphi(n)\$ is a permutation of \$n\$ and \$n/\varphi(n)\$ is minimum,now as we all know that means (simple conclusions from mathematics): \$\varphi(n)...