Just as a note of possible improvement, wouldn’t it be the case that a vertex only really belongs in possible-next-sums if all its downward neighbors have already gone into minimal-sums, rather than just one?
It may keep the size of possible-next-sums down, but it may take too much bookkeeping to be worth it. At any rate, it’s not like possible-next-sums is meant is supposed to be as small as possible, just as small as efficiently maintainable. So, I don’t know.
It wouldn’t be that much bookkeeping to do, though. One could use a trie to represent a map which takes in a vertex and outputs how many of its immediate predecessors have already been put into minimal-sums. The lookup time for any particular vertex would be Theta(N) and given any particular vertex’s node in the tree, its immediate successors could each be found in constant time.
So we could modify step 2. above to:
2. Update the trie for each successor of <v>=s. (This takes time Theta(N)). If any of them turn out to have had all N of their immediate predecessors already put into minimal-sums, then stick them into possible-next-sums. (This takes time O(N log |possible-next-sums|), and thus the time for step 2 as a whole remains O(N log MN)).
One could also possibly use a more efficient structure than the naive trie here. Perhaps a structure directly reflecting that of the hypercube. The lookup time for any vertex would then be Theta(K) where K is the Hamming distance of the vertex from the origin.
Yes (or at any rate “possible-next-sums” is a somewhat misleading name, in fine bad-programmer tradition).
I don’t see how to do this with what I think of as a trie; the upward neighbors of a vertex are not generally lexicographically near the vertex, so I’d think you’d need something more like your hypercube lattice idea:
It would take a more careful analysis than I’ve done to decide whether this sort of thing would help. I’d guess that it would be hard to make this efficient enough to improve on the only-logarithmic complexity of the possible-next-sums map, however.
For an example of my carelessness, this assumes that the operation of copying a <v>=s node is O(1). But if <v> is naively represented as a string or bit-vector, it’s O(N) in length and so copying it should take O(N) as well (for a total of O(N[sup]2[/sup] log MN) in step 2). <v> could instead be represented as a linked list (pointing to previous values in the minimal-sums list). Doing this wrong could cause a noticeable performance hit for large N.
Yeah, my discussion of the successors of a vertex being “near” that vertex itself in a trie was confused; I had somehow switched carelessly into thinking of a structure which mimicked the structure of the hypercube.
I should also note that if the values are not all positive, you can efficiently generate the minimal sums in the same way, by replacing all negative values with their absolute values and subtracting their sum from all overall values. (For example, for values {-5,-2,1,4,8}, you’d work instead with values {1,2,4,5,8} and subtract 7 from all sums. Presence of a “2” in the sum is interpreted as absence of a “-2”, etc.) Essentially you’ve rotated the poset hypercube to put a different vertex on the bottom; the negative values correspond to directions which were formerly upward and are now downward.
[QUOTE=Omphaloskeptic]
You want to generate sums upward from the bottom. Maintain two data structures: a list minimal-sums (which will become your desired output, and can just be a linked list) and a set possible-next-sums (which should be able to efficiently maintain a sorted state on random-access insertion and deletion). Begin with both of these structures empty. Start at the bottom vertex <0…0>=0.
Now repeat, M+1 times (the first time through just gives you 0; the next M times give you the lowest M sums):[ol][li]Append <v>=s to minimal-sums.[/li][li]Insert all upward neighbors of <v>=s into possible-next-sums (unless already present).[/li][li]Find a minimal sum <v>=s in possible-next-sums.[/li][li]Remove <v>=s from possible-next-sums.[/ol]You can end the final iteration after step 1 if you want.[/li]
The set possible-next-sums will usually get large, eventually. But since each vertex has only O(N) upward neighbors, in M steps it will only get to size O(MN). Efficient access, insertion, and deletion into such a set should be O(log MN). So each iteration should take[ol][li]O(1)[/li][li]O(N log MN)[/li][li]O(log MN)[/li][li]O(log MN)[/ol]and the overall algorithm should run in O(MN log MN).[/li][/QUOTE]
As I mentioned above, the problem reduces to looking at the sequence for x[k] where k = 1 to M, so, effectively, N = M, which means that your algorithm takes O(M^2 log(M^2))
I came up with a similar algorithm, but I think it is takes less time.
I have a list of ‘candidates’ (similar to your possible-next-sums) that are separated into two parts: a ‘node’ and an ‘x_idx’ (an index into the x[k] sequence.) Each candidate also contains a ‘value’ field, which is the value of the sum using the indexes in ‘node’ and ‘x_idx’.
For example, for a candidate 3-tuple, the ‘node’ might be [2 5] and the x_idx may be 7, which means that, if this 3-tuple is chosen, the next sum in the sequence is the 3-tuple [2 5 7] (i.e. x[2]+x[5]+x[7]), and this candidate’s x_idx is then incremented to 8.
Below is the code in Matlab
function [sorted_sums] = sort_sums(sorted_values, M)
% Add the first candidate
candidates(1).node = [];
candidates(1).x_idx = 1;
candidates(1).value = sorted_values(1);
for I=1:M,
[junk,min_idx] = min([candidates.value]);
node = candidates(min_idx).node;
x_idx = candidates(min_idx).x_idx;
value = candidates(min_idx).value;
% Update sorted_sums
sorted_sums(I).indexes = [node x_idx];
sorted_sums(I).value = value;
% Update candidates
% First, update the one currently chosen
candidates(min_idx).x_idx = x_idx + 1;
candidates(min_idx).value = value + ...
sorted_values(x_idx+1) - sorted_values(x_idx);
% Next, add a new candidate
candidates(I+1).node = sorted_sums(I).indexes;
candidates(I+1).x_idx = x_idx + 1;
candidates(I+1).value = value + sorted_values(candidates(I+1).x_idx);
end
We go through the code M times, and in each pass, we have to find the min of a sequence. I assume this can be done in O(length of sequence) time. Since one candidate is added to the sequence in each pass, that means that after M passes, the sequence will be length M, which means that finding the min should take O(M) time.
So, overall, this algorithm should take O(M^2)
Also, if we’re careful and the ‘candidates’ list is structured properly, maybe the min can be found in O(log(M)), which would make the overall time O(M log(M))
I think the primary difference between my algorithm and yours is that ‘candidates’ grows to size M, while ‘possible-next-sums’ grows to M^2
Using the example you gave of {2,3,5,7,15} and M = 6, we get the following output
Step 1:
Candidates: ([] -> 1)
sum = 2 (indexes = [1])
Step 2:
Candidates: ([] -> 2), ([1] -> 2)
sum = 3 (indexes = [2])
Step 3:
Candidates: ([] -> 3), ([1] -> 2), ([2] -> 3)
sum = 5 (indexes = [3])
Step 4:
Candidates: ([] -> 4), ([1] -> 2), ([2] -> 3), ([3] -> 4)
sum = 5 (indexes = [1 2])
Step 5:
Candidates: ([] -> 4), ([1] -> 3), ([2] -> 3), ([3] -> 4), ([1 2] -> 3)
sum = 7 (indexes = [4])
Step 6:
Candidates: ([] -> 5), ([1] -> 3), ([2] -> 3), ([3] -> 4), ([1 2] -> 3), ([4] -> 5)
sum = 7 (indexes = [1 3])
Yes, I agree; your algorithm takes more care than mine in figuring out which sums are possible for the next smallest and so is more efficient.
Discussing the two algorithms in terms of the 0-1 vectors (the coefficients on the x[k] in each sum), my algorithm used the simple (but wasteful, as Indistinguishable pointed out) idea that any vector with at least one 1 represents a larger sum than the vector with a 1 replaced by a 0 (i.e., with that term omitted). So by making all single-bit 0->1 replacements the algorithm certainly gets to all possible sums. However, there are multiple paths to get to all vectors with more than one 1, so these sums are considered before they are really possible.
Your algorithm uses a rather nice recursive form for generating all strings, which does not have this multiple-path problem. The idea is that the sums represented by the two vectors v010…0 and v110…0 are both larger than the sum represented by vector v100…0 (where v is an arbitrary bit vector, and the values increase left-to-right). So when you pull a vector v100…0 off the list, you replace it with the two vectors v010…0 and v110…0, both of which are guaranteed to be larger and hence not yet missed. It’s not hard to see that this generates all bit strings exactly once, so it won’t miss any sums. (Of course, the sum v010…0 is necessarily smaller than the sum v110…0, so this procedure still adds some cases which are not possible next values, but it’s a pretty nice simple procedure for reducing the size of the list.)
To be a little pedantic, for this problem the strings should all have finite length N, so the ending cases should also be considered. Your Matlab code doesn’t check to see whether x_idx > N; in this case it should just not add these cases to the candidate list.