Is there a direct way of getting the Nth combination of an ordered set of all combinations of nCr?
Example: I have four elements: [6, 4, 2, 1]. All the possible combinations by taking three at a time would be: [[6, 4, 2], [6, 4, 1], [6, 2, 1], [4, 2, 1]].
Is there an algorithm that would give me e.g. the 3rd answer, [6, 2, 1], in the ordered result set, without enumerating all the previous answers?
From the Python 3.6 itertools recipes:
def nth_combination(iterable, r, index):
'Equivalent to list(combinations(iterable, r))[index]'
pool = tuple(iterable)
n = len(pool)
if r < 0 or r > n:
raise ValueError
c = 1
k = min(r, n-r)
for i in range(1, k+1):
c = c * (n - k + i) // i
if index < 0:
index += c
if index < 0 or index >= c:
raise IndexError
result = []
while r:
c, n, r = c*r//n, n-1, r-1
while index >= c:
index -= c
c, n = c*(n-r)//n, n-1
result.append(pool[-1-n])
return tuple(result)
In practice:
iterable, r, index = [6, 4, 2, 1], 3, 2
nth_combination(iterable, r, index)
# (6, 2, 1)
Alternatively, as mentioned in the docstring:
import itertools as it
list(it.combinations(iterable, r))[index]
# (6, 2, 1)
See also more_itertools - a third party library that implements this recipe for you. Install via:
> pip install more_itertools
Yes there a direct way of getting the Nth combination of an ordered set of all combinations of nCr? Say you need to generate 0th, 3rd, 6th.. combinations of a given set. You can generate it directly without generating combinations in between using JNuberTools. You can even generate next billionth combination (if your set size is large) Here is the code example:
JNumberTools.combinationsOf(list)
.uniqueNth(8,1000_000_000) //skip to billionth combination of size 8
.forEach(System.out::println);
The maven dependency for JNumberTools is :
<dependency>
<groupId>io.github.deepeshpatel</groupId>
<artifactId>jnumbertools</artifactId>
<version>1.0.0</version>
</dependency>