6
votes
Accepted
Generating all possible permutations in the fox, goose and beans problem
Start with deciding how to represent the state.
A simple approach is to say that the state at a location is a string of length 4 in which each character is one of FGBX_. There are three locations, ...
- 18.4k
5
votes
Accepted
How do I narrow down a search space if symmetries are equivalent?
Each of the 3^25 combinations can be interpreted as a 25 digit number in base-3 number system. So there is a one-to-one correspondence between those numbers from 0 to 3^25-1 and those combinations / ...
- 221k
5
votes
Accepted
Software-design for algorithm engineering
Does this mean the OOP paradigm is not a good fit for this category of problems? Or am I simply not experienced enough with OOP to utilize for this domain?
You can use the OOP paradigm to encapsulate ...
- 27k
4
votes
Birthday Paradox, Analytical and Monte Carlo solutions give two systemically slightly different results
Consider when your number of people, n, is 366.
Using your proposed analytic solution for n=366,
you get NumPairs = n*(n-1)/2 = 66,795.
You then say that the probability of two people having
...
- 141
4
votes
Accepted
How to generate "meaningful combinations" from the set of characters?
You have a dictionary that allows to confirm that a given combination is meaningful. But brute force is too expensive, so you want to optimize the search by pruning the search tree:
I am not aware ...
- 82.3k
3
votes
Accepted
Calendar scheduling: home field constraints
You have broken down the problem into match-up selection and scheduling, and of course, this break down constrains the scheduling.
You're thinking of some way to revisiting some of the match-ups when ...
- 34.8k
3
votes
Designing a builder as a compile-time state machine
The only meaningful way I can think of "the builder with internal state" is something I've read long time ago in this blog post.
The idea is similar to proposals in comments which can achieved with ...
2
votes
Accepted
Generating combinations without getting stuck in recursive calls
You are performing a traversal of a directed graph using a Depth First Search. You need to mark each node you visit so you don't visit it again. In your case, you mark nodes by adding them to ...
- 4,749
2
votes
How to generate "meaningful combinations" from the set of characters?
If you have a list of entities which are meaningful (such as a dictionary of English words), you can do it in the opposite direction: walk through the list and select the words which contain only ...
- 139k
2
votes
Accepted
Time efficient way to count pairs in an array whose sum is divisible by a specific number?
Solution in O(N) time and O(N) space using hash map.
The concept is as follows:
If (a+b)%k=0 where
a=k*SOME_CONSTANT_1+REMAINDER_1
b=k*SOME_CONSTANT_2+REMAINDER_2
then (REMAINDER_1 +REMAINDER_2 )%...
- 212
2
votes
Eliminating combinations based on user input
Here is a short outline how to approach this for "not-too-large" number of goods in an optimal manner:
Start with a configuration of boxes which fulfills all the constraints (but isn't ...
- 221k
2
votes
Eliminating combinations based on user input
One way to solve this is to treat it like a graph problem:
Which means this:
"Flammable Liquid" "Oxidizer"
"Flammable Liquid" "Organic Peroxide"
"...
- 120k
2
votes
Algorithm for multi-dimensional maximisation
"Knapsack" is not an algorithm, it is a class of problems, so knowing if your problem falls into this category does not give you an algorithm.
So yes, your problem is actually a special case ...
- 221k
2
votes
Accepted
How to find all combinations of all items in a set?
The name for this is Cartesian product.
Python has a function for this, and the documentation for it shows code that's roughly equivalent to what the function itself does:
def product(*args, repeat=1):...
- 268
1
vote
Software-design for algorithm engineering
Depending on your long term needs, keeping those data structures in global variables might be just right if you're using the program in isolation.
As soon as you want to use the algorithm as part of ...
- 18.6k
1
vote
Software-design for algorithm engineering
Let me guess: this is a program
only for academic purposes, which will probably have a restricted life time
in the range of 2K lines of code up to 20K at most
with just one developer (you)?
Then ...
- 221k
1
vote
How to find all combinations of all items in a set?
Lets say there are n different attributes, the first one having k1 different values, the second one k2, ..., the n-th one kn.
The most straightforward algorithm here is to implement an odometer. Just ...
- 221k
1
vote
How to model combinatorial information in RDBMS
You need to properly model your domain. You are modeling products. You need to model both products and product-variants where a product-variant is a particular product with specific attributes.
Both ...
- 762
1
vote
Accepted
Calendar scheduling: wait time between games
A simple way of approaching this in a pragmatic manner could be:
allow games to be scheduled initially on slots violating the contraints, so you can start with a schedule where each game gets a slot
...
- 221k
1
vote
Accepted
Determining resource exhaustion beforehand
In general, this looks like an NP-complete problem. This means that a brute-force approach is essentially the optimal solution (that we know of) if the compatibility table can be any value at all.
In ...
- 111k
1
vote
Scheduling: balanced home/away round-robin tournament algorithm
I ended up going with something like this. Deff could use some cleanup and de-duplication.
import collections
teams = [1, 2, 3, 4, 5, 6, 7, 8, 9]
rounds = 8
schedule = []
teams.insert(0, None)
d = ...
- 19
1
vote
Spreading objects in bags and bags' compartments
This part is not necessarily clear from your problem description but I am going to assume that you can only put one object per compartment.
If you drop the fact that putting together object x and y ...
- 382
Only top scored, non community-wiki answers of a minimum length are eligible