2

Given a list of m items, I am looking for a way to repeatedly pick a tuple of n distinct items from this list with low discrepancy.

For example, suppose I have a list of 3d points, and I want to perform some ransac fit, so I need to pseudo-randlomly pick n points for the fit, until I found a fit that is good enough.

The obvious way to pick n items from a list is to just generate n distinct pseudo-random numbers between 0 and m. But if you do this repeatedly, there is a high chance of repeatedly selecting the same item or the same combination of items before trying out all other combinations.

Is there an algorithm that, when picking a tuple of n points, can assure that

  • each tuple contains each point only once
  • no point is selected twice before all other points have been used once. (So if a selected tuple contained point A, no other tuple may contain A until all other points have been chosen for a tuple)
  • no pair of points is selected twice before all other pairs have been used once. (So if a selected tuple contained points A and B, no other tuple may contain this pair until all other pairs have been chosen for a tuple)
  • no triple of points is selected twice before all other triples have been used once
  • ...
  • no n-1 combination is selected twice before all other n-1 selections have been used once
  • no n-tuple is selected twice before all other tuples have been used once

(These are not absolute requirements, I would be happy with a selection method that makes it merely unlikely instead of impossible, that point A will be picked again before all other points)

I am looking for a way to generate such a permutation of tuples without saving a list of all tuples that have been tried before, since the size of this list and the time to search trough it would become prohibitive for larger sizes.

An example:

Given a list containing $[ I_1, I_2, I_3, I_4, I_5, I_6, I_7, I_8, I_9 ]$, and selecting tuples of size 3 from this list:

  • First I pick $[I_1, I_2, I_3]$
  • (Order does not matter. This tuple is for my purposes equivalent to $[I_3, I_2, I_1]$ or $[I_3, I_1, I_2]$, ...)
  • The next tuples I pick should contain neither $I_1$ nor $I_2$ nor $I_3$, until all other items have been selected once
  • Even after all other items have been picked once, the subsequent tuples should also contain neither ${I_1 , I_2}$ nor ${I_1 , I_3}$ nor ${I_2 , I_3}$, until all other combinations of 2 items have been used once.

I am not quite sure whether the term "low discrepancy" is correct here, I am basing this on the usage in low discrepancy sequences, which allow me to repeatedly select a single point from a list, without picking the same point twice, and with low probability to pick points from the same subset in a row. I am looking for something similar for tuples.

mdewey
  • 17,806
HugoRune
  • 141
  • Just to make sure I understand, let me try and paraphrase. You want to draw a tuple $x_n=(a_i){i=1}^n \in X_n \subseteq \mathbb R^n$ such that every length-$k$ contiguous subtuple $x_k$ has not yet been drawn from $X_k$. Thereby the sequence not only needs to be low-discrepancy, but every "slice" of every element of every sequence _also needs to be low-discrepancy with respect to its corresponding "slice" of the population. – shadowtalker Jun 25 '16 at 14:11
  • If so, I think you're way overthinking this. It seems to me that you should be able to directly draw multivariate low-discrepancy samples. See here and here, for instance. – shadowtalker Jun 25 '16 at 14:12
  • Unfortunately I do not quite understand your reformulation, but I agree that I may be overthinking it for sure :) But to me it seems that the links you pointed out only allow me to pick a vector from $\mathbb R^n$, e.g. with a Halton sequence. I have a discrete list of measurements, (which happen to be points in $\mathbb R^3$, but that is incidental), and want to pick tuples only from this list. It is fairly straightforward to use one of the 1d sequences to draw individual entries with low discrepancy from a finite list, but I do not know how to extend this to tuples that fit my criteria – HugoRune Jun 25 '16 at 15:20
  • It looks like that issue has come up before. This isn't something I know much about, but as I start poking around it looks like the question you're asking doesn't have a definitive answer in the literature. – shadowtalker Jun 25 '16 at 15:27

0 Answers0