Opened 2 years ago

Closed 12 months ago

#30483 closed defect (fixed)

Deprecate Combinations iterator for itertools/combinations or IntegerListsLex

Reported by: Samuel Lelièvre Owned by:
Priority: major Milestone: sage-9.5
Component: combinatorics Keywords:
Cc: Frédéric Chapoton, Samuel Lelièvre Merged in:
Authors: Mike Hansen Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: 007700a (Commits, GitHub, GitLab) Commit: 007700a609949e47d60b102bfac47d73d4a5cb7f
Dependencies: Stopgaps:

Status badges

Description (last modified by Samuel Lelièvre)

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 (12)

comment:1 Changed 2 years ago by Samuel Lelièvre

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 2 years ago by Sébastien Labbé

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 2 years ago by Sébastien Labbé

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 2 years ago by Matthias Köppe

Milestone: sage-9.2sage-9.3

comment:5 Changed 20 months ago by Matthias Köppe

Milestone: sage-9.3sage-9.4

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

comment:6 Changed 15 months ago by Matthias Köppe

Milestone: sage-9.4sage-9.5

comment:7 Changed 13 months ago by Mike Hansen

Branch: u/mhansen/deprecate_combinations_iterator_for_itertools_combinations_or_integerlistslex

comment:8 Changed 13 months ago by Frédéric Chapoton

Commit: 007700a609949e47d60b102bfac47d73d4a5cb7f

needs review ?


New commits:

007700aTrac #30483: Use itertools to iterate through Combinations

comment:9 Changed 12 months ago by Samuel Lelièvre

Authors: Mike Hansen

comment:10 Changed 12 months ago by Mike Hansen

Status: newneeds_review

comment:11 Changed 12 months ago by Frédéric Chapoton

Reviewers: Frédéric Chapoton
Status: needs_reviewpositive_review

ok, thanks

comment:12 Changed 12 months ago by Volker Braun

Branch: u/mhansen/deprecate_combinations_iterator_for_itertools_combinations_or_integerlistslex007700a609949e47d60b102bfac47d73d4a5cb7f
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.