Tag Info

New answers tagged

0

I have modified the original Cantor's formula for pairs: pi(k1, k2) = 1/2(k1 + k2)(k1 + k2 + 1) + k2 To this custom one: pi(k1, k2) = 1/2(k1 + k2)(k1 + k2 + 1) + (k1*k2) So far all unique numbers, no matter f(A,B) or f(A,B). If anyone can improve the algorithm, you are welcome, I am not that good at math calculations and progression. Here's a ...


2

If only problem is that you want the two numbers to be interchangeable, then just sort them. Make it so bigger number is always first and smaller second. Then you can use the Pairing Function you already tried.


4

It's easy to come up with a scheme, but you need a number range that is at least as big as the square of the possible number range for ids. Otherwise you cannot guarantee what you need, i.e. that the combined value is unique (google "pigeonhole principle"). This probably means that you need a bigger data type to store the combined number than for the id. ...


0

If you only want to limit rotation to 45 degrees, you don't need to use sin and cos, for that particular case I would advice you to use a fast isometric diamond drawing algorithm and adapt it to your matrix. Usually a couple nested loops and 4 variables (x, y, width, height) will do it.


1

For this problem, I used a Place/Transition (P/T) Net. I used the “standard” graphics for P/T Net with two modifications: changed the token colour from black to “reddish-orange”, added a bounding box with dashed lines to represent a process. I modified the labels you used for processes and resources – instead of starting from 1, I started from 0. Then I ...


1

Randomly distribute the most numerous tile so that there are no adjacencies. Then randomly distribute the next most numerous tile, and so on. That should work well unless the two most numerous tiles cover almost the entire rectangle.


0

The big O notation is defined as a set: So contains all functions that are - starting from some arbitrary large point - always smaller than g. Now, when you have a function that is in and then execute another one that increases slower than g it is certainly increasing slower than 2g. So executing anything slower than g will not change the complexity ...


1

I answered a similar question at http://stackoverflow.com/questions/26028124/the-intersection-of-all-combinations-of-n-sets/26028865#26028865 and the only difference in what you need is that the second map should map an element to the set of sets it is in, rather than every subset of that set.


5

Don't get hung up on this. It is paralysis by analysis. What if I told you Haskell was the best language? Would that help you? What if you don't know Haskell? That is why this is subjective and off-topic, but it is still an issue that beginners struggle with ("Which language is better...") The best language for you, right now, is the language you are most ...


1

For maximum efficiency, use your set of keywords to create a Pattern, e.g. Pattern p = Pattern.compile("circle|ellipse|parabola|hyperbola|conic\s*section"); Matcher m = p.matcher(text) while (m.find()) { ... } This is about as fast as you can go in Java.


2

Start with the definition of O (): O (n log n) means "less than C n log n, if n is large". O (n) means "less than D n, if n is large". If you add both, the result is less than C n log n + D n < C n log n + D n log n < (C + D) n log n = O (n log n). In general, if f (n) > C g (n) for large n and some C > 0, then O (f (n)) + O (g (n)) = O (f ...


0

If your matrix can be accessed as a 2D array (x, y), then your problem generalises to new(x, y) = old(x, y) * (1 - 0.2) + old(x + 1, y) * 0.2 for all but the last column. The last column is a special case. Either use new(x, y) = old(x, y) * (1 - 0.2) for that column only, or else pad your source array with an extra column of zeros first and then you ...


5

If you were going to set it out longhand it would look roughly like this: Suppose the total time is: a n + b n log(n), where a and b are constants (ignoring lower order terms). As n goes to infinity (a n + b n log (n)) / n log (n) -> a / log (n) + b -> b So the total time is O(b n log(n)) = O(n log (n)).


1

Bin packing is very computationally difficult. Think of half of the problem: you want to pack product in shipping boxes with no wastage in the box. An optimal solution for that would require going through all possible subsets and all possible 3d arrangements of the product that needs to ship in one truck. I'll give you the optimal solution for that because I ...


50

Let's reason our way through it and remember the definition of O. The one I'm going to use is for the limit at infinity. You are correct in stating that you perform two operations with corresponding asymptotic bounds of O(n) and O(nlog(n)) but combining them into a single bound is not as simple as adding the two functions. You know your function takes at ...


59

O(n) + O(n log(n)) = O(n log(n)) For Big O complexity, all you care about is the dominant term. n log(n) dominates n so that's the only term that you care about.


0

Unless your edges have attributes (which you didn't state) the simplest way is to not add edge A → B if A → B already exists. This is how decentralized flooding mechanisms (e.g. USENET) keep from forming cycles. As far as what objects should know what they are connected to, you've got a space/time trade-off: you can have nodes know edges or edges know ...


1

To find the four longest distances, you need to search over all the distances. So for n nodes, you need to loop through n^2 distances, and so something like: if dist > smallest_max replace smallest max in array of four maximums with dist recalculate the smallest max from array This is O(n^2), which is not good but it's not exponential like ...


1

I don't remember how to play Stratego, but in general if you want to encourage a certain type of behaviour in your AI (i.e. being offensive) you have to award some value to that kind of behaviour. Think about evaluating each potential move on its impact to the overall strength of a position. Ask: "what are the chances of my position being better or worse ...


3

Designate some of the AI pieces as offensive you should assign certain pieces an offensive role. You would then need to decide whether an offensive or defensive move should be taken on a particular turn. Try to use low number pieces, 2,4,5 for scouting and figuring out pieces' ranks (you can also inadvertently run into the flag this way) then send in threes ...


1

This is the classic bin-packing problem. It is classic because it can be applied to so many tasks that we'd like to optimize but it is computationally NP-hard.


0

Here's a working solution with decent performance. ordered = lambda x, y: (x, y) if x <= y else (y, x) def makeArrows(edges): """ input: a sequence of (src, dst) pairs, maybe some reciprocal. output: generator yielding (src, dst, is_double_ended) triples. """ undirected_edges = set() for src, dst in edges: edge = ordered(src, dst) # ...


1

So, after working on the algorithm a little more I got it working. The answer to my question is: It should be shifted n - l′(i) characters to the right even when l′(i) = 0. When l′(i) is zero, that means the following: L′(i) is zero. So no reoccurring substring was found to the left that has a differing previous character. E.g: mismatch: ...


1

Technically no, you can't antialias an existing line because you don't truly know where the bounds of the line are--or mathematically where the line exists in relation to the surrounding pixels. Add that to the fact that the line actually obscures underlying pixels--which can't be blended into line. You could smooth the image; but I don't believe that's ...


0

Just collect the pairs in a set. (In Ruby, it will be a Set of two-element Arrays.) let Set s = {} for each pair [a,b] if s contains [a,b] // duplicate, do nothing else if s contains [b,a] // converse duplicate ... else add [a,b] to S If you are writing Ruby, it is already capable of using arrays


3

As people are hinting in the comments, if you want to do this for the fun of doing it, that's one thing, but if you want a library of scientific functions to use, you should use one that's already been written by experts. There's a list at http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic#Libraries The open-source libraries listed there are also ...


0

You're asking about a class of equivalent problems i.e. the bin-packing algorithm (which is NP hard see http://en.wikipedia.org/wiki/Bin_packing_problem). You can't guarantee a perfect solution for any number of customers and sticks within a (reasonable) linear amount of time. What you can do is use heuristics to get a 'best effort' solution. Check out bin ...


3

This particular problem is a variation on a well known (and well studied) problem known as the cutting stock problem. In the classic definition of this problem, consider that you have large rolls of product of a given width. You need to cut them into the smaller width rolls with minimum waste (and knife changes): The reason that this is so well studied ...


0

I did some work in a college operating systems class about allocation of memory blocks with different sized files using the best-fit, worst-fit, first-fit algorithms, which if you think about it is essentially the same process for this problem. The overarching theme was without knowing all of the requests ahead of time you can't go through all the possible ...


2

You're imposing three constraints here: a specific total number of questions several pools of questions of similar difficulty, where the exam should contain elements of each pool a predefined average difficulty As ratchet freak said, this is a knapsack problem and therefore hard to solve, although if the list of questions is reasonably small a complete ...


1

I do not think it is possible to deterministically build such a random set in "one go", whatever it exactly means. However here is what I think is the closest alternative: Start with N random numbers. As long as your average is not satisfying, randomly remove a number and replace it with a smaller/larger one. To quickly find the numbers to remove and their ...


1

Well, why not start with a very simple approach? You have "level 0" fields where the user can enter values, "level 1" fields which only depend on "level 0" field, "level 2" fields depending on "level 1" or "level 0" fields, and so on. Behind each "level n" field with n>0 there is a function which takes care of incomplete input values (like C = f(A,B) with ...


1

The tecniques are the good old: invalidations, lazy init, wrapping each control in a 'node' of a recalc-graph. But i feel that there should be a more canonical approach to this recurrent problem, and a paper where this approach is explained and so on. Can anyone suggest me where can i find such information? I believe the canonical approach ...


1

Assuming the amount of recalculation is trivial, then some kind of Model-View-Controller structure would be appropriate: The user changes B The View notifies the Controller (via event, etc.) that B changed (or that something changed) and the Controller passes B (or everything editable) to the Model. The Model updates internal values and exposes the values ...


0

Brute force may not be feasible for even small datasets. I have written something like this in my beginnings, in C#. I used a genetic algorithm. The source code (hosted at Codeplex) is awful, I didn't know any better at the time. But you can take a look at the video presentation: http://vimeo.com/20610875 I start talking about the subject of your ...


0

This is written from the pragmatic point of view. Don't reinvent the wheel. You are better off learning and using a known piece of software than writing your own scheduling program that likely won't preform as well and will be 'fun' to maintain - both for you and the next guy. Scheduling problems are hard... and not just hard, but they can often be NP-hard. ...


1

This problem is harder than solving it for 2 invoices (just group all invoices but one). If we try solving it for 2 invoices and 1700 bills we see that the sum of the 2 invoices is equal to the sum of the 1700 bills, so all we need to find is a subset of the 1700 bills whose sum is equal to one of the invoices. Thus we have a subset sum problem, which means ...


0

To get started with, God's Algorithm is not an algorithm. There is no particular way in which you can solve different permutations of cube with that algo. What creators of god's algo did: Partitioned the positions into 2,217,093,120 sets of 19,508,428,800 positions each. Reduced the count of sets we needed to solve to 55,882,296 using symmetry and set ...


0

I assume that you are not pursuing GPU computation just for the sake of it. In other words, you are willing to consider CPU or "traditional techniques", comparing multiple techniques, and finally choosing whatever gives the highest performance, instead of having to stick to using GPU in order to make a thesis. I find that Chain Code (contour tracing) ...


4

BigO is, simply put, a measure of algorithm complexity. In a best case scenario, even the worst algorithm may be finished in one operation/iteration. However, different operations have different average- and worst-case complexities. These worst-case complexities could be considered the upper bound. So, how can we figure out the upper bound? An algorithm ...


1

If you need to consider multiple crontab entries for the same task, you will have to iterate through a full 400-year Gregorian cycle. For example: 59 23 29 2 * me /home/me/mytask # 11:59 Feb 29 01 00 1 3 * me /home/me/mytask # 00:01 Mar 1 These events will occur two minutes apart every leap year Worse: 59 23 29 2 * me /home/me/mytask # 11:59 Feb 29 01 ...


1

The divide and conquer algorithm has 3 steps at each level: A recursive call on the left half. A recursive call on the right half. Calculate the maximum mixed sum. Steps 1 and 2 are recursive, they just call the function again using the new end points. Step 3 is not, it just uses the fact that the sum/product must include the border values to make only ...


3

Every sort algorithm has a worst case, and in many cases the worst case is really bad so it is worth testing for it. The problem is, there is no single worst case just because you know the basic algorithm. Common worst cases include: already sorted; sorted in reverse; nearly sorted, one out of order element; all values the same; all the same except first ...


0

Ben Aaronson's answer is much better than either of my attempts, but I think the main reason is the technique he uses to iterate through the tree, using two Node pointers instead of one, rather than the more object-orientated style. The whole thing can be inlined, which allows a direct comparison with my version and shows that it is indeed more elegant, ...


0

There is no way to do what you want to do in Java. Java doesn't offer the freedom of C when dealing with pointers. The only pointers Java has are object references. Your first attempt is therefore as good as you can do in Java. You have to distinguish the case of left, right and root insertion. If creating and initializing the node is complex, you can ...


0

You can avoid the repetition by creating the new child Nodes earlier and defaulting them to empty, rather than using null to represent an empty Node. The body of your while loop might look something like: Node child = node.right; if (k < node.key) child = node.left; if (child.isEmpty()) { child.set(k, v); child.left = new Node(); //Could ...


5

Part of the problem is that you're not following good OO principles. In this case, the one that's probably most applicable is "Tell, don't ask": If you want a Node to add a child, you should tell it to add a child, you shouldn't ask it to expose all the relevant information you need then go ahead and add the child for it. Likewise, if (because you're doing ...



Top 50 recent answers are included