Enumerating weighted permutations in sorted order problem

Question

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.

Answer 1

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.

Answer 2

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