[David Mertz <me...@gnosis.cx>] > Here's a discussion of both a conceptually simple and a convoluted but > fast version (the latter, naturally, by Tim Peters).
Not really convoluted - it's the natural thing you'd do "by hand" to move from one partition to the next: look at the current partition, throw out the 1s, also throw out an instance of the smallest component `i` of what remains, then break the sum of what was thrown away into a (sub)partition "greedily" with largest component i-1 and the rest (if any) 1s. Although, no, that may not be obvious at first ;-) The point of the recipe is really to show all that can - with appropriate parallel data structures - be done in O(1) time. > This is for integer partitions, but compositions are simply the permutations > on the > full length of the list of each partition. > > http://code.activestate.com/recipes/218332-generator-for-integer-partitions/ > > Maybe Timmy will provide something more efficient than his partition code > combined with itertools.permutation. I'm not sure if such shortcuts exist > myself. As Mark said, solving this particular problem is a straightforward application of itertools.combinations. > ... > If we had a composition() function (maybe in itertools... but more likely in > more-itertools given the minimalist philosophy of itertools itself) .... For the ambitious, generating combinatorial objects is a huge topic of its own, but really doesn't belong in itertools. It's unfortunate that `combinations` and `permutations` and `product` live there already, because they really have little to do with "iterator algebra". They're just ordinary generators that can't exploit lazy arguments even when iterators are passed.(first thing they do is convert their iterable arguments to tuples). On the other hand, there is no standard module they _do_ belong in. I'm _starting_ to get concerned that the `math` module may become an incoherent mess over time. For example, we just added `math.comb()`, which didn't really fit anywhere else either, but in an ideal world _would_ live in the same module as `itertools.combinations()`. On the third hand, we haven't yet sprayed enough combinatorial functions all over creation to make much of a case for adding a module dedicated to that area of discrete math. But we certainly _could_ ;-) _______________________________________________ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/O3K4OCNKRERTOVNYKWIJKGVVQHJRGSBP/ Code of Conduct: http://python.org/psf/codeofconduct/
