Opened 7 years ago

Closed 6 years ago

Last modified 2 years ago

#838 closed request (fixed)

copy k elements out of N

Reported by: Peter Owned by: Peter
Priority: major Milestone: yat 0.14
Component: random Version: trunk
Keywords: Cc:

Description

I need to do this for a bam file, but there is no reason to limit this to BamRead.

From a range [first, last), I want to pick (i.e. copy to another range) k elements. This can be done with something like this (untested):

  1. set N = distance(first, last)
  2. Loop over [first, last)
  3. copy first+i with probability p_i = (k-c_i) / (N-i), where c_i is how many elements we have copied from the previous elements: [first, first+i).

Change History (4)

comment:1 Changed 6 years ago by Peter

Owner: changed from Jari Häkkinen to Peter
Status: newassigned
Version: trunk

I suggest the following interface instead:

OutputIterator template<typename InputIterator, typename Size, typename OutputIterator>
copy_k_of_n(InputIterator, Size k, Size n, OutputIterator)

similar to std::copy_n in C++11.

comment:2 Changed 6 years ago by Peter

Component: utilityrandom

comment:3 Changed 6 years ago by Peter

Resolution: fixed
Status: assignedclosed

(In [3454]) closes #838

comment:4 Changed 2 years ago by Peter

In 3878:

New class BamPairIterator2 that takes a sort range of bam reads as
input and behaves as iterating through bam read pairs sorted with
respect to the second read. Also fixed an error in
test::Suite::trivial_iterator and apply that test on BamPairIterator?

closes #913
fixes #838

Note: See TracTickets for help on using tickets.