Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.
17
votes
2answers
242 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
129 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 ...
2
votes
2answers
90 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
85 views
4
votes
2answers
124 views
Find co-occurrence of elements
My input consists of a list of lists (not necessary of the same length), like
...
7
votes
2answers
241 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
42 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 ...
1
vote
0answers
84 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 ...
4
votes
2answers
121 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 ...
2
votes
0answers
55 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
64 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 ...
3
votes
2answers
116 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 ...
7
votes
1answer
68 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 ...
5
votes
1answer
66 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
112 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, ...
5
votes
2answers
99 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
64 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
63 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.
...
0
votes
1answer
305 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 ...
3
votes
2answers
92 views
6
votes
1answer
182 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
223 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
42 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
86 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 ...
8
votes
2answers
98 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
959 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
68 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 ...
4
votes
2answers
75 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
98 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 ...
2
votes
2answers
136 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
377 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
68 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
145 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
49 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):
...
1
vote
1answer
84 views
Counting friends of friends of friends
Can you comment, review or suggest things for this? Maybe it should be broken into two methods?
friends is a list of strings of ...
6
votes
1answer
73 views
Project Euler #62 + Java 8 streams
(Inspired by this question)
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 ...
15
votes
2answers
281 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 ...
4
votes
5answers
628 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 ...
3
votes
2answers
231 views
All upper and lowercase permutations of a string
A couple of questions:
Is the algorithm wasting CPU time or memory unnecessarily?
If there is something in the code that is not idiomatic Python, how to improve on that?
...
3
votes
2answers
258 views
Permutations in C#
I have a program that will get all possible permutations of a certain equation:
A + 13 * B / C + D + 12 * E - F - 11 + G * H / I - 10 == 66
Where A, B....I is a value 1-9, and where each digit ...
3
votes
3answers
661 views
Letter combinations of phone dial pad number
In preparation for interviews, I have written a solution to this question:
Given a sequence of numbers (34128) and an input map such as a dial
pad on a phone (2->[a,b,c], 3->[d,e,f], ...
5
votes
1answer
97 views
Safe cracker string with all combinations
Imagine a safe with a 4-digit code, and accepting a continuous stream of code entries, such that when the 4 digits are seen in the right sequence, the safe opens. Generate a short string that ...
4
votes
2answers
68 views
4
votes
1answer
251 views
Password Attacker (Google apac test problem)
Original Problem
Short Summary:
Given a \$M\$ possible characters all of which must be used at least
once, find the number of possible combinations of length (exactly)
\$N\$.
The ...
4
votes
5answers
187 views
Permutation of n lists
I have code which gives permutations for 10 lists. The code works fine for small number of lists with small number of values.
Result : It should return all possible permutations. I have to store the ...
5
votes
1answer
585 views
Solving the 'Vietnamese school maths problem'
Having read Can you do the maths puzzle for Vietnamese eight-year-olds that has stumped parents and teachers?, which presented the problem of filling in numbers 1 to 9 to satisfy
$$ a + 13 ...
0
votes
2answers
84 views
Unique combinations of sets with N min selections of overall set
I'm in the process of attempting to write a parser compiler. In this, sets play a major role. I'm in the 'lexical ambiguity' isolation phase, and to that, I need to yield a set of every possible ...
2
votes
1answer
90 views
Generating alphanumeric combinations
I was happy with my shell script that needed to generate alphanumeric combinations of length N (in this case, 3)
for i in {a..z}{a..z}{a..z}; do ...
Now I became ...
2
votes
1answer
41 views
Generating combinations of n elements in groups of k
I've written this program that writes all the combinations (without repetition) of n elements in groups of k.
I think the code is good, but I like to know if you have some better (or faster) ...
3
votes
1answer
88 views
Necklace counting problem-with consecutive prime constraint
This is codeEval challenge to count the number of chains possible to make with beads holding numbers. Constraint is sum of the consecutive beads of chain should be a prime number.
The standard ...
