Tag Info

Hot answers tagged combinatorics

Accepted

Print all "balanced" sequences of 'A' and 'B'

Refactor to use functions Try to avoid boolean variables. Pseudocode like: ...
• 3,242

Find all combinations of length 3 whose sum is divisible by a given number

Time complexity of iterating through all the combinations is O(n³). We can solve it in O(n²) by using the fact that if you know 2 numbers out of 3, you know exactly ...
• 1,591

Print all "balanced" sequences of 'A' and 'B'

Avoid unnecessary computations The requirement that all prefixes of length $\geq 4$ must be balanced excludes a lot of combinations. For any prefix length, 80% of the combinations of that length are ...
• 110k
Accepted

Find non-overlapping pairs of elements in a list whose difference is less than some given threshold

Your code is doing far too much work. If we sort the list before we start, then we need only compare adjacent elements as candidates. Whenever we find a pair that satisfies our predicate, then add it ...
• 67.7k

Find non-overlapping pairs of elements in a list whose difference is less than some given threshold

You need pairs, not partitions. Your current implementation does a lot of unnecessary work. It looks like you are generating all possible partitions of the input collection and then rejecting the ones ...
• 11k
Accepted

Count five-digit octal numbers with alternating even and odd digits, without repeated digits

As Toby noted, it's not too difficult to calculate the answer. The more you can offload the computer work to insights from your brain, the better your approach will be. But we'll proceed with ...
• 739

Count five-digit octal numbers with alternating even and odd digits, without repeated digits

The code is reasonably clear. It obviously iterates over all possible 5-digit octal numbers, and tests each one to determine if it satisfies the required property. I would suggest renaming the ...
• 67.7k

Subarrays with length

Algorithm When you need to save resources, a better algorithm is always the first thing to look into. Currently, you go over every potential sub-array, and test each element whether it is the length. ...
• 18.4k

Find all combinations of length 3 whose sum is divisible by a given number

As far as clean code which expresses the intent goes, I quite like your little snippet. In fact, it's the sort of thing which, if I were solving this problem in production code, I'd probably use your ...
• 5,966

A more elegant way to uniformly sample from non-negative integers with a fixed sum

Making your current implementation more readable with better naming. Your current code is reasonable, but the function and variable naming don't do much to assist with readability. Better names and a ...
• 11k

Printing subarrays ⚡

Your code is obfuscated The code you have written looks very obfuscated. For example, the outer do-loop does two things: it copies elements from ...
• 42.5k

A more elegant way to uniformly sample from non-negative integers with a fixed sum

"Elegant" is an intangible, so let's specify: Can we make it faster? Yes (a lot!) Can we make it stay in the numeric domain instead of a weird venture into strings? Yes! Can we code-golf it ...
• 55.5k
Accepted

Boolean evaluation

Time complexity cannot be $n^3$. There are just too many ways to parenthesize the string, and the code inspects them all. I run an experiment counting a number of calls to ...
• 54.6k
1 vote

Effective encoding-decoding chain determination (time optimization)

I don't know if it good enough for you, but if pre-calculations do not count, you can use the solution below. Basically, I compute all options from ПРОЦ and when ...
• 151
1 vote

An algorithm that minimizes the number of ingredients necessary

With such a small input dataset, it's already fast and I wouldn't worry about either algorithmic optimisation or micro-optimisation. I do think you should unravel your generator to a generator ...
• 55.5k
1 vote

A more elegant way to uniformly sample from non-negative integers with a fixed sum

This is longer, but more readable, and if you can reduce the loop with syntactic sugar we might even have an elegant solution ...
• 856
1 vote

Subarrays with length

Check the repercussions of using namespace std;, especially in headers/source to be included. The code presented gives no clue what it is to achieve: Document your ...
1 vote

Pascal's triangle solution in Python code

Use functions. You have a review with some useful advice, and its best advice is that you organize your programs around functions. Here I'll extend that idea. Functions should be focused. If we take a ...
• 11k
1 vote

Pascal's triangle solution in Python code

PEP 8 The Style Guide for Python Code has many recommendations that all Python programs should follow. These include: snake_case for variable and function names, ...
• 32.9k
1 vote
Accepted

Subset Product Algorithm

Reasons to put code in functions (and classes): Code on module level is evaluated right away: I can't try it out using copy&paste if there is an input() ...
• 5,363
1 vote

Brute Force Algorithm in C

This part of the code has a common beginner error: ...
• 67.7k

Only top scored, non community-wiki answers of a minimum length are eligible