Polyhedron and combinatorics; evalf(1); quick_sort; Basic.copy()

[smichr]

this is the same as #1498 but committed against 0.7.2

[amakelov]

I'll take a look at this as soon as I have some free time : )

[smichr]

Thanks!

[asmeurer]

Why is this against 0.7.2?

[haz]

Is there any merit to having full_cyclic_form1 and/or cyclic_form0 defined?

[smichr]

It looks like they were added for convenience so when someone wants to enter notation as it appears in a book, for example, that is 1-based with singletons omitted, and see the result in the same form, they can do

p = Permutation(full_cyclic_form1(what_I_see, size))
...do something
print cyclic_form1(p.cyclic_form)

The full_cycle_form0 is also needed because Permutation requires that all indices be present whereas standard notation allows singletons to be omitted. Perhaps methods could be modifed to use a sparse-permutation storage and then it wouldn't matter if they used 1-based or 0-based notation.

[haz]

I haven't been following things too closely, so my feedback is quite shallow unfortunately. One further meta comment I had was about xrange -- I remember seeing that sympy was moving towards using only range. Is this not the case anymore?

[asmeurer]

xrange vs. range doesn't matter that much. If it's potentially big, use xrange. And obviously if you need to index it, use range.

[smichr]

Why is this against 0.7.2?

Because I was hoping to have it be part of 0.7.2 to fill out the combinatorics changes that were already made.

[smichr]

xrange has been changed to range. question to self: is range indexable in 3.3 or does it return an iterator?

[smichr]

ok, range(10, 20, 2)[3] works in 3.x

[smichr]

There are going to be failures because of the R to L multiplication change. I'll work these out but am leaving this open for any other comments.

[smichr]

I think things are ok after all.

[asmeurer]

Unless this has a significant API change, it would be better to merge this into master. 0.7.2 should only have bug fixes or major API changes that would rather not wait a release, so that it can stabilize.

[asmeurer]

Sorry to be a stickler about it, but if we only released when there are no new patches coming in, then we would never release (this is almost what is happening already).

[smichr]

No problem either way, but here's what's happened so you can decide which way you want this to go:

1. evalf(1) can be done
2. there is a quick_sort function for handling intra-session arg ordering
3. Polyhedron has been added
4. lots of changes to how Permutation works and many of the previous functions deleted

Perhaps 1 and 2 could go in now? We're still discussing the current behavior of how Permutations are multiplied and if a change is made there it's going to be major.

[smichr]

I can close this and reopen 1498. I'll wait for your advice, @asmeurer .

[asmeurer]

I think if anything we should try to finalize the Permutation convention before the release, especially if we are going to change it. But how soon can it be done?

[jrioux]

What is the benefit of quick_sort, is it really that much faster than sorted(x, key=default_sort_key) and worth the complication?

[smichr]

It uses hash sorting and if there are no clashes, you are done. This has
got to be faster than constructing a key based on the tree of an
expression...at least I would think so. And I guess that's why it is used
in Add to do the sorting (or is it Mul -- one of the two).

[smichr]

I know there is a test failure in the demonstration of using DisjointCycle multiplication because I'm floundering with the class construction. I would like DisjointCycle and BaseDisjointCycle (should be renamed to put Base at the end) to be merged together if possible -- but not sure that it is possible -- and I want the returned object to come back as DisjointCycle, not defaultdict and I'm not sure how to get that done. Can anyone see what I'm trying to do and give me a hand? @ness01 , perhaps, or anyone else that is fluent in object creation?

[ness01]

I'm sorry, but it is unclear to me what you are trying to do. The following merges BaseDisjointCycle and DisjointCycle, and creates the constructor you like, plus copying:

diff --git a/sympy/combinatorics/permutations.py b/sympy/combinatorics/permutations.py
index 5746162..c0ba9c9 100644
--- a/sympy/combinatorics/permutations.py
+++ b/sympy/combinatorics/permutations.py
@@ -213,9 +213,7 @@ def __str__(self):
         reduced = Permutation(self.as_list()).cyclic_form
         return str([tuple(c) for c in reduced])

-
-class DisjointCycle(BaseDisjointCycle):
-    def __new__(cls, *args):
+    def __init__(self, *args):
         """Load up a BaseDisjointCycle instance with the values for the cycle.

         Examples
@@ -226,7 +224,11 @@ def __new__(cls, *args):
         """

         from sympy.ntheory.residue_ntheory import int_tested
-        d = BaseDisjointCycle()
+        if len(args) == 1 and isinstance(args[0], BaseDisjointCycle):
+            for k, v in args[0].iteritems():
+                self[k] = v
+            return
+        d = self
         if not args:
             return d
         args = int_tested(args)
@@ -234,8 +236,9 @@ def __new__(cls, *args):
         args += [args[0]]
         for i in range(n):
             d[args[i]] = args[i + 1]
-        return d

+    def copy(self):
+        return BaseDisjointCycle(self)

 class Permutation(Basic):
     """

Note that it is not obvious to me if this is particularly pythonic style.

In any case, what is the difference between the BaseDisjointCycle class and the Permutation class? Note that the product of two cycles need not be a cycle, so I suppose BaseDisjointCycle is a representation of a permutation in disjoint cycle form, plus multiplication in reversed order? And interpretation of iterables as cycles? If this is the case, I would suggest that the concerns should be separated: (1) a method (not necessarily in the python sense) to reverse multiplication order, (2) a method (in the python sense) to display the disjoint cycles of a permutation, (3) a method (not necessarily in the python sense) to interpret iterables as cycles, and (4) possibly a redesign of the permutation classes to allow different representations, one of which could be via disjoint cycles.

For (1), I would like to use the python with statement if possible. We could additionally support a function leftMul(perm1, perm2, ...). A thin wrapper LeftMul()_perm1_perm2 could also work, but getting out the permutation requires additional brackets as far as I can tell.

(2) Is very easy to implement.

(3) Could either follow the same ideas as (1), or (imho preferrably) just declare tuples to be cyles and lists to be "permutations in array form".

(4) I don't know enough about.

I hope this is of any help. Let me know if you would like me to code up some of this, I should have smallish amounts of free time starting from next week.

[asmeurer]

(1) would be very painful, because it would have to change the order globally, meaning that all algorithms would essentially have to be written in an order independent way.

[smichr]

btw, making mul work from R to L or L to R is easy to do. We just need to decide how P1*P2 should be interpreted: apply P1 then apply P2 or vice versa. I'm leaning towards making the multiplilcation go from R to L.

[ness01]

@asmeurer Hm true.

@smichr I think it is clear that we can make __mul__ work L-R or R-L, the more interesting question is which of them (or both) to support.

[ness01]

@asmeurer Note that at least for groups, you can essentially switch between left and right multiplication by replacing every element by its inverse. (This isn't practical when entering, but allows an easy wrapper for algorithms, I think.)

[smichr]

Ignore the previous question about A and B and contains. I moved the old __eq__ code to is_in and this can be renamed easily if necessary. I wonder if is_subgroup and is_in can be merged, perhaps by adding a keyword like strict which, if False, will do the resizing that is_subgroup does. I feel pretty confident that we shouldn't have __eq__ doing what it used to be doing, even if it means losing the convenience of using ==. Other ideas?

[smichr]

@pernici , this should be ready for any modifications that you want to make.

[pernici]

After the change in __eq__ to check that two groups have the same elements but have different generators
one can do G.is_subgroup(H) and G.order() == H.order(), which is longer than G == H

[smichr]

is_subgroup includes the check that

if G.order() % self.order() != 0:
            return False

If strict is True, should that be G.order() != self.order(), hence

if strict and G.order() != self.order or G.order() % self.order() != 0:
    return False

[asmeurer]

Shouldn't that be if strict and G.order() == self.order or G.order() % self.order() != 0:

[pernici]

It seems to me that the definition of is_subgroup is correct;
when strict and G.order() != self.order , self can be a subgroup of G, for instance A_5 is a subgroup of
S_5, with S_5.order() = 120, A_5.order() = 60

[pernici]

I made a pull request smichr#16; apart from adding a default argument to
is_transitive, I fixed a bug in base; the order in the strong base matters, but I used previously a dict
in computing it, so the order was in general lost.

[smichr]

is_subgroup correct

I think I was confusing degree with order. I think the current implementation is fine.

I fixed the doctest error in the patch and made another modification.

SymmetricGroup(3).is_subgroup(CyclicGroup(5)*SymmetricGroup(3)) should be True

In order for this to happen we need better resizing. For this case, Permutation(*range(n)) should be resized to Permutation(*range(new_n)) and Permutation(*range(n-1)) resized to Permutation(*range(new_n-1)) BUT how do we know that that is what is intended by a given permutation, what if the user meant "a cycle of only the first two elements" not "a cycle of all but the last element". Is resizing ever a good idea? I'm leaning towards "no" (even though I just added another commit for it that allows resizing in contains()).

[pernici]

SymmetricGroup(3).is_subgroup(CyclicGroup(5)*SymmetricGroup(3)) should be True

No, I wrote that before, but it is not true.
SymmetricGroup(3) acts on [0,1,2], while the subgroup SymmetricGroup(3)
in CyclicGroup(5)*SymmetricGroup(3) has support [5,6,7] (it leaves fixed 1,..,4), so they are different groups,
although isomorphic.
Different is the case of

>>> SymmetricGroup(3).is_subgroup(SymmetricGroup(3)*CyclicGroup(5), strict=False)
True

In this case the two SymmetricGroup(3) have the same support, so in the strict=False sense they are equal.

[pernici]

I would like to eliminate the stabilizer_cosets method; it is almost a duplicate of basic_transversals;
_stabilizer_cosets can be trivially obtained from _transversals and _base; if i is not in G._base
then G._stabilizer_cosets[i] = [range(size)]; otherwise G._stabilizer_cosets[i] is the list of the array forms
of G._transversals[i].

For instance

>>> G = PermutationGroup([Permutation(6)(0,1,2), Permutation(5,6)])
>>> G.base
[0, 5]
>>> G.stabilizer_cosets()[0]
[[0, 1, 2, 3, 4, 5, 6], [1, 2, 0, 3, 4, 5, 6], [2, 0, 1, 3, 4, 5, 6]]
>>> G.basic_transversals[0]
{0: Permutation([], size=7), 1: Permutation([1, 2, 0], size=7), 2: Permutation([2, 0, 1], size=7)}
>>> G.stabilizer_cosets()[1]
[[0, 1, 2, 3, 4, 5, 6]]

[smichr]

On Mon, Sep 17, 2012 at 11:44 AM, pernici notifications@github.com wrote:

SymmetricGroup(3).is_subgroup(CyclicGroup(5)*SymmetricGroup(3)) should be
True

No, I wrote that before, but it is not true.
SymmetricGroup(3) acts on [0,1,2], while the subgroup SymmetricGroup(3)
in CyclicGroup(5)*SymmetricGroup(3) has support [5,6,7](it leaves fixed 1
,..,4), so they are different groups,
although isomorphic.
Different is the case of

OK. So do you think this is ready to commit to 0.7.2 or is there something
else that you think should be modified?

[pernici]

In smichr#17 coset_factor is 2x faster; I have taken away

        # look for another quick exit
        if any(p == g for ui in u for p in ui):
            return [I]*(len(u) - 1) + [g]

because g does not always belong to the last coset representative.

[pernici]

OK. So do you think this is ready to commit to 0.7.2 or is there something else that you think should be modified?

I do not like the duplication of data between _stabilizer_cosets and _transversals, but I suppose it can be
eliminated in some later PR.
I think it is ready to be committed.

[smichr]

OK, this is in. Thanks to all who helped in the review process. This ended up being a lot more involved that I imagined.

[asmeurer]

Awesome. Hopefully no issues slipped past Travis. It's time to release...

[coveralls]

Changes Unknown when pulling 419d310 on smichr:combinatorics into * on sympy:0.7.2*.

[coveralls]

Changes Unknown when pulling 419d310 on smichr:combinatorics into * on sympy:0.7.2*.

[coveralls]

Changes Unknown when pulling 419d310 on smichr:combinatorics into * on sympy:0.7.2*.