0
$\begingroup$

Suppose I have these values with weights -- $$ x_1 = 2\\ x_2 = 4\\ x_3 = 5\\ $$ There is no negative or $0$ value. I need to find $2$ element subset with maximum value computed from a function $f(\cdot,\cdot)$, lets say the function values are like this -- $$ f(x_1,x_2) = 10\\ f(x_2,x_3) = 12\\ f(x_3,x_1) = 14\\ $$ What I am doing is running $O(n^2)$ loop (trying all combinations) and keeping the best pair, i.e. $\{x_3, x_1\}$

Is there any faster way to do this ? because my dataset can get arbitrarily large (10,000) and instead of 2 elements, I may need to compute the same with k elements ($k < \text{number of data points}$)

Sorting: Unfortunately, sorting is not possible, actually the weights that I am getting is from a function, the function takes $k$ data point (any combination) at a time and returns a value, i.e. $w = f(x_i, x_j, \ldots, x_k)$ so I need to pick the $k$ subset with the best (or you can say highest) $w$ value.

please help.

$\endgroup$

closed as unclear what you're asking by D.W., jonaprieto, Rick Decker, David Richerby, Nicholas Mancuso Dec 5 '14 at 21:18

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Are all weights positive integers, or can you have negative integers as well? (I don't see why sorting isn't possible even if you get the value from a function, so what?) $\endgroup$ – Juho Dec 5 '14 at 12:39
  • $\begingroup$ why kind of function is $f(x_{1,\cdots,k})$ (?) If we don't provide the definition, I suggest that try with a bitmask to perform a brute force search. $\endgroup$ – jonaprieto Dec 5 '14 at 15:18
  • $\begingroup$ I'm afraid I can't understand your question. Just like Juho says, I can't understand why you can't sort. I don't understand why it matters how you got the values; get all the values, in whatever way you like, and then once you have them all, sort them. Also your notation is not very clear: you re-use $k$ for two different purposes, I don't know what $f(x_i,x_j,\dots,x_k)$ means, it's not clear whether you're telling us about the number of different $x$-values or the number of different $w$-values, and it's confusing in other ways. Can I encourage you to edit your question? $\endgroup$ – D.W. Dec 5 '14 at 17:46
  • 2
    $\begingroup$ If I understand your question correctly (and I very well might not), without any information about $f$ you cannot do better than $O(n^k)$, since there are $O(n^k)$ different ways to choose a subset of $k$ of the $n$ elements. But you haven't told us what $f$ is. If you tell us what $f$ is maybe we can find a better solution. So I encourage you to edit the question to specify what function $f$ you have. $\endgroup$ – D.W. Dec 5 '14 at 17:47
1
$\begingroup$

If I understand you correctly, the order of the inputs to function F does not influence the output W, so order is not important. I'm deducing this from the three possible subsets in your example at the top where K = 2 and N = 3.

For a set of N elements, and a function F taking K inputs where order of inputs does not matter, the complexity to find all possible W outputs I don't think is O(N ** K). I'm using ** as to the power of.

I would think it is the same problem as finding the number of ways to choose K elements from a set of N elements disregarding order. I think one could also say the number of partitions of K elements over a set of N elements.

The number of ways to choose K elements from a set of N elements is: N // since you are choosing from a set of N elements * (N - 1) // since next you are choosing from a set of N - 1 elements * (N - 2) // same reasoning as above ... * (N - (K - 1)) // just before you have chosen K elements * (N - K) // you have chosen the K-th element Sort of like factorial, but from N - K + 1 up to N, which is the same as N! / (N - K)!.

Lastly, we have to disregard order of the elements, and there is K! ways to order K elemetns, which brings us to: N! / (N - K)! / K! As each W is calculated you can simply keep the highest yealding inputs, and when you have tried all inputs you will be guaranteed to have found the right set of inputs.

So, supposing the above is correct (it worked for small mental verification of K = 2, N = 4 and K = 3, N = 4 and K = 3, N = 5) then I suppose the complexity analysis is O(N! / (N - K)! / K!) and not O(N ** K).

If you know F then you could optimise it, to get a linear improvement, or maybe find inputs that could be omitted to get an even bigger speedup.

Without knowing F you are stuck with trying everything.

One other thing you could do is employ memoization to avoid having to evaluate F for similar inputs.

$\endgroup$
0
$\begingroup$

If I understand correctly you can just sort the elements in time $O(n \log n)$ using say, mergesort, and pick the $k$ largest elements.

$\endgroup$
  • $\begingroup$ hi, question is edited, unfortunately sorting is not possible. $\endgroup$ – ramgorur Dec 5 '14 at 12:21

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