Join devRant
Do all the things like
++ or -- rants, post your own rants, comment on others' rants and build your customized dev avatar
Sign Up
Pipeless API
From the creators of devRant, Pipeless lets you power real-time personalized recommendations and activity feeds using a simple API
Learn More
-
@modislaszlo What do you mean by move the smallest weight number? Swap the cheapest pair which needs a swap? Anyways either this and bubble-sort work well for (a), pretty fast :) now try (b)
-
@SirWindfield If by a tree you mean searching all possible swaps (BFS/DFS), I did that and it works for lists of up to length 10, otherwise it runs forever. I need something for larger lists
-
@matanl it's because you have to perform same computations many time .Store them so that you can avoid those and you are good to go
-
@anekix I need a polynomial time algorithm, it's theory as I stated. What you suggested might work for lists of size 12 or 15 but not 100
-
@matanl did you try what I said?Because it will work for lists of size 100 .Complexity will.be somewhere o(n^2)
-
@matanl And yeah this is not an open problem of cs in same way knapsack is not or coin change or log cutting or minimum steps problem or LCS (longest common subatring) or Longest increasing subsequence problem and tons more are not open problems. Isn't n^2 polynomial time?
-
@matanl please read about solving edit distances and you will get an about how big an input can be in your case list of 100 numbers is nothing you can go 10000000000x and still smooth
-
@anekix if I remember correctly, all the problems you mentioned are not known to be in P complexity class, i.e. they're exponential. For example, knapsack is exponential in the number of bits required to represent the target sum. Since this is a permutation we count number of bits and not the value of the number. Look for pseudo-polynomial definition. Hence, they're exponential in time and not n^2 as you suggested. This problem can definitely be solved in n! steps but I'm looking for a way to solve it in polynomial time. Btw the weight [1,2,3,4,3,2,1] was proven by my office partner to have a polynomial time solution. The weight suggested in (b) still doesn't have such solution
-
@anekix So my friend got up with a linear programming solution (there's a chance it will not work since it's linear and not integer), and it is polynomial like you suggested. I wan't really familiar with this tool so thanks for mentioning it :) I think it's like O(n^12) and not fast enough, but maybe will be enough for me to finish with this project.
-
@matanl glad you got it working. If you read upon this technique of solving problems you will understand why it's n^2 so very fast and I can assure you this is a medium difficulty problem you just have to know the right method.i will give you some links to study upon if you want.
-
@anekix n^12 and not n^2, fair enough though, it's polynomial
Yes! 😎
Hope this hasn't been posted before, found it hilarious.
From /r/ProgrammerHumor
Almost every f*****g time :(
Guys I heard a rumor that you like riddles, I'm stuck on my theory project and I'd like to throw a bone:
Say you have a list p = [7,6,2,3,4,5,1,0] and you want to order it, i.e. change it to [0,1,2,3,4,5,6,7], by swapping adjacent elements. Provide an algorithm to do this optimally, when:
a. (Warm-up) each swap costs 1
b. Swaps weight is [4,3,2,1,2,3,4], i.e. if you want to swap position 0 with 1 it'd cost 4, position 3 with 4 will cost 1 and so on.
The optimal overall cost for b is 50 (I did an exhaustive search), however you need to find a general approach which is able to order every list with minimal overall cost (no time constraints as long as the solution is not exponential in the list length), using the provided weight function.
(you get a credit if the solution goes to a paper or anything 😉 it's actually a computer science open problem, but seems possible to me)
undefined
riddle
algorithms