Algorithm: combinations of (k) taken from (n) values
Darrell
darrell at dorb.com
Sun Apr 9 01:16:13 EDT 2000
Pasted the Charles algorithm into a class using a coroutine to provide
iterators.
The idea being to make the algorithm lazy.
Is it possible to figure out a combination at some huge offset without
figuring out all previous combinations? Seems like it might be, in which
case the isn't much use.
import coroutine
class Choices:
def __init__(self,n,k=None) :
"""
Prepares to return elements from a list consisting of all k-element
(ordered)
subsets of {0 ... n-1}.
"""
self._combinations=[]
self._skip=1
def combs(n=n,k=k, self=self):
"""returns sorted list of k items taken from n."""
l=self._combinations
if k==None:
k=n
for c in range(n):
l.append([c])
for i in range(k-1):
li = []
for c in l:
for j in range(c[-1]+1,n):
li.append(c+[j])
// Bet Christian can show me a better way to do
this.
if self._skip==0:
self._combinations=li
coroutine.resume_caller (li[-1])
self._skip=self._skip-1
l = li
return l
self._coroutine=coroutine.coroutine(combs)
def next(self):
self._skip=1
return self._coroutine.resume()
def __getitem__(self, i):
if i < len(self._combinations):
return self._combinations[i]
cnt=i-len(self._combinations)+1
self._skip=cnt
self._coroutine.resume()
return self._combinations[i]
def __getslice__(self, i, j):
self[j]
return self._combinations[i:j]
choices=Choices(30,2)
for x in range(3):
print choices.next()
print 'getitem:',choices[7]
print 'getslice:', choices[40:50]
More information about the Python-list
mailing list