Fill values X from values Y
I'm trying to create an algorithm to fill some values X (e.g. 10,000, 50,000, 100,000) from another set of values Y (e.g. 2500, 5000, 10,000, 42,500, 27,500).
Aim: To get the highest total filling of values X.
Rules: Can't repeat any value Y. Any value X must be entirely filled to count.
I've tried to knapsack this but it doesn't work very well because it creates huge value arrays. Any ideas?
Edit for more clarity:
An array of values X (ValueX), and an array of values Y (ValueY). Fill each individual value from ValueX, using any combination of values from ValueY. Once a value from ValueY has been used, it cannot be reused.
Example:
Fill ValueX[0] (10,000)
You could use ValueY[2] (10,000) and that would fill it completely. However now ValueY[2] cannot be reused for future filling of any ValueX.
If you then tried to fill ValueX[1] (50,000), you could use ValueY[3] (42,500), ValueY[1] (5000) and ValueY[0] (2500), to get a total of 50,000. Now those values(3, 1, 0) from ValueY have also been used.
See also questions close to this topic

How would I go about changing the font and size in this arraylist?
I want to change the font size and the font style. The font is too small. I have tried a few things, but none of it seems to be working. How do I go about doing this?
Here is the window that's created:
public class Questions { public ArrayList<String> mind = new ArrayList<>(); public ArrayList<String> energy = new ArrayList<>(); public ArrayList<String> nature = new ArrayList<>(); public ArrayList<String> tactics = new ArrayList<>(); public ArrayList<String> identity = new ArrayList<>(); Questions(){ pullMind(); pullEnergy(); pullNature(); pullTactics(); pullIdentity(); } public ArrayList<String> pullMind() { mind.add(" You feel more energetic after spending time with a group of people."); mind.add(" If someone does not respond to your email quickly, you start wondering if you said something wrong."); mind.add(" If the room is full, you stay closer to the walls, avoiding the center."); mind.add(" You feel very anxious in a stressful situation."); mind.add(" You do not usually initiate conversations."); mind.add(" You usually find it difficult to relax when talking in front of many people."); mind.add(" An interesting book or a video game is often better than a social event."); mind.add(" You find it difficult to introduce yourself to other people."); mind.add(" You do not mind being at the center of attention."); mind.add(" You enjoy going to social events that involve dressup or roleplay activities."); mind.add(" It does not take much time to start getting involved in social activities at your new workplace."); mind.add(" You are a relatively reserved and quiet person."); return mind; } public int getMindSize() { return (mind.size()); }

Pause Media Player in case of phone call or user open a video or an audio in another program
I want to pause media player in case the user use another program to watch video or the user receive a phone call like any multimedia app (YouTube ,...)
MediaPlayer mediaPlayer = MediaPlayer.create(this, R.raw.song); mediaPlayer.start();
thanks

How do convert a number into int[] array format?
This for java. I have a number
int a = 254; and I want to convert into int b[] = {2,5,4};Pls advise

Efficient algorithm for grouping variablelength tuples
I am trying to devise an efficient algorithm for grouping a sequence of tuples of integers of any length, such as:
[(), (1,), (1,1), (1,2), (2,), (2,1,1), (2,1,2), (2,2)]
The grouping rule, in Python for example, is the following:
def tupleSameGroup(tuple1, tuple2): sameGroup = True for index in range(min(len(tuple1), len(tuple2))): if tuple1[index] != tuple2[index]: sameGroup = False return sameGroup
In rough words, if one tuple is a "subset" of another matching from the beginning, they are the same group. An empty tuple is in the same group as any tuple.
Based on this rule, I want my algorithm to produce as output a list of all unique groups of tuples; so a list of list of tuples, where within the inner list the tuples are all in the same group, but between there is a pair that is not. For the above example, the desired output is:
[[(), (1,), (1,1)], [(), (1,), (1,2)], [(), (2,), (2,1,1)], [(), (2,), (2,1,2)], [(), (2,), (2,2)]]
Any help would be much appreciated! Thank you.

Algorithm question: finding next non overlapping interval
Lets say we have a list of interval sorted by start point in ascending order. we want an algorithm to find for each interval, the next nonoverlapping interval with smallest start point.
For example we have list of interval as {(1,5), (2,4), (4, 6),(6, 10)}, for 0th interval (1, 5), the nearest nonoverlapping interval is 3rd interval which is (6, 10), for 1st (2,4) it should be 2nd (4,6). Therefore the desired output is [3, 2, 3, 1].
I can come up with an brute force O(N^2) algorithm which is to do linear scan for each interval. But I think there might exist an O(N) algorithm, anyone know the is there a better solution for this problem?

Datastructure to store database record
I want to store employees record. I don't want to use any external libraries or framework. I am trying to build the data structure from scratch.
There will be three fields,
EmployeeName Age Salary
We also want to query like,
Get all the salary where EmployeeName = "Bill" Get all the EmployeeName where salary > 2000 Get all the Salary where age='50'
I am open to use any language but not any builtin package. What is the recommended datastructure to achieve it ?

List permutations with variable length and alternate list content
I'm trying to list all permutations of variables, where each variable has 2 alternatives which can not be in the same permutation.
Let's say we have 2 variables A and B but I need to use them with an Index as A1, A2 and B1, B2. To make it even more complicated, the "1" index can occur alone and is not allowed with another "1", the "2" index can not occur alone. So what I need would be:
 A1
 B1
 A1 B2
 B1 A2
Using 3 variables A1, A2, B1, B2, C1, C2:
 A1
 A1 B2
 A1 C2
 A1 B2 C2
 B1
 B1 A2
 B1 C2
 B1 A2 C2
 C1
 C1 A2
 C1 B2
 C1 A2 B2
And I would need it for n variables (n1, n2). I found this one, but it didn't really help me:permutations variable length, but it doesn't quite fit. Actually I don't have a clue at all at the moment how to handle this.

Javascript create an array with unique combination of values
Despite reading a lot of Q/A about permutation/combination: Finding All Combinations of JavaScript array values + JavaScript  Generating combinations from n arrays with m elements I have not found the right way to get the kind of result I'm looking for. I got a 10 values array:
var arr = [0,1,2,3,4,5,6,7,8,9];
If I'm right, the number of all possible permuted arrays of unique values (no duplicates):
[5,9,1,8,2,6,7,0,4,3] [4,8,0,2,1,9,7,3,6,5] ...
is 2x3x4x5x6x7x8x9x10 = 3628800
I'm trying to produce a function to dynamically create the 'n' array. For example:
function createArray(0) > [0,1,2,3,4,5,6,7,8,9] function createArray(45648) > [0,1,5,3,2,8,7,9,6] (something like...) function createArray(3628800) > [9,8,7,6,5,4,3,2,1,0]
The way I'm figuring to achieve it is:
createArray(1) permutes the 2 last signs (8,9 > 9,8)
createArray(2>6) permutes the 3 last signs (8,7,9 > 9,8,7)
createArray(3628800) : all values are permuted (9>0)
Do you think it's possible/easy to do, and if yes how to proceed ?
[EDIT]
Thanks for helpfull answers
function permute(permutation, val) { var length = permutation.length, result = [permutation.slice()], c = new Array(length).fill(0), i = 1, k, p, n = 0; while (i < length) { if (c[i] < i) { if (n <= val) { k = i % 2 && c[i]; p = permutation[i]; permutation[i] = permutation[k]; permutation[k] = p; ++c[i]; i = 1; if (n == val) { arr = permutation.slice(); console.log("n="+n+"\n"+arr); console.log( 'Duration: '+((new Date()  t1)/1000)+'s' ); break; } else { n+=1; } } } else { c[i] = 0; ++i; } } } let t1 = new Date(); permute([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 100000); // < array requested
console : n=100000 + 0,5,8,1,7,2,3,6,4,9 + Duration: 0.004s

Python: Combination using dataframe criteria
I have an excel file with 4 rows and 5 columns with column labels as 1,2,3,4,5
1 2 3 4 5 Row 1 12 10 7 6 12 Row 2 24 22 9 18 8 Row 3 26 10 10 5 8 Row 4 24 5 17 1 0
I wish to generate a combination (a,b,c) consisting of column labels such that:
(row a, col a)  (row a, col b) == (row b, col a )  (row b, col b) 12  10 = 24 22
AND
(a,b,c) is such that b > a and c > b and c < 5
Expected Output:
(1,2,3) and (1,2,4)
import numpy as np import pandas as pd df = pd.read_excel('table.xlsx', sheetname='Sheet1') df.index = list(range(1, df.shape[1] + 1)) df.columns = list(range(1, df.shape[1] + 1)) combo = [(a,b,c) for a in df.columns for b in df.columns for c in df.columns if b > a and c > b and c > a and c < 5 and df.loc[a,a]  df.loc[a,b] == df.loc[b,a]  df.loc[b,b]]
I am getting the following error:
ValueError: Length mismatch: Expected axis has 3 elements, new values have 5 elements

Confused about Memoization performance  SICP exercise 3.27
From SICP
Exercise 3.27: Memoization (also called tabulation) is a technique that enables a procedure to record, in a local table, values that have previously been computed. This technique can make a vast difference in the performance of a program. A memoized procedure maintains a table in which values of previous calls are stored using as keys the arguments that produced the values. When the memoized procedure is asked to compute a value, it first checks the table to see if the value is already there and, if so, just returns that value. Otherwise, it computes the new value in the ordinary way and stores this in the table. As an example of memoization, recall from 1.2.2 the exponential process for computing Fibonacci numbers:
(define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib ( n 1)) (fib ( n 2))))))
The memoized version of the same procedure is
(define memofib (memoize (lambda (n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (memofib ( n 1)) (memofib ( n 2))))))))
where the memoizer is defined as
(define (memoize f) (let ((table (maketable))) (lambda (x) (let ((previouslycomputedresult (lookup x table))) (or previouslycomputedresult (let ((result (f x))) (insert! x result table) result))))))
...
Explain why memofib computes the nth Fibonacci number in a number of steps proportional to N.
The insert! and lookup procedures are defined in the book as follows:
(define (lookup key table) (let ((record (assoc key (cdr table)))) (if record (cdr record) false))) (define (assoc key records) (cond ((null? records) false) ((equal? key (caar records)) (car records)) (else (assoc key (cdr records))))) (define (insert! key value table) (let ((record (assoc key (cdr table)))) (if record (setcdr! record value) (setcdr! table (cons (cons key value) (cdr table))))) 'ok)
Now, assoc has number of steps proportional to n. And since lookup and insert! uses assoc, they both have number of steps proportional to N.
I do not understand how memofib has a number of steps proportional to N. My observations are:
 Due to the definition of the argument to memofib (the lambda which has n as the formal parameter), the table would have mostly ordered keys, And the keys would be looked up in an ordered way. So it is safe to assume any call to lookup would be close to a constant time operation.
 Insert! on the other hand will not be aware that the keys would be added in some order. If a value does not exist in the table, insert! will always scan the whole list, so it would have number of steps proportional to n every time.
 If we have n1 elements in the table and we wish to compute (memofib n), it would have number of steps proportional to n due to insert!
 If we have no keys, then (memofib n) would have number of steps proportional to n^2 due to insert! being called every recursive call to memofib.
If lookup and insert! are constant then it would make sense for memofib to have number of steps proportional to n. But the real number of steps looks like n*(nk) where k are number of keys already in the table.
Am I doing it wrong? What am I missing?

Dynamic programming applied on a recursive algorithm
so bellow is my code for an algorithm using recursive calls. I will not explain what the algorithms exactly does, because i do not think that it is important to know for this question. It basically just calculates the amount of valid paths for a given input n. The algorithm has exponential complexity, so it is really slow for bigger n.
With the current algorithm i am only able to calculate n up to 10 in realistic time, but other people working on the same problem told me that it is possible to get up to 200 with the same recursive approach i took by adding in dynamic programming. So i read into dynamic programming a bit and i think i understood what it is supposed to do. It memorizes previous calculations so you do not have to calculate them again, instead you can just take them out of a list or so.
But i do not understand how i am able to apply that for my code, could anyone help me out or atleast give me a hint?
public class CalculatePaths { static private int n; static private int remainingSteps; // calculates how many steps are left static private int paths = 0; // calculates how many valid paths there are public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.println("Enter a value for n: "); n = scanner.nextInt(); remainingSteps = 2 * n; move(0, 0, 0, 0, remainingSteps); System.out.println("There are " + paths + " valid paths for n = " + n); } /** * Goes through all paths and calculates the amount of valid paths * Stops if x or y or negative * Stops when all steps were used * A valid path has to meet the following conditions: * 1. There arent any remaning steps left * 2. The xcoordinate has to be 0 * 3. The ycoordinate has to be equal to n */ public static void move(int xDirection, int yDirection, int parentx, int parenty, int remainingSteps) { // calculates the current coorindates with the parent coordinates and the direction coordinates parentx = parentx + xDirection; parenty = parenty + yDirection; if (parentx == 0 && parenty == n && remainingSteps == 0) { paths++; } // recursive call as long as the coordinates arent negative and there are still remaining steps if (remainingSteps > 0 && parentx >= 0 && parenty >= 0) { move(1, 0, parentx, parenty, remainingSteps  1); // goes to the right... move(0, 1, parentx, parenty, remainingSteps  1); // goes up... move(0, 1, parentx, parenty, remainingSteps  1); // goes down... move(1, 1, parentx, parenty, remainingSteps  1); // diagonal top left... } } }

Porting an example from QuantEcon.jl to POMDPs.jl
I asked this in the Julia discourse website but got no response. I'm asking over here to see if I have better luck.
Just for fun (and to learn about POMDP) I am porting an example of dynamic programming from QuantEcon.jl to POMDPs.jl. The example is available here.
My code for the implementation is:
using POMDPs using POMDPModels using POMDPModelTools using DiscreteValueIteration struct SimpleOG{TI <: Integer, T <: Real, TR <: AbstractArray{T}, TQ <: AbstractArray{T}} <: MDP{T, T} B :: TI M :: TI α :: T β :: T R :: TR Q :: TQ end function SimpleOG(; B::Integer = 10, M::Integer = 5, α::T = 0.5, β::T = 0.90) where {T <: Real} u(c) = c^α # utility function n = B + M + 1 m = M + 1 R = Matrix{T}(undef, n, m) Q = zeros(Float64, n, m, n) for a in 0:M Q[:, a + 1, (a:(a + B)) .+ 1] .= 1 / (B + 1) for s in 0:(B + M) R[s + 1, a + 1] = a <= s ? u(s  a) : Inf end end return SimpleOG(B, M, α, β, R, Q) end POMDPs.states(simpleog::SimpleOG) = collect(0:(simpleog.M + simpleog.B)) POMDPs.n_states(simpleog::SimpleOG) = simpleog.B + simpleog.M + 1 POMDPs.stateindex(simpleog::SimpleOG, s) = Int(s) + 1 POMDPs.actions(simpleog::SimpleOG) = collect(0:simpleog.M) POMDPs.n_actions(simpleog::SimpleOG) = simpleog.M + 1 POMDPs.actionindex(simpleog::SimpleOG, a) = Int(a) + 1 POMDPs.transition(simpleog::SimpleOG, s, a) = simpleog.Q[Int(a) + 1, Int(s) + 1, :] POMDPs.reward(simpleog::SimpleOG, s, a) = simpleog.R[Int(s), Int(a)] POMDPs.reward(simpleog::SimpleOG, s, a, sp) = reward(simpleog, s, a) POMDPs.discount(simpleog::SimpleOG) = simpleog.β g = SimpleOG()
When I try to solve the model I get:
julia> POMDPs.solve(g) MethodError: no method matching solve(::SimpleOG{Int64,Float64,Array{Float64,2},Array{Float64,3}}) Closest candidates are: solve(!Matched::POMDPPolicies.FunctionSolver, !Matched::Union{MDP, POMDP}) at /Users/amrods/.julia/packages/POMDPPolicies/oW6ud/src/function.jl:23 solve(!Matched::POMDPPolicies.RandomSolver, !Matched::Union{MDP, POMDP}) at /Users/amrods/.julia/packages/POMDPPolicies/oW6ud/src/random.jl:36 solve(!Matched::POMDPPolicies.VectorSolver{A}, !Matched::MDP{S,A}) where {S, A} at /Users/amrods/.julia/packages/POMDPPolicies/oW6ud/src/vector.jl:23 ... Stacktrace: [1] toplevel scope at In[14]:1
Can you help me figure out what is going on?

Dividing Weights Equally in Javascript (bin sorting/knapsack sort of problem)
I have 100 bins, and a random number of boxes (which each have weight and volume). I need to distribute the boxes as equally as possible into the bins, and no bin can have more than 100 volume. While the number of boxes is random each turn, I know the amount of boxes (
boxCount
), and the weight and volume of each box in an array.Because weight needs to be distributed equally, I'm taking total weight of all boxes, and dividing it by 100 to get the average amount that needs to be in each bin. Below I'm simply trying to iterate over each box and assign it to a bin if the current bin is less than the average and volume is less than 100. But the bin stays at zero, it's not increasing. Is something wrong in the if statement?
Also, any pointers on how this can be optimized so that every bin has the closest possible amount to the average would be much appreciated, as the current method might be pretty far off if the next box has a lot of weight or volume.
let bin = 0; for (let i = 0; i < boxCount; i++) { w = 0; vol = 0; if (((w + allBoxes[i].weight) <= (average)) && ((vol + allBoxes[i].volume)) < 100) { w = w + allBoxes[i].weight; vol = vol + allBoxes[i].volume; allBoxes[i].bin = bin; } else { bin = ++bin; } }

Knapsack dynamic in R
I am trying to implement the sudo code from wikepedia in order to solve the knapsack problem but my code fails. My function takes as input a data frame X with 2 columns,the first was the weights and second the values
weights value 10 110 20 150 15 180 30 170 18 130 knapsnack_dyn<function(X,W){ w<c(0,X[,1]) v<c(0,X[,2]) n<nrow(X) m< matrix(0,nrow=n+1,ncol=W+1) keep<m res<c() for (i in 1:n+1){ for (j in 0:W+1){ if (w[i]>j ){ m[i,j]<m[i1,j] keep[i,j]<0 }else{ m[i,j]<max(m[i1, j], m[i1, jw[i]] + v[i]) keep[i,j]<1 } } } K=W+1 for (i in n+1:1){ if(keep[i,K]==1){ res[i]<i K=Kw[i] } } return(c(res,m[n+1,W+1])) }

How to implement knapsack problem with recursion in java
So if you arent aware of what the knapsack problem is, it is a way of fitting different weights from a knapsack so that they add up to equal a specified total weight. Here is an example from my book on how to go about solving the problem if the specified total weight was 20.
If anybody knows how to implement this problem in java using recursion PLEASE help, im so confused. Here is what I started but I'm pretty sure this is wrong and I have no clue where to go now.
import java.util.*; public class n01044854 { public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.println("Please first enter a weight capacity up to a value of 100, followed by a series of individual weight values with 25 weights being the max.) "); String values = input.nextLine(); String[] tokens = values.split(" +"); int capacity = Integer.parseInt(tokens[0]); int[] weightValues = new int[tokens.length  1]; for (int i = 0; i < tokens.length  1; i++) weightValues[i] = Integer.parseInt(tokens[i+1]); optimizeWeights(capacity, weightValues, 0); } public static void optimizeWeights(int target, int[] weights, int currentIndex) { if (weights[currentIndex] == target) System.out.println("Success! Knapsack optimally filled."); else if (weights[currentIndex] < target) { int newTarget = target  weights[currentIndex]; optimizeWeights(newTarget, weights, currentIndex + 1); } else if (weights[currentIndex] > target) { if (currentIndex < weights.length  1) optimizeWeights(target, weights, currentIndex + 1); else //confused on what to do } } }