StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POGenerating non-consecutive combinations
text
Body
copied!<p>I am trying to create a generator (iterator which supports doing a next, perhaps using yield in python) which gives all combinations of r elements from {1,2,...n} (n and r are parameters) such that in the selected r elements, no two are consecutive.</p> <p>For example, for r = 2 and n= 4</p> <p>The generated combinations are <code>{1,3}, {1,4}, {2, 4}</code>.</p> <p>I could generate all combinations(as an iterator) and filter those which don't satisfy the criteria, but we will be doing unnecessary work.</p> <p>Is there some generation algorithm such that the <code>next</code> is O(1) (and if that is not possible, O(r) or O(n)).</p> <p>The order in which the sets are returned is not relevant (and hopefully will allow an O(1) algorithm).</p> <p>Note: I have tagged it python, but a language-agnostic algorithm will help too.</p> <p><strong>Update:</strong></p> <p>I have found a way to map it to generating pure combinations! A web search reveals that O(1) is possible for combinations (though it seems complicated).</p> <p>Here is the mapping.</p> <p>Suppose we have a combination <code>x_1, x_2, ... , x_r</code> with <code>x_1 + 1 < x_2, x_2 + 1 < x_3, ...</code></p> <p>We map to <code>y_1, y_2, ..., y_r</code> as follows</p> <pre><code>y_1 = x_1 y_2 = x_2 - 1 y_3 = x_3 - 2 ... y_r = x_r - (r-1) </code></pre> <p>This way we have that <code>y_1 < y_2 < y_3 ...</code> without the non-consecutive constraint!</p> <p>This basically amounts to choosing r elements out of n-r+1. Thus all I need to do is run the generation for (n-r+1 choose r).</p> <p>For our purposes, using the mapping after things are generated is good enough.</p> <p><strong>Reasons for choosing svkcr's answer</strong></p> <p>All great answers, but I have chosen svkcr's answer.</p> <p>Here are some reasons why</p> <ol> <li><p>It is effectively stateless (or "Markovian" to be more precise). The next permutation can be generated from the previous one. It is in a way almost optimal: O(r) space and time.</p></li> <li><p>It is predictable. We know exactly the order(lexicographic) in which the combinations are generated.</p></li> </ol> <p>These two properties make it easy to parallelise the generation (split at predictable points and delegate), with fault tolerance thrown in (can pick off from the last generated combination if a CPU/machine fails)!</p> <p>Sorry, parallelisation was not mentioned earlier, because it didn't occur to me when I wrote the question and I got that idea only later.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload