-2
$\begingroup$

(I hope this is on-topic for this site -- mods feel free to send this to another stack exchange if not )

I've got an optimization problem where I need to choose from one of several options to maximize a quantity.

Each of those options is an array of numbers of arbitrary length, and each of the elements is strictly non-increasing (either decreasing or not changing), moving from left to right.

Here is an example, stacking them row-wise:

87643
99732
76534
87651
64311

I can only choose the leftmost in the stack, and after I choose it, it's gone. The naive way to do this would be to look for the maximum from the first column, take it, then redefine the problem with the removed element out and then continue.

So:

        87643
        9732
        76534
        87651
        64311
        val = 9
out = (2[1])

        87643
        732
        76534
        87651
        64311
        val = 18
out = (2[2])

        7643
        732
        76534
        87651
        64311
        val = 26
out = (2[2], 1[1])

and so on

This is sort of slow given the size of my array, and how it's likely to scale. Are there any better alternatives?

Edit:

No idea why the downvotes but anyway I figured out that I can just concatenate a vector of indices (1 through N) to each array, concatenate the 2d arrays, then sort by the value. I select elements until the cumulative sum matches what I want.

$\endgroup$
  • $\begingroup$ Probably a better fit at cs.stackexchange or stackoverflow...Did you try having a priority queue, push the first element of each list (along with the index of which list it's in and where in that list), then repeatedly pop the front of the queue, take it, add the next item in its list to the queue. $\endgroup$ – usul Aug 27 '19 at 10:47
1
$\begingroup$

One thing you could try:

  1. Take the first value in each input array, and the number of the input array.
  2. Sort the array from (1.) based on value.
  3. Your desired output is the input array number from the first element in the sorted array.
  4. Remove the first element from the sorted array, and note its array number.
  5. Add the next value from the noted array number into the sorted array, unless that array number now refers to an empty array.
  6. Repeat (3.), (4.), (5.) until all array numbers/indices refer to empty arrays.

Example:

Input source arrays:

87643 = input array number 1
99732 = input array number 2
76534 = input array number 3
87651 = input array number 4
64311 = input array number 5

1. Generate a 1-time input array:

[(8,1),(9,2),(7,3),(8,4),(6,5)]

Update the starting index for the source arrays (don't update the array content, just keep track of the value you're on for each array):

7643
9732
6534
7651
4311

2. Sort the input array:

[(9,2),(8,1),(8,4),(7,3),(6,5)]

3. The first element contains your output:

out = (2[1])

4. remove the first element:

[(8,1),(8,4),(7,3),(6,5)]

first element was from array number 2

5. add/sort the next single value from the previously removed output index, unless that index is now empty:

7643
9732 = input array number 2
6534
7651
4311

[(9,2),(8,1),(8,4),(7,3),(6,5)]

This would only read/sort the first elements in each index once at the beginning. Then, you're just reading/sorting a single value with each successive iteration, which should be fast.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.