largestPartialIntersectionWeighted

Similar to largestPartialIntersection, but associates a weight with each distinct element in the intersection.

If at least one of the ranges is a multiset, then all occurences of a duplicate element are taken into account. The result is equivalent to merging all input ranges and picking the highest tgt.length, weight-based ranking elements.

void
largestPartialIntersectionWeighted
(
alias less = "a < b"
RangeOfRanges
Range
WeightsAA
)
(
RangeOfRanges ror
,
Range tgt
,
WeightsAA weights
,)

Parameters

less

The predicate the ranges are sorted by.

ror RangeOfRanges

A range of forward ranges sorted by less.

tgt Range

The target range to copy common elements to.

weights WeightsAA

An associative array mapping elements to weights.

sorted SortOutput

Whether the elements copied should be in sorted order.

Examples

1  import std.typecons : tuple, Tuple;
2 
3  // Figure which number can be found in most arrays of the set of
4  // arrays below, with specific per-element weights
5  double[][] a =
6  [
7      [ 1, 4, 7, 8 ],
8      [ 1, 7 ],
9      [ 1, 7, 8],
10      [ 4 ],
11      [ 7 ],
12  ];
13  auto b = new Tuple!(double, uint)[1];
14  double[double] weights = [ 1:1.2, 4:2.3, 7:1.1, 8:1.1 ];
15  largestPartialIntersectionWeighted(a, b, weights);
16  // First member is the item, second is the occurrence count
17  assert(b[0] == tuple(4.0, 2u));
18  // 4.0 occurs 2 times -> 4.6 (2 * 2.3)
19  // 7.0 occurs 3 times -> 4.4 (3 * 1.1)
20 
21 // multiset
22  double[][] x =
23  [
24      [ 1, 1, 1, 4, 7, 8 ],
25      [ 1, 7 ],
26      [ 1, 7, 8],
27      [ 4 ],
28      [ 7 ],
29  ];
30  auto y = new Tuple!(double, uint)[1];
31  largestPartialIntersectionWeighted(x, y, weights);
32  assert(y[0] == tuple(1.0, 5u));
33  // 1.0 occurs 5 times -> 1.2 * 5 = 6

Meta

Suggestion Box / Bug Report