Opened 3 years ago

Closed 3 years ago

#25018 closed defect (fixed)

Bug in shuffle product `ShuffleProduct_w1w2`

Reported by: zabrocki Owned by:
Priority: major Milestone: sage-8.2
Component: combinatorics Keywords: combinat, words, shuffle product
Cc: saliola, darij Merged in:
Authors: Mike Zabrocki Reviewers: Darij Grinberg
Report Upstream: N/A Work issues:
Branch: 3f8f272 (Commits, GitHub, GitLab) Commit: 3f8f272c6e4450e82da4a871888b9612c3b32a42
Dependencies: Stopgaps:

Status badges


Here is the command that I entered to trigger this bug

sage: list(Words(1,1)[0].shuffle([2]))
[None, None]

The class sage.combinat.words.shuffle_product.ShuffleProduct_w1w2 tries to cast the output of the call in the parent of w1 but if it fails, it outputs None rather than something else.

Change History (18)

comment:1 Changed 3 years ago by zabrocki

Of course what we should see in that example is

sage: list(Word([1]).shuffle([2]))
[word: 12, word: 21]

The problem is the parent of Words(1,1)[0] is

sage: Words(1,1)[0].parent()
Finite words over {1}

and the output of the shuffle contains 1 and 2 and so the offending code in ShuffleProduct_w1w2

            return self._w1.parent()(res)
        except ValueError:
            # Special situation: the parent of w1 is too
            # restrictive to be cast on res.
            if isinstance(self._w1.parent(), Compositions_n):
                return Compositions(res)

has the problem that since it can't make [1,2] into a finite words over {1} and it isn't a composition, then it doesn't do anything.

comment:2 Changed 3 years ago by zabrocki

  • Cc saliola darij added

I am pretty sure that the line return Compositions(res) never gets called because (I believe) that line should read return Composition(res) (no s)

comment:3 Changed 3 years ago by darij

Ouch. The whole idea of trying to ducktype to self._w1.parent() smells to me, but I don't know how to improve on it. Can we take the union of two alphabets?

comment:4 Changed 3 years ago by zabrocki

The simple solution is just to add the line return res (which will just be a list in the case that the other checks fail) at the end of the except clause.

We could also check that isinstance(w1.parent(),FiniteWords) and if that is the case call return Word(res) and if it fails then just return res.

comment:5 Changed 3 years ago by zabrocki

  • Authors set to Mike Zabrocki
  • Branch set to public/25018/bug_in_shuffle
  • Commit set to f75e10d4033a0bd51f61c1796bfb6cb25be92d90
  • Status changed from new to needs_review

New commits:

f75e10dif w1 is a word, return a word, else a list

comment:6 Changed 3 years ago by darij

Looks good, but care to add a doctest for the Composition fix?

sage: from sage.combinat.words.shuffle_product import ShuffleProduct_w1w2
sage: a = Compositions(1)([1])
sage: b = Compositions(2)([1,1])
sage: ShuffleProduct_w1w2(a, b).list()

should return

[[1, 1, 1], [1, 1, 1], [1, 1, 1]]

comment:7 Changed 3 years ago by zabrocki

  • Status changed from needs_review to needs_work

I think I will take a little more care with this. This code is generating bad parents right now and this could just push the error down the road.

sage: A = Compositions(6, inner=[2,3])[0]
sage: [B in B.parent() for B in A.shuffle_product([1])]
[False, False, False]

If I am not mistaken, this is actually a problem with the Composition code since this isn't right:

sage: Compositions(6, inner=[2,3])([2,2,2,2,2])
[2, 2, 2, 2, 2]
sage: _.parent()
Compositions of the integer 6 satisfying constraints inner=[2, 3]

comment:8 Changed 3 years ago by git

  • Commit changed from f75e10d4033a0bd51f61c1796bfb6cb25be92d90 to 3f8f272c6e4450e82da4a871888b9612c3b32a42

Branch pushed to git repo; I updated commit sha1. New commits:

3f8f272added doc test, minor change for test of Composition, correct import

comment:9 Changed 3 years ago by zabrocki

I modified the doc test that was there. This doesn't fix the parent problem, but I think that should be another ticket about the Composition code. What do you think?

comment:10 Changed 3 years ago by darij

TBH I prefer a new doctest rather than editing the old one. But I don't have an opinion on the parent issue... this is a design issue. How do `Partitions' do it? Do their parents also reflect all the restrictions that were placed when they were generated?

comment:11 Changed 3 years ago by zabrocki

Don't think of it as 'editing the old doctest', think of it as correcting it. The reason that doctest is there is to test those lines of code, and it didn't before and now it does.

Check out #15131 and run the test that was raised in the description *not* on this branch. You will see that it fails. You had already identified this as an error and opened (and closed) a ticket that didn't fix the problem.

You are right that Partitions does not fully check that an element is in the class when it creates an element. For example:

sage: B = Partitions(4,max_part=2)([3,1])
sage: B in B.parent()

comment:12 Changed 3 years ago by zabrocki

  • Status changed from needs_work to needs_review

comment:13 Changed 3 years ago by darij

I can't run it right now, as I'm going through a full rebuild of Sage (previous one was crashing on start reproducibly). But I don't understand your argument for why the old doctest shouldn't be left around.

comment:14 Changed 3 years ago by zabrocki

Please look carefully at the lines I changed and at the lines just above those. The same doc test was repeated twice so I have not removed anything. Instead I changed the second doctest so that it does what the sentence says it does. In between the two repeated doctests, it was written (just above where I changed it):

        Sage is no longer confused by a too-restrictive parent
        of `I` when shuffling two compositions `I` and `J`
        (cf. :trac:`15131`)::

So I corrected the doctest below that sentence so that it does what that sentence says.

I am 99.9% sure that this is what the original author of those lines (you) meant to put there before and unfortunately it was just missing the 3-4 characters that would have triggered the bug.

If you want, I can add a different doctest.

comment:15 Changed 3 years ago by darij

  • Status changed from needs_review to positive_review

Ah! Thanks for keeping track. I have long forgotten what errors I have fixed (or thought so) 4 years ago, but this should have been my intent. LGTM then!

comment:16 Changed 3 years ago by tscrim

Reviewer name.

comment:17 Changed 3 years ago by darij

  • Reviewers set to Darij Grinberg

comment:18 Changed 3 years ago by vbraun

  • Branch changed from public/25018/bug_in_shuffle to 3f8f272c6e4450e82da4a871888b9612c3b32a42
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.