3
$\begingroup$

Let $S$ be a set of $n$ integers. Consider the following weighted permutations problem.

Let $m<n$ be an integer. What is an efficient algorithm to enumerate all subsets of $m$ integers of $S$ such that they are listed in order of the sum of the integers in each subset?

Each subset is a permutation, and each permutation has a total weight that is the sum of the integers in the permutation.

The idea is to come up with an algorithm that is not the trivial algorithm of enumerating all subsets, and then sorting them, i.e. more of a "streaming" type algorithm. That is, efficiency in terms not so much of time but of "small" space.

Maybe this is published somewhere in the literature although I have not seen it.

$\endgroup$
1
  • $\begingroup$ For $m=1$, you can repeatedly find the $k$th largest element of your set, where $k$ is decreasing. This should take quadratic time and constant space. This will maybe generalize for other fixed values $m$ too. $\endgroup$
    – Juho
    Nov 5 '13 at 18:46
2
$\begingroup$

Seems like a straightforward recursive algorithm, combined with streams (also known as lazy lists or generators), should work. i.e.,

def subsets(m, S):
  if m==0:
      return [{}]
  if S is empty:
      return []
  s = min(S)
  S' = S \ {s}
  T = subsets(m, S')
  U = [u.union(s) for u in subsets(m-1, S')]
  return merge(T, U)

With the obvious definitions and Python-ish notation. This returns a list in the desired order, i.e., a list of subsets, sorted by the sum of the elements in each subset. Here I haven't provided the merge routine, but it can be implemented using the standard algorithm for merging sorted lists.

For clarity of exposition, I've written the above using lists and list comprehensions. However, for an actual implementation, you should use streams (e.g., Python generators and generator comprehensions) rather than lists. If you do that, there's no need to build all of the lists and represent them in memory; the algorithm shown above can proceed in a streaming fashion.

This is the kind of problem where a language with explicit support for lazy evaluation will shine. With lazy evaluation, I believe you can implement a beautiful, elegant solution that looks clean but has excellent memory complexity.

$\endgroup$
1
  • $\begingroup$ on the right track but it seems sketchy, cant quite follow, not sure it would work. hint: what would be the output of your algorithm denoting sorted input integers as strings with with binary flags in each position. also, extra credit, does this appear in literature anywhere. $\endgroup$
    – vzn
    Nov 5 '13 at 19:22
0
$\begingroup$

You have $\frac {n!}{(n-m)!m!}$ options for different subsets. And therefore the minimum efficiency of such algorithm is exponential.

$\endgroup$
1
  • 1
    $\begingroup$ There is no problem with that. We want a mechanism $M$ (which you can think of as an object in the sense of OOP) which has a function "next" that outputs the next subset, in increasing order of total weight. We want "next" to be as fast as possible (either in the "worst" case, that is for each call, or on average, that is amortized), and $M$ to use as little memory as possible. $M$ can also presumably take some (reasonable amount of) time to initialize. $\endgroup$ Nov 7 '13 at 4:57

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.