Opened 13 months ago

Last modified 6 hours ago

#30483 new defect

Deprecate Combinations iterator for itertools/combinations or IntegerListsLex

Reported by: slelievre Owned by:
Priority: major Milestone: sage-9.5
Component: combinatorics Keywords:
Cc: chapoton, slelievre Merged in:
Authors: Mike Hansen Reviewers:
Report Upstream: N/A Work issues:
Branch: u/mhansen/deprecate_combinations_iterator_for_itertools_combinations_or_integerlistslex (Commits, GitHub, GitLab) Commit: 007700a609949e47d60b102bfac47d73d4a5cb7f
Dependencies: Stopgaps:

Status badges

Description (last modified by slelievre)

As reported at

the iterator from Combinations hangs.

This ticket is to deprecate it in favour of the faster itertools/combinations or IntegerListsLex.

Change History (9)

comment:1 Changed 13 months ago by slelievre

  • Description modified (diff)

Possibly related:

  • #19986 - make Combinations a new style Parent
  • #5288 - Cython Gray code iterator for k-combinations of a set

comment:2 Changed 13 months ago by slabbe

IntegerListsLex provides the enumeration in *reverse* lexicographic order. So using this will break the code based on those rank and unrank methods... But using itertools should work.

comment:3 Changed 13 months ago by slabbe

copy pasting what I tried which creates lots of doctests failures because the ordering is reverse lexicographic:

  • src/sage/combinat/combination.py

    diff --git a/src/sage/combinat/combination.py b/src/sage/combinat/combination.py
    index 3722147f14..c286895f83 100644
    a b class Combinations_setk(Combinations_msetk): 
    420420             [2, 4, 5],
    421421             [3, 4, 5]]
    422422        """
    423         if self.k == 0:
    424             return self._iterator_zero()
    425         else:
    426             return self._iterator(self.mset, len(self.mset), self.k)
    427 
     423        from sage.combinat.integer_lists.invlex import IntegerListsLex
     424        C = IntegerListsLex(max_part=len(self.mset)-1, length=self.k, min_slope=1)
     425        for c in C:
     426            yield [self.mset[a] for a in c]

comment:4 Changed 11 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:5 Changed 7 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

comment:6 Changed 2 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5

comment:7 Changed 6 days ago by mhansen

  • Branch set to u/mhansen/deprecate_combinations_iterator_for_itertools_combinations_or_integerlistslex

comment:8 Changed 9 hours ago by chapoton

  • Commit set to 007700a609949e47d60b102bfac47d73d4a5cb7f

needs review ?


New commits:

007700aTrac #30483: Use itertools to iterate through Combinations

comment:9 Changed 6 hours ago by slelievre

  • Authors set to Mike Hansen
Note: See TracTickets for help on using tickets.